정렬 알고리즘 정리

 

정렬 알고리즘은 데이터를 특정한 기준에 따라서 정렬하기 위해 사용하는 알고리즘입니다.

대표적인 정렬 알고리즘의 동작 아이디어를 한 문장으로 정리해보겠습니다.

 

정렬 알고리즘	핵심 아이디어
선택 정렬	가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법이다.
삽입 정렬	데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법이다.
퀵 정렬	기준 데이터(Pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
계수 정렬	특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법이다.

 

대표적인 정렬 라이브러리를 성능에 따라서 비교해보겠습니다.

정렬 알고리즘	평균 시간복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단하다.
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때 가장 빠르다.
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠르다.
계수 정렬	O(N + K) (K는 데이터 중에서 가장 큰 양수)	O(N + K) (K는 데이터 중에서 가장 큰 양수)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작한다.

 

정렬 알고리즘 종류와 시간복잡도 계산

 

파이썬의 표준 라이브러리에서 기본으로 제공하는 정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

따라서 계수 정렬을 사용해 매우 빠르게 정렬해야 하는 특이한 케이스가 아닐 시, 파이썬의 정렬 라이브러리를 사용하는 것이 가장 합리적이다.

정렬은 다양한 알고리즘에 사용되는데, 대표적으로 이진 탐색의 경우 데이터가 정렬되어 있을 때만 사용이 가능하다.

또한 '크루스칼 알고리즘'의 경우, 간선의 정보를 정렬하는 과정이 반드시 필요하다.

이처럼 문제를 해결하기 위해서 정렬을 요구하는 경우가 매우 많기 때문에 파이썬의 정렬 라이브러리의 사용 방법을 익히는 것이 중요하다.

 

이 포스트는 '이것이 코딩 테스트다' 정렬을 공부하고 정리한 내용입니다.