주요 정렬 요약(8+2)

나만의 언어로 암기해보기

• 버블 정렬: 이웃 교환의 연속
  • 셰이커정렬 : 이웃교환을 위 아래 번갈아서 함
• 단순선택(선택 정렬) : 자리 정해서 한번에 새치기(원격 교환)
• 단순삽입(삽입 정렬) : 한명씩 새치기
  • 이진 삽입정렬
• 셸 정렬: 징검다리 교환
• 퀵 정렬: 피벗을 기준 (원격)교환하며 분할 정복
• 병합 정렬: 반씩 쪼개서 분할 정복
• 힙 정렬: 힙으로 정렬해놓고 하나씩 꺼내며(다시 힙으로 만들면서) 정렬
• 도수 정렬: 누적도수 분포표를 인덱스로 사용하여 정렬  (비교 및 교환이 없음)

---

• 아래부터 각 정렬의 설명

버블(이웃 교환의 연속) - O(n^2)

• 맨 뒷쪽부터 상호 교환을 앞쪽 까지 함(한 패스)
• 패스를 n 번 반복함 (패스마다 교환이 n-1번씩 줄어듬)

개선

• 패스에서 교환이 안 일어나면 끝내기(break)
• 교환이 일어난 마지막 원소까지만 교환하기(last)
• 셰이커 - 교환이 방향을 번갈아 하기 (last 적용 가능)

---

단순 선택(자리 정해서 한번에 새치기) - O(n^2)

• 가장 작은 원소를 찾아, 가야할 자리의 카드와 교환
• 최소 값을 찾는 범위를 줄여가며 반복

---

단순 삽입(한명씩 새치기) - O(n) ~O(n^2)

• 원소를 선택하고 제자리로 갈때까지 앞의 원소와 교환
• 위의 과정을 두번째 원소부터 선택하여, 마지막 원소까지 반복

개선

이진 삽입 정렬

• 멈춰야 할 위치를 찾는 비교 연산을 이진 연산으로 줄임.
  • 찾고 나서는 찾은 위치까지 교환만 해나가면 됨
• 그러나 교환이 n번 되기 때문에 여전히 O(n) 이다.

---

셸(징검다리 교환) - O(n) ~O(n^1.25)~O(n^2)

• 단순 삽입의 장점은 살리고 단점은 보완
• 단순 삽입의 장단점
  • 장 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 빠름
  • 단: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많음

방법

• h 간격으로 배열을 여러 배열로 쪼개고 각 배열을 삽입 정렬 한 후 합친다.
• h 간격을 1까지 두배로 늘리면서 반복한다.
• h 가 서로 배수가 되지 않도록 하면 더 좋음

특징

• 안정적이지 않음

---

퀵 (피벗 활용 분할 정복) O(nlogn)~O(n^2)

• 단순 선택(서로 교환)의 스캔을 양쪽으로 하면서, 교환 기준을 피벗으로 줬다고 보면 될 것 같다.
• 한번에 정렬이 되지 않으므로 분할 정복한다.

방법

• 피벗을 정하여 배열을 두 그룹으로 나눔
• 피벗을 중심으로 양쪽 끝에서부터 스캔한다
  • 왼쪽은 피벗보다 큰 값을 찾을 때까지
  • 오른쪽은 피벗보다 작은 값을 찾을 때까지
• 찾은 값을 서로 교환한다.
• 피벗을 만날때까지 계속 교환한다.
• 위 과정을 나뉜 두 그룹에 대하여 재귀적으로 반복한다.
  • 베이스는 원소가 두개 이상인 배열

스택으로 비재귀적으로 만들 수 있다.

• 원소 수가 적은 배열이 나누는 과정이 더 빠름
• 먼저 푸쉬한 그룹이 나중에 나눠짐(스택 구조)
• 스택으로 구현 도중 원소 수가 더 많은 배열을 먼저 푸쉬하면 스택의 최대 크기를 낮출 수 있다.

피벗 선택법

배열에서 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택

• 원소가 3개 이상인 경우

발전된 방법

• 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬함
• 가운데 원소와 맨 끝에서 두번째 원소를 교환함

→ 정렬해야할 원소가 3개 줄어들고, 피벗이 대충 가운데에 있음.

---

병합(머지) O(nlogn)

• 분할 정복
• 분할, 정렬, 결합을 재귀적으로 반복한다.

---

힙 정렬  O(nlogn)

• 이미 힙 구조인 배열을 앞에서 하나씩 꺼내서 넣으면 정렬 됨
  • 힙에서 원소를 하나 꺼내고 나면, 다시 힙으로 만들어줘야 함
• 따라서 힙 구조가 아닌 배열이면 정렬 전에 반드시 힙으로 만들어야 함.

기본 개념

힙

• 부모의 값이 자식의 값보다 항상 큰 조건을 만족하는 완전 이진 트리
• 부모가 자식보다 항상 작아도 힙
• 형제 사이의 대소 관계는 일정하지 않음

완전 이진 트리

• 완전: 부모는 왼쪽 자식부터 추가하여 모양을 유지
• 이진: 자식의 최대 개수가 2개

힙을 배열로 나타냈을 때 인덱스

• 부모 : a[(i-1)]//2]
• 왼쪽 자식: a[i*2+1]
• 오른쪽 자식: a[i*2+2]

정렬 방법

1. 루트(가장 큰 수) 를 배열의 가장 오른쪽 수(리프의 가장 마지막)와 교환하며 루트 제거
2. 힙이 깨졌으므로 힙을 다시 만들어줌
3. 위의 과정을 반복

힙이 깨졌을 때 다시 힙을 만드는 방법

• 새로 들어간 루트를 큰 값을 가진 자식과 위치를 바꿈
• 바뀐 노드에서 또 다시 큰 값을 가진 자식과 위치를 바꿈
• 리프까지 갈 때까지 반복

배열을 힙으로 만들기(분할 정복)

아랫쪽이 모두 힙이라면 루트만 리프까지 이동하면 힙이 된다는 점에 착안한다

• 분할 : 루트를 중심으로 자식들을 하나의 트리(서브 트리)로 분할한다.
• 정복 : 루트를 이동해 서브트리를 힙으로 만든다.
• 결합 : 합치면 루트만 빼고 모두 힙이므로 루트를 이동하며 트리를 만든다.

즉, 분할을 계속 해서 가장 아랫 단계부터 상향식으로 올라간다.

---

도수정렬 O(n)

정렬 단계

1. 도수 분포표 만들기
2. 1을 이용하여 누적 도수 분포표 만들기
   • 각 인덱스별로 인덱스 이하의 수가 몇개인지를 저장하고 있음
3. 2를 이용하여 원래 배열을 새 배열에 복사하며 정렬

특징

• 다른 배열과 달리 원소들의 비교 및 교환이 없다.
• 배열 복사는 뒷쪽부터 해야 안정적(stable;같은 원소의 순서가 유지됨)이다.
• 시간 복잡도만 보면 '개쩌는 정렬이잖아?' 할 수 있지만 제약 조건이 있다.
  • 도수 분포표를 만들어야 하기 때문에 최소, 최댓값이 정해져 있어야 한다.
  • 공간복잡도가 O(n) 으로 올라간다. ;n은 최솟값과 최댓값의차이

---

최대한 간단히 썼는데도 정렬이 워낙 많다보니 길어졌다. 시간이 될 때 각 정렬에 대해서도 자세히 다뤄볼 예정이다.

다루고 싶은 주제들

• 각 정렬의 간단한 구현
• 각 정렬의 시간 복잡도와 그 이유 (특히 셸정렬, 퀵정렬)

참고서적

Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)