기본 정렬

3가지 기본적인 정렬을 소개한다. 이들은 시간 복잡도상으로 비효율적인 정렬 알고리즘군에 속한다. 선택 정렬과 버블 정렬은 ‘정렬되어 있지 않은 배열의 크기를 하나씩 줄여나가는 것’에 초점을 맞추고 있고, 삽입 정렬은 ‘정렬되어 있는 배열의 크기를 하나씩 늘려나가는 것’에 초점을 맞추고 있다는 특징이 있다.

선택 정렬(Selection Sort)

n의 크기를 가진 배열 내에서 가장 큰 원소를 찾아 맨 뒤(n번째 자리)로 보내고, n-1의 크기를 가진 배열(가장 큰 원소는 제외된 배열) 내에서 가장 큰 원소를 찾아 그 중 맨 뒤(n-1번째 자리)로 보내는 식으로 반복하는 방식이다.

• 이를 단계별로 쪼개어 생각해보면 이렇다.

  1. 배열을 순회하기 : n-1회 순회함
  2. 가장 큰 수를 찾기 : n에 비례하는 시간이 듦
  3. 두 수의 자리를 교환하기 : 상수 시간이 듦
• 점차 ‘정렬되어 있지 않은 배열’의 크기는 1씩 줄어들게 된다. 따라서, 비교하는 총 횟수는 (n-1) + (n-2) + … + 2 + 1 이 들게 되는 것이고 이는 n(n-1)/2 이므로, 선택 정렬은 Θ(n^2)의 시간이 드는 것이다.

버블 정렬(Bubble Sort)

선택 정렬과 마찬가지로, 제일 큰 원소를 끝자리로 옮기는 방식이되 그 옮기는 방식만 다르다. 이웃한 원소와 하나하나 비교하면서 순서를 바꾸어 나아가는 방식이다.

• 이를 단계별로 쪼개어 생각해보면 이렇다.

  1. 배열을 순회하기 : n-1회 순회함
  2. 이웃 원소와 비교하기 : 상수 시간이 듦
  3. 가장 큰 원소를 맨 끝으로 보내기 : n에 비례하는 시간이 듦
• 여기서도 마찬가지로, 점차 ‘정렬되어 있지 않은 배열’의 크기는 1씩 줄어들게 된다. 따라서, 비교하는 총 횟수는 (n-1) + (n-2) + … + 2 + 1 이 들게 되는 것이고 이는 n(n-1)/2 이므로, 선택 정렬은 Θ(n^2)의 시간이 드는 것이다.

삽입 정렬(Insertion Sort)

마치 땅따먹기를 하듯이, ‘정렬된 배열’의 범위를 순차적으로 넓혀가는 방식이다. 정렬이 틀어진 원소를 발견하면, 이를 ‘정렬된 배열’의 올바른 위치에 이를 삽입하여 채워넣는 원리다. 삽입 정렬의 큰 강점은 “배열이 거의 정렬되어 있는 상태로 입력된 경우에는 Θ(n)에 가까운 시간이 든다”라는 것이다. 물론 선택 정렬과 버블 정렬도 ‘무의미한 순환’을 위한 시간 낭비를 줄이게끔 구현할 수 있지만, 이를 위해 의식적으로 코드를 추가해야하므로 오버헤드가 생긴다. 반면, 삽입 정렬은 별다른 코드 추가 없이 효율적으로 순환한다.

• 이를 단계별로 쪼개어 생각해보면 이렇다.

  1. 배열을 순회하기 : n-1회 순회함
  2. 틀어진 순서의 원소를 발견하면, 이를 (while을 통해) 올바른 위치에 삽입하기 : 순서 조정이 필요한 원소를 i번째에서 발견했다고 쳤을 때, 최악의 경우 i-1회 순회함(물론, 평균적으로 절반 정도 훑겠지만.)
• 아예 역순으로 배열되어있는 최악의 케이스를 상상해보자. 그럼 1 + 2 + … + (n-2) + (n-1) 이 들게 되는 것이고 이는 n(n-1)/2 이므로, 삽입 정렬은 Θ(n^2)의 시간이 드는 것이다.

고급 정렬

3가지 고급 정렬을 소개한다. 병합 정렬과 힙 정렬은 최악의 경우에도 Θ(nlogn)이 소요되고, 퀵 정렬은 Θ(n^2)이 소요된다. 최악의 경우가 이런 것이고, 평균 성능은 퀵 정렬이 어떤 정렬에도 뒤떨어지지 않아 실무에서 많이 사용된다.

병합 정렬(Merge Sort)

입력을 반으로 나누어 각각을 정렬한 후 합치는 정렬. 다만 이게 재귀적으로 적용되기 때문에 반으로 쪼개진 후 그 ‘각각’이 또 병합정렬에 의해 정렬되어 합쳐지게 된다.

• 이를 단계별로 쪼개어 생각해보면 이렇다. 재귀적이기 때문에 한 번의 분할/병합 과정만을 나타내겠다.

  1. 배열을 반으로 나누기
  2. (반으로 쪼개진) 두 개의 배열을 각각 독립적으로 정렬하기 : 재귀가 들어가는 부분임
  3. 병합하기 : ‘전반부의 첫 원소’와 ‘후반부의 첫 원소’를 비교하여 그 중 작은 원소를 새 배열의 앞부터 채움. 대신 여기서 활용된 원소는 기존 배열(전반부/후반부)에서 제외시키고, 첫 원소 비교를 되풀이. n에 비례하는 시간이 듦
• 전반부와 후반부의 배열을 서로 병합할 때에는 n에 비례하는 시간(즉, cn)이 들고, 전반부와 후반부 각각은 독립적으로 정렬할 때 2T(n/2)이 들기 때문에 T(n) <= 2T(n/2) + cn이 성립한다.
• 반복 대치를 이용해 수행 시간을 구해보면 Θ(nlogn)이 나오며, 물론 마스터 정리(a = b = 2, f(n) = n 에 해당)를 써도 Θ(nlogn)가 나온다.

퀵 정렬(Quick Sort)

기준원소를 정해서 그보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 재배치하는 방식이다. 이 또한 재귀적으로 적용되기 때문에 그 ‘각각’이 또 퀵 정렬에 의해 재배치 된다. 퀵 정렬은 병합 정렬과 다르게 재귀적 해결 이후 더 이상의 후처리가 필요없다.

• 이를 단계별로 쪼개어 생각해보면 이렇다. 재귀적이기 때문에 한 번의 분할 과정만을 나타내겠다.

  1. 기준원소를 정해 이보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 재배치하기 : 모든 원소가 기준원소와 비교되어야 하므로 이 과정에서 n에 비례하는 시간이 듦
  2. (기준원소를 기준으로 쪼개진) 두 개의 배열을 각각 독립적으로 정렬하기 : 재귀가 들어가는 부분임
• 모든 원소를 기준원소와 비교하는 과정에서 Θ(n)이 든다. 퀵 정렬에서 가장 이상적인 경우는 분할이 항상 반반씩 균등하게 될 때이며, 최악의 경우는 항상 한쪽에 모든 원소가 쏠리는 때이다. 전자의 경우 T(n) = 2T(n/2) + Θ(n)이 되어 Θ(nlogn)이 들고, 후자의 경우 T(n) = T(n-1) + Θ(n)이 되어 Θ(n^2)이 든다.

힙 정렬(Heap Sort)

힙이라는 특수한 자료구조를 사용하는 방식이다.

[참고] 힙(Heap)이란?
힙은 이진 트리로서, 맨 아래층을 제외하고는 모두 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져있다. 힙의 모든 노드는 힙성질을 만족해야 한다. 최소힙/최대힙의 개념이 있는데, 최소힙을 기준으로 힙성질은 “각 노드의 값은 자기 자식의 값보다 작거나 같다”이다.

• 이를 단계별로 쪼개어 생각해보면 이렇다.

  1. 주어진 배열을 힙으로 만들기
  2. 힙에서 가장 작은 원소(루트 노드)을 제거하고, 대신 다른 노드의 원소를 루트 노드 자리에 두기 : 제거한 순서대로 배열에 채워둠
  3. 힙성질을 만족하도록 힙 수선해주기(= heapify) : 이를 통해 1)로 되돌아가게 됨
• 배열을 처음 힙으로 만드는 과정에서 Θ(n)이 든다. 그리고 루트 노드를 제거(pop)한 후 망가진 힙성질을 수선할 때, 높이에 비례하는 Θ(logn)이 든다. 이렇게 하나씩 루트 노드를 계속 제거하며 n에 비례하게 반복해야하므로 결국 Θ(nlogn)의 시간이 든다. 처음 힙을 만들 때 드는 Θ(n)과 heapify에서 드는 Θ(nlogn)의 합으로 마침내 힙 정렬은 Θ(nlogn)이 들게 된다.

---

[참고자료]
문병로(2018). 관계 중심의 사고법, 쉽게 배우는 알고리즘. 한빛아카데미.
https://im-developer.tistory.com/135