우연히 github 의 trending 저장소에서 언어별로 알고리즘을 구현한 The Algorithms 에 들어가게 되었습니다.

이것 저것 클릭해 보다가 bogo sort 라는 알고리즘이 있길래 처음 듣는건데 뭐지 하고 봤더니 정말 엄청난 알고리즘이네요.

The Algorithms 에 있는 보고 정렬 구현 소스를 가져와 봅니다.

import random

def bogo_sort(collection):
    def is_sorted(collection):
        if len(collection) < 2:
            return True
        for i in range(len(collection) - 1):
            if collection[i] > collection[i + 1]:
                return False
        return True

    while not is_sorted(collection):
        random.shuffle(collection)
    return collection


if __name__ == "__main__":
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(bogo_sort(unsorted))

동작 방식은 배열이 정렬되어 있는지 확인하고(is_sorted) 정렬되어 있지 않다면 random 기능을 이용해서 요소를 다시 섞고 정렬 여부를 무한히 확인합니다.

유튜브 댓글에 나와 있듯이 운이 좋다면 빠를수 있는 알고리즘이고 일반적인 경우에는 언제 끝날지 알수 없는 정렬 알고리즘이네요.

Ref

Browser not supported