[알고리즘]정렬 알고리즘

정렬

정렬은 주어진 데이터를 숫자의 순서나 어휘의 순서대로 나열하는 것이다. 데이터의 정렬은 빠른 탐색을 위한 것으로 데이터가 정렬되어 있는 경우 이진탐색을 할 수 있다.

이진탐색은 logn의 성능을 보이는데 이는 43억개의 정렬된 자료에서 어떤 값을 찾을 때 최악의 비교횟수가 32인 속도이다.

현재 비교정렬 알고리즘은 시간복잡도를 O(nlgn) 이하로 줄일 수 없다고 증명되었다.

대표적인 정렬의 종류

O(n²) 정렬

버블정렬 (Bubble Sort)

• 매번 연속된 두개의 인덱스를 비교하며 정한 기준의 값을 뒤로 넘기는 방식을 반복한다. 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동해 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.
• 시간복잡도가 거의 모든 상황에서 최악인 정렬방법. 이미 정렬된 자료일 경우는 최선의 성능

• 공간복잡도는 O(n)이다.

  선택정렬 (Selection Sort)

  

• 단순한 정렬 방법으로 모든 요소를 훑어서 가장 작은 데이터를 골라내는 방식을 n번 반복하며 복잡도는 O(n²)이다.
• 교환 과정이 n을 넘지 않으므로 교환비용이 많이 드는 상황에서 유용하다.
• 하나의 배열에서 정렬을 진행하므로 공간복잡도는 O(n)이다.

삽입정렬 (Insertion Sort)

• 모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 정렬된 배열 내 자신의 위치를 찾아 삽입
• 평균적으로 버블정렬, 선택정렬보다 빠르나 자료구조에 따라 밀어내는데 오랜 시간이 걸린다.
• 이미 정렬된 자료에 삽입/삭제하는 경우에 오버헤드가 적어 최선의 알고리즘
• 배열의 크기가 작을때 상당히 효율적이어서 배열의 크기가 클때는 O(nlng) 알고리즘을 쓰다가 삽입정렬로 전환하기도 한다.

O(nlgn) 정렬

병합정렬(Merge Sort)

• 원소의 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개서 자른 순서의 역순으로 크기를 비교해 병합하는 분할 정복 알고리즘이다. 병합된 부분은 이미 정렬되어 있으므로 전부 비교하지 않아도 제자리를 찾을 수 있다.
• 정렬할 데이터 크기만한 메모리가 더 필요하다.
• 퀵정렬, 힙정렬에 비해 성능이 떨어지지만 Stable sort(기존 데이터의 순서를 유지)이라는 장점이 있다.

• 정렬된 두 배열의 정렬된 합집합을 구할 때 병합정렬 알고리즘의 마지막 단계를 이용할 수 있다.

  힙정렬(Heap Sort)

  

• 원소들을 전부 힙에 삽입한 뒤 힙의 루트의 있는 값이 최소값(최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다. 힙이 빌 때까지 이를 반복한다.

• 일반적인 경우 퀵 정렬이 빠르지만 최악의 경우 O(n²)의 성능을 가지는 퀵 정렬에 비해 항상 O(nlgn)의 일정한 성능을 발휘한다.

  퀵정렬(Quick Sort)

  

• 적절한 원소 하나를 기준(피벗, pivot)으로 잡고 그보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈다. 그리고 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
• 평균적인 상황에서 최고의 성능을 나타낸다.
• C, C++, Java 등 거의 모든 언어에서 제공하는 정렬함수에서 퀵 정렬 또는 퀵 정렬의 변형 알고리즘을 사용한다.
• 피벗으로 어떤 값을 잡는지에 따라 효율이 달라진다. 최악의 경우 시간복잡도가 O(n²)가 되는데, 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우에 그렇다. 랜덤으로 피벗값을 잡는 것이 대표적인 방법이지만 O(n²)일수도 있으므로 순수한 퀵 소트보다는 다른 정렬 알고리즘과 섞는 하이브리드 퀵 소트를 쓴다.

하이브리드 정렬

인트로 정렬 (Intro sort)

• 퀵정렬 + 힙정렬
• 퀵 정렬을 기본으로 하지만 재귀 깊이가 깊어지는 경우 힙정렬을 사용한다.

팀 정렬 (Tim sort)

• 병합정렬 + 삽입정렬
• 병합정렬은 원소의 개수가 적을 때 오버헤드가 발생하기 때문에 파티션 크기가 특정 값(보통 16 또는 32) 이하일 때 삽입정렬을 사용한다.

각 언어에서 사용하는 정렬 알고리즘

Java

• Arrays.sort : 퀵 정렬
• Collections.sort : 합병정렬 (퀵 정렬이 stable하지 않고 일정한 효율 O(nlgn)을 보장하지 않아서)

Python

파이썬은 팀정렬(Tim sort)를 사용한다. 이는 stale하지 않기 때문이다.