정렬 알고리즘

• 요소들을 순서대로 재배열하는 알고리즘
• 자료 탐색에 있어서 필수적인 알고리즘

정렬 알고리즘 시간복잡도

• 삽입 / 셀 : 키 값을 비교해서 자료를 삽입
• 선택 / 힙 : 특정 자료구조를 통해 정렬
• 교환 / 퀵 : 키 값을 비교해서 교환
• 병합 : 키 값을 비교하고 자료를 병합
• 분배 : 키 값을 여러 개의 부분 집합으로 분배 후 정렬

• In-place Sorting : 주어진 입력 배열 이외의 추가적인 메모리를 요구하지 않는 정렬
  • 선택 정렬, 삽입정렬, 버블정렬

1) 삽입 정렬 Insertion

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 제자리 정렬 (in-place sorting) 알고리즘
• 시간 복잡도
  • Best : O(N) - 리스트가 거의 정렬된 상태
  • Worst : O($N^2$)

셸 정렬 Shell

• 삽입 정렬을 보완한 알고리즘
• 정렬해야 할 리스트의 각 K번째 요소를 추출해 부분 리스트를 만들고, 각 회전마다 간격을 줄여가면서 정렬

2) 선택 정렬 Selection

• 제일 큰 것 혹은 제일 작은 것부터 제자리에 보내는 정렬
• 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 2번째 데이터와 바꾸는 과정을 반복
• 시간복잡도 : O($N^2$)

3) 버블 정렬 Bubble

• 앞에서부터 인접한 두 원소를 보면서 앞의 원소가 뒤의 원소보다 클 경우 자리를 바꾸는 것을 반복
• 시간복잡도 : O($N^2$)

4) 병합 정렬 Merge

• 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법
  1. 데이터를 분할 (Divide)
  2. 비교해서 정렬 (Conquer)
  3. 데이터 합치기 (Merge)
• 시간 복잡도 : O(NlogN)
  • 병합이 일어나는 총 Depth는 log N, 각 Depth 별 병합은 O(N)
• 추가적인 공간이 O(N) 필요하고, Stable Sort 임

5) Quick Sort

• 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘
  • 장점 : 추가적인 공간이 필요하지 않다는 점 / 평균적으로 merge 보다 빠름
  • 단점 : Stable sort 아님
• 시간 복잡도
  • Best : O(logN)
  • Avg : O(NlogN)
  • Worst : O($N^2$)

Quick Sort 동작 방식

1. 정렬 시 제자리로 보낼 pivot을 정합니다.(맨 앞에 있는 값을 pivot이라 가정)
2. pivot을 제외하고 left, right라고 이름 붙은 포인터 2개를 둡니다.
3. left는 pivot보다 큰 값이 나올 때 까지 오른쪽으로 이동하고 right는 pivot보다 작거나 같은 값이 나올 때 까지 왼쪽으로 이동합니다.
4. 그 다음 두 포인터가 가리키는 원소의 값을 스왑합니다.
5. 이걸 left와 right가 교차할 때 까지 반복하면 됩니다.
6. right가 left보다 작아진 순간이 오면 pivot과 right을 스왑

Quick Sort 더 나은 피벗 고르기

• 퀵 소트 성능 향상 시키는 방법 중 하나

• Quicksort는 일반적으로 파티션의 가장 왼쪽 또는 가장 오른쪽 요소를 피벗 요소로 선택

  -> 정렬되거나 거의 정렬된 입력에서 최악의 경우 O(N^2) 동작을 야기함

1. Randomized Quicksort: 피벗에 대해 임의의 인덱스 사용하기
2. median-of-3: 피벗 파티션의 첫 번째, 중간 및 마지막 요소의 중앙값을 선택하여 피벗으로 사용

6) 계수 정렬 Counting

• 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘
• 가장 큰 데이터와 가장 작은 데이터의 차이가 백만을 넘지 않을 때 효과적으로 사용 가능
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능
• 시간 복잡도 : 최악의 경우에도 O(N+K)
  • 데이터 개수 N, 데이터 중 최댓값 K

예상 질문

• Quick Sort 시간복잡도, 그 외 특징 설명해보세요
• Merge Sort 시간복잡도, 그 외 특징 설명해보세요
• 이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 Sort 기법은 무엇인가요?
• 선택/버블정렬의 경우 어떤 경우든 시간복잡도가 O(N^2)인데 왜 사용하는 걸까요?

• QuickSort의 성능을 향상시키기 위한 기법에는 어떤 게 있나요?

• 퀵 소트가 더 빠른 이유

  CPU의 cache hit 비율이 높기 때문에 지역성 참고 면에서 더 빠르다.

• 정렬의 평가 방법, swap 횟수