[알고리즘] 정렬

1. 정렬이란?

정렬(sort)은 자료를 크기 순서대로 맞춰 일렬로 나열하는 것

• 단어를 가나다순 혹은 알파벳순으로 나열한 정렬이 좋은 예
• 문제: 리스트 안에 있는 자료를 순서대로 배열하기
• 입력: 정렬할 리스트(예: [45, 8, 91, 33])
• 출력: 순서대로 정렬된 리스트(예: [8, 33, 45, 91])

정렬의 종류

• 선택 정렬
• 삽입 정렬
• 병합 정렬
• 퀵 정렬
• 거품 정렬

2. 선택 정렬

• 처리할 대상 범위에서 최솟값을 찾아 그 값과 범위의 맨 앞ㅇ 있는 값을 서로 바꾸는 과정을 반복한다. 이 과정이 한 번 끝날 때마다 범위 안의 맨 앞에 있는 값은 정렬이 끝난 것이므로 정렬 대상 범위에서 제외한다.
• 자료를 크기 순서로 정렬하려면 반드시 두 수의 크기를 비교해야 한다. 따라서 정렬 알고리즘의 계산 복잡도는 보통 비교 횟수를 기준으로 한다.
  • 비교를 총 $n(n-1) / 2$ 하는 계산 복잡도 $O(n^2)$ 알고리즘
  • 비교 횟수가 입력 크기의 제곱에 비례하는 시간 복잡도를 가진 알고리즘
  • 입력 크기가 커질수록 정렬하는 데 시간 오래 걸림

3. 삽입 정렬

• 시간 복잡도
  - 일반적으로 계산 복잡도 $O(n^2)$: 정렬할 입력 크기가 크면 정렬하는 데 시간 오래 걸림
  - 이미 정렬이 끝난 경우 (ex. [1,2,3,4,5]) 계산 복잡도 $O(n)$
  

4. 병합 병렬

• 주어진 문제를 절반으로 나눈 다음 각각을 재귀 호출로 풀어 가는 방식
• 큰 문제를 작은 문제로 나눠서(분할하여) 푸는(정복하는) 방법을 분할 정복이라 함
• 입력 크기가 커서 풀기 어려웠던 문제도 반복해서 잘게 나누다 보면 굉장히 쉬운 문제(종료 조건)이 되는 원리
• 시간 복잡도 $O(n*logn)$, 선택 정렬이나 삽입 정렬보다 빠른 정렬 성능

5. 퀵 정렬

• 주어진 문제를 절반으로 나눈 후 재귀호출하는 방식은 병합 정렬과 같음
• 단, 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 차이점
• 즉, 먼저 기준과 비교해서 그룹을 나눈 다음 각각 재귀 호출하여 합치는 방식
• '좋은 기준'을 정하는 것이 정렬의 효율성을 가늠하게 함
• 시간 복잡도
  - 최악의 경우 $O(n^2)$: 기준을 잘못 정한 경우
  • 일반적인 경우 $O(n*logn)$