Sorting Algorithm
정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬 알고리즘은 이진 탐색 의 전처리 과정이기도 하기 때문에 반드시 짚고 넘어가야 한다. 책에서는 다양한 정렬 알고리즘 중 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 언급했다.
Selection sort
말 그대로 데이터를 선택해서 정렬하는 것이다. 오름차순 정렬을 하고자 할 때 전체 데이터에서 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 두 번째 데이터와 바꾸고… 이러한 연산을 반복하면 된다.
하지만 선택 정렬은 다른 정렬 알고리즘과 비교해 시간 복잡도가 커 비효율적이다.
Insertion sort
삽입 정렬은 데이터를 하나씩 확인하며 필요할 때만 위치를 바꾼다. 따라서 데이터가 거의 다 정렬되어 있을 경우에 굉장히 효과적이다.
첫 번째 데이터는 정렬되어 있다고 가정하고, 두 번째 데이터부터 어떤 위치에 들어갈지를 판단해서 넣는다.
Quick sort
이름만 들어도 빠른 정렬이라는 생각이 든다. 퀵 정렬의 포인트는 pivot을 사용하는 것이다. 일종의 기준점 역할을 하는 피벗을 기준으로 큰 수와 작은 수를 교환하는 방식으로 동작한다. 연산이 끝날때 마다 리스트를 반으로 나누기 때문에 빠른 시간 내에 정렬이 가능하다.
Count sort
계수 정렬은 특정한 조건이 부합할 때 사용하면 매우 빠른 알고리즘이다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이라고 한다. 왜냐하면 모든 범위를 담을 수 있는 크기의 리스트를 선언해서 사용 해야 하기 때문이다.
특히 성적 분포처럼 동일한 값을 갖는 데이터가 여러 개 존재할 때 적합하다. 요약하자면 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터가 많이 중복되어 있을수록 유리하다.
정렬 알고리즘별 시간 복잡도
참고로 파이썬의 정렬 라이브러리 sorted 함수는 O(NlogN) 을 보장한다.
참고
- 이것이 취업을 위한 코딩 테스트다