python의 sort()의 시간 복잡도

python의 sort는 어떤 알고리즘을 사용할까?

주로 사용되는 정렬함수 [ sorted() ] 와 리스트 타입의 메소드 [ sort() ] 는 모두 내부적으로 'Timsort' 알고리즘을 사용한다.

 

Timsort는 팀 피터스가 파이썬을 위해 개발한 정렬 알고리즘이다.

삽입 정렬과 병합 정렬의 특징을 결합한 알고리즘이다. -> 이제 삽입 정렬과 병합 정렬에 대해서 알아보자

 

1) 삽입 정렬 [ Insertion Sort ]

- 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눈다.

- 정렬되지 않은 부분의 첫 번째 원소를 적절한 위치에 삽입하여 정렬된 부분을 확장해 나가는 방식으로 작동한다.

 

 

최선의 경우 : O(n)

평균, 최악의 경우: O(n^2)

 

특징: 

- 안정적인 정렬 방법이다.

- 작은 데이터 세트에 효율적이다.

- 추가 메모리 사용이 거의 없다.

 

2) 병합 정렬 [ Merge Sort ]

- 배열을 반으로 나눈다. 

- 각 부분을 재귀적으로 정렬한다.

- 정렬된 두 부분을 병합하여 전체를 정렬한다.

 

Merge Sort에 대한 그림도 그려보려고 했으나.. 조금 지쳐서 url로..넘겨보려 한다..ㅎㅎ!! 구글에 설명이 잘 나왔다.

search 병합 정렬 on google...

 

데이터들을 다 분리하고 합치면서 정렬하는.. 그런 방법이다.

 

특징:

- 최선, 평균, 최악 : O(n log n)

- 안정적인 정렬 방법이다.

- 큰 데이터 세트에 효율적

- O(n)의 추가 메모리 공간을 필요로 한다.

 

3) Tim sort [ insertion sort + merge sort ]

주로 배열의 일부가 이미 정렬되어 있을 때 높은 효율을 보인다.

- 최선의 경우: O(n)

- 평균의 경우: O(n log n)

- 최악의 경우: O(n log n)

 

타 언어에 비해, 이미 정렬이 어느정도 최적화 되어 있어, 비교적 자유롭게 sort()를 사용해도 될 것 같다.