정렬 알고리즘(Sorting Algorithm)

항상 정렬 헷갈리네요. 오름차순으로 정렬했을 때를 가정하고 정리해볼게요.

 

Bubble Sort

인접한 두 개의 데이터를 비교해가면서 가장 큰 값을 배열 맨 끝에 두면서 정렬합니다. 한 턴마다 비교대상 중 가장 큰 값이 그 중 제일 뒤에 가도록 보장합니다.

시간 복잡도 : O(n^2)

 

Selection Sort

앞에서부터 시작하여 해당 수보다 작은 수를 찾고, 만약 찾았으면 그 수랑 swap하고 없으면 (그 수가 가장 작은 수이기 때문에) 그대로 둡니다. 다음은 그 다음 인덱스부터 비교합니다. 한 턴마다 비교대상 중 가장 작은 값이 제일 앞에 가도록 보장합니다.

시간 복잡도 : O(n^2)

 

Insertion Sort

index 1부터 시작하여 해당 인덱스 아래 수와 비교하며 더 작은 수를 발견할 때까지 앞으로 이동합니다. 앞의 인덱스들부터 비교하여 정렬해놓기 때문에 i번째 비교시작할 때 i-1 이하 인덱스들은 모두 정렬되어 있는 것입니다. 만약 애초에 오름차순으로 정렬이 다 되어있다면 n번에 정렬이 끝날 수도 있습니다.

시간 복잡도 : O(n^2)

 

Merge Sort

병합 정렬의 아이디어는 기본적으로 'Divide Conquer and Combine'입니다. 재귀를 통해 가장 작은 단위까지 쪼갭니다. 그리고 쪼갠 것끼리 서로 비교하여 정렬하고 합쳐 결국 가장 큰 단위까지 오게되는 것입니다. 재귀에 대한 부분은 이 부분입니다.

void mergeSort(int[] a, int m, int n) {
    if(m < n) {
        int middle = (m + n) / 2;
        mergeSort(a, m, middle);
        mergeSort(a, middle + 1, n);
        merge(a, m, middle, n);
    }   
}

여기서 mergeSort는 재귀에 관한 부분이고 merge가 이제 봉합하면서 정렬에 대한 부분입니다. 재귀의 특성을 아름답게 잘 사용한 정렬이라고 생각합니다. 정렬한 수를 담을 배열은 전역변수로 선언해서 사용하여 담을 수 있습니다. 시간 복잡도는 간략하게 n개의 개수에 대해서 lon(n)만큼 계산되기 때문에 n^log(n)로 말할 수 있습니다.

시간 복잡도 : O(n*log(n))

 

Heap Sort

힙 정렬은 힙이라는 자료구조에서 가장 위의 수를 꺼내어 정렬하는 방법입니다. 가장 위의 수가 가장 작은 수라는 것은 보장하지만 그 아래에 대해선 힙의 질서로 되어있을 뿐 정렬은 되어있지 않습니다. 그래서 가장 위의 수를 꺼내고 Heapify라는 과정을 거치는데 log(n)의 시간이 소요됩니다(트리의 특성상). n개의 수가 있다면 결국 시간복잡도는 n*log(n)이 되는 것입니다.

시간 복잡도 : O(n*log(n))

 

Quick Sort

퀵정렬도 병합정렬과 마찬가지로 'Divide and Conquer'의 개념을 적용합니다. 또 재귀도 적용을 하는데요. 다른 점이 있다면 퀵정렬에서는 '피봇'이라는 개념을 사용한다는 것입니다. 피봇은 정렬을 하기 위한 기준점을 제시합니다. 이 기준점을 바탕으로 왼쪽에는 작은 수, 오른쪽에는 큰 수를 만족시키구요. 이러한 규칙이 점점 작은 단위로 재귀를 통해서 만족됨으로써 결국 전체적으로 정렬이 되는것입니다.

보통은 구현시 가장 앞쪽 인덱스를 피봇으로 설정해두구요. 인덱스 1를 i, 맨 끝 인덱스를 j로 두어 피봇보다 큰 i를 구하고, 피봇보다 작은 j를 구해 서로 2개의 데이터를 swap합니다. 그리고 i, j가 엇갈릴 때 그만두고 다음 재귀가 시작됩니다. 맨 처음이 피봇을 기준으로 피봇보다 작은 왼쪽, 피봇보다 큰 오른쪽으로 나누어졌다면 이제 왼쪽, 오른쪽 각각에 대해서 정렬이 시작되는 것입니다.

시간 복잡도 : O(n*log(n))

 

stable sort와 unstable sort

정렬에서 같은 값을 가진 데이터가 정렬 후 입력순으로 그대로 유지가 될 때 stable하다고 하고 그것을 보장하지 않을 때는 unstable하다고 합니다. stable이냐 unstable이냐는 각 sort마다 어떻게 구현되는지를 알면 구분할 수 있을 것입니다.

• Bubble Sort : stable

  • 같은 값을 가진 데이터 간에는 움직이지 않습니다

• Selection Sort : unstable

  • 같은 값을 가진 데이터 뒤에서 swap될 수도 있습니다
  • 예) 5(1), 4(1), 5(2), 2(1), 3(1) → 2(1), 4(1), 5(2), 5(1), 3(1)

• Insertion Sort : stable

  • 같은 값을 가진 데이터 간에는 움직이지 않습니다

• Merge Sort : stable

  • 병합정렬은 병합할 때 입력순부터 먼저 병합되기 때문에 순서가 보장됩니다.

• Heap Sort : unstable

  • 힙 구조는 주어진 수가 힙 구조내에서 어느 노드의 밑에 있느냐에 따라서 같은 수라도 더 뒤에 있는 수가 Heapfify후 root로 올 수도 있습니다

• Quick Sort : unstable

  • 피봇을 기준으로 순서와 관계없이 바뀌므로 순서를 보장하지 않습니다.
  • 예) 3(1) 5(1) 5(2) 1(1) 3(2) 2(1) 2(2) 5(3) → 1(1) 2(2) 2(1) 3(1) 3(2) 5(2) 5(1) 5(3)