Python - Sort 알고리즘

Sort Algorithm

Python의 Sort는 어떤 알고리즘을 사용하는가?

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467–474, January 1993. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subsequence, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python’s standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[3] on the Android platform,[4] and in GNU Octave.[5]

Timsort 알고리즘은 Merge sort에서 변형이 되었고, Merge sort는 평균 시간복잡도 O($nlogn$)이며 worst case에서도 O($nlogn$)이다.

Quick Sort의 worst case에서는 O($n^2$)이다.

Quick Sort / Merge Sort

Merge Sort

분할을 하고, 정렬을 한 후 합쳐오는 과정을 걸친다.

Quick Sort

---

Quick 정렬은 Pivot (기준값)을 정하고, 자기보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치를 시킨다.

그 이후, Pivot 기준으로 왼쪽과 오른쪽을 또 다시 같은 행위를 반복한다.

이렇게 반복하여, 모든 값들이 정렬될때까지 진행을 한다.

Merge 정렬은 순차적으로 인접한 2개의 값을 정렬을 한다, 그 다음 2개를 정렬 한 후, 각각 정렬된 4개를 정렬한다.

그 이후, 2개를 정렬하고, 또 다시 2개를 정렬 한후, 각각 정렬된 4개를 정렬한다.

그 이후 4개씩 정렬된 2파티션을 정렬한다.

반복하여 모든 값들을 정렬한다.

다음과 같은 구조일때 Sort결과는 어떻게 되는가?

Class의 값들을 가지고 있는 List를 Sort하였을때, 내부 변수 a, b에 따라 어떻게 작동을 하게 되는지 알아보자.

a를 기준으로 먼저 sort를 하면, a기준으로 오름차순 정렬이 되어있을 텐데, 이 상태에서 b기준으로 재정렬을 하게 되면, a의 상태는 어떻게 되는가?

class A:
    def __init__(self, a: str, b: str):
        self.a: str = a
        self.b: str = b

if __name__ == "__main__":
    test_information = [A("A", "B"), A("Test", "Code"), ....., A("EEE", "DDDD" ]
    sort(test_information, key=item(0))
    sort(test_information, key=item(1))

sorted의 기준은 class 객체이므로, b로 정렬을 하였다면, a의 순서는 b와 pair로 된 상태가 된다.