Python은 어떤 정렬 알고리즘을 이용할까?

토즐라·2022년 6월 24일

1D1Q

목록 보기

5/7

Question

파이썬의 sorted 내장함수는 어떤 정렬 알고리즘을 이용할까?🤔

00. 개요

정렬 알고리즘은 컴퓨터 분야에서 굉장히 중요하게 여겨지는 문제 중 하나로, n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘입니다.

자료구조, 알고리즘 과목에서 과거에 정말 많은 정렬 알고리즘을 공부했습니다. $O(n^2)$ 의 시간복잡도를 가지고 있는 Selection sort, Insertion sort, Bubble sort와 $O(n \log n)$ 의 시간복잡도를 가지고 있는 Merge sort, Heap sort, Quick sort, Tree sort 등등 지금 생각나는 것만 적어도 6개나 됩니다.

문득 알고리즘 문제를 풀다 파이썬은 이 많은 정렬 알고리즘중에 어떤 알고리즘을 내장함수 내부에 채택하고 있는지, 왜 그 알고리즘을 채택한 것인지 궁금해졌습니다.

따라서 파이썬의 내장함수는 어떤 정렬 알고리즘을 이용하고 있는지, 또 문제에 따라 다른 알고리즘을 직접 구현해 풀 필요가 있는지 차근차근 알아보겠습니다.

01. 파이썬의 정렬 알고리즘

python에서 자료를 정렬할 때 쓰는 방법에는 두 가지가 있는데, 바로 리스트에 sort() 메소드를 적용하는 방법과 sorted() 내장함수를 이용하는 방법입니다. 그렇다면 이 두 방법은 어떻게 다르고, 어떤 상황에서 어느 함수를 이용해야 하는지 알아보겠습니다.

list.sort()
sorted(list)

sort()

This method modifies the sequence in place for economy of space when sorting a large sequence. To remind users that it operates by side effect, it does not return the sorted sequence (use sorted() to explicitly request a new sorted list instance).
python 3.10.5 manual

우선, sort 함수는 리스트명.sort() 형식으로 이용하는 리스트형의 메소드입니다. 즉, 이 함수는 입력값으로 리스트밖에 받지 못합니다. 또, 이 함수는 리스트 원본값을 직접 수정합니다.
또, sorted()함수와는 다르게, 정렬을 수행한 리스트를 따로 반환하지 않습니다.

sorted()

Return a new sorted list from the items in iterable. ... The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).
python 3.10.5 manual

sorted 함수는 sorted(리스트명) 형식으로 이용하는 내장함수이며, 리스트 원본 값은 그래도 유지합니다. sort 함수와는 다르게 어떤 입력값이든 받을 수 있습니다. 또, 이 함수는 정렬 작업을 수행한 후의 값을 반환합니다.

그럼 둘 중 뭘 쓰면 되나요?

원본을 유지해야 할 때에는 sorted() 함수를 이용하면 됩니다.
리스트 말고 다른 자료형을 정렬할 때에는 sorted() 함수를 이용하면 됩니다.
원본이 필요 없을 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.
list를 이용할 때에는 시간, 공간 절약을 위해 sort() 함수를 이용하면 됩니다.

아래부터는 더 범용적으로 사용할 수 있는 sorted() 함수의 내부 알고리즘을 알아보겠습니다.

02. Timsort 알고리즘

The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.
python 3.10.5 manual

파이썬의 sorted() 함수는 Timsort 알고리즘을 이용합니다.

Timsort 알고리즘이란?

우선, timsort 알고리즘에 대해 굉장히 잘 정리되어 있는 네이버 기술블로그 글이 있어 링크 남깁니다. Timsort에 관한 자세한 내용은 위 링크를 참조하시면 좋을 것 같습니다. 아래 내용은 대부분 이 블로그의 글을 정리한 것임을 알립니다.

Timsort란 2002년 소프트웨어 엔지니어 Tim Peters에 의하여 만들어진 알고리즘으로, 앞에서 언급했던 Insert sort와 Merge sort를 결합하여 만든 Hybrid stable sorting 알고리즘입니다.

이 알고리즘은 미리 어느 정도 정렬된 부분이 존재하는 실생활 데이터의 특성을 고려하여 더 빠르게 작동하도록 고안된 알고리즘으로, 최선의 시간복잡도는 $O(n)$ , 평균은 $O(n \log n)$ , 최악은 $O(n \log n)$ 의 시간복잡도를 보여줍니다.

Timsort는 안정적인 두 정렬방법을 결합했기에 안정적이며, 추가메모리를 사용하긴 하지만 Mergesort에 비해 적은 추가 매모리를 사용하여 다른 $O(nlogn)$ 정렬 알고리즘의 단점을 최대한 극복한 알고리즘입니다.

이 알고리즘은 python을 제외하고도, java, android, google chrome, 그리고 swift까지 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있습니다.

Timsort는 mergesort를 기반으로 좀 더 효율적으로 덩어리 run을 나누고 제각기 다른 크기를 가진 run을 최대한 효율적인 방법으로 병합하여 실생활 데이터의 특성을 이용하여 여러 가지 최적화 기법을 도입한 정렬 알고리즘입니다. 완전히 무작위인 데이터에 대해서는 속도가 빠른 편은 아니지만 일정한 패턴이 있는 일반적인 데이터에 대해서는 빠른 성능을 보여주고 안정적이며 최악의 시간 복잡도가 $O(nlogn)$ 을 이룹니다.

Timsort의 작동 방식

Insertion sort는 인접한 메모리와의 비교를 반복하며 정렬을 진행합니다. 따라서, 작은 입력에 대해서는 insertion sort의 성능이 매우 좋은데요. 이것을 이용하여 전체를 작은 덩어리로 잘라서 각각의 덩어리를 insertion sort로 정렬한 뒤 병합하여 성능을 높이고자 하는 것이 Timsort의 기본적인 원리입니다.

Timsort는 run을 생성할 때 크기를 동적으로 구합니다. Run을 만들 때, 이미 정렬된 subsequence를 기준으로 생성하며, 만약 minimum run size보다 작다면 insertion sort를 사용합니다.

Minimum run size는 데이터의 크기에 의해 결정되면, 만일 데이터의 크기가 64보다 작다면 minirun은 64가 되며, 사이즈가 큰 array에서는 32에서 64 사이의 minirun 크기를 가지고 분할시킵니다.

이렇게 모든 run이 만들어졌다면, 병합을 진행하는데 병합은 2개씩 이루어지면 stack을 이용해서 run을 push하고, 앞서 push되어 있던 run과 병합이 진행됩니다.

python의 timsort 알고리즘

cypthon 코드를 살펴보면 sorted() 함수 내부에 다음의 C 코드로 Timsort 알고리즘이 구현되어 있습니다.

앞선 네이버 블로그를 통해 이론을 파악하고 코드를 살펴보면 실제로 어떻게 Timsort 알고리즘이 구현되어 있는지 확실히 이해할 수 있으므로, 코드를 찬찬히 읽어보시는 것을 추천드립니다.

03. 정리

파이썬의 sorted 내장함수는 어떤 정렬 알고리즘을 이용할까?🤔

💡 파이썬의 sorted 내장함수는 Timsort 알고리즘을 이용합니다.
💡 Timsort 알고리즘은 느슨한 패턴을 어느 정도 지니는 현실 데이터에서 좋은 성능을 보입니다.
💡 따라서 Timsort는 파이썬 말고도 다른 언어에서 표준 정렬 알고리즘으로 활용되고 있습니다.