[알고리즘] 정렬 시간복잡도 비교

정렬의 정의

$n$개의 숫자를 입력받아 입력 받은
숫자들을 점점 커지는 순서나 점점 작아지는 순서로 다시 재배열하여 출력하는 것

---

 

선택정렬

• 현재 상황에서 가장 작거나 가장 큰 숫자를 선택하여 재배치하는 아이디어의 알고리즘
• 수행시간: $_{n}\mathrm{C}_{2}$ 또는 $n(n-1) \over 2$ 또는 $\sum_{i=1}^{N-1} i$
• 최악: 선택정렬의 경우에는 항상 일정하기 때문에 최악의 경우는 없다
• 최선: 선택정렬의 경우에는 항상 일정하기 때문에 최선의 경우는 없다
• 즉, 시간복잡도는 $O(n^2)$
• Not Stable 정렬임

---

 

삽입정렬

• Key 값을 정렬된 배열에 알맞은 위치에 삽입하여 정렬문제를 푸는 알고리즘

$T(n) = c_{1}n+c_{2}(n-1)+c_{3}(n-1)+ c_{4}\sum_{j=2}^n t_{j}+c_{5}\sum_{j=2}^n (t_{j}-1)+c_{6}\sum_{j=2}^n (t_{j}-1)+c_{7}(n-1)$

• 최선: 배열이 이미 정렬된 경우, $t_{j} = 1$
• 최악: 배열이 반대순서로 정렬되어 있는 경우
• 평균: 이미 정렬이 되어있는 경우는 잘 없기 때문에 결국 시간복잡도는 $O(n^2)$
• Stable 정렬임

---

 

합병정렬

• 이미 정렬된 두 개의 배열을 입력으로 받아 정렬된 하나의 배열을 출력하는 정렬 알고리즘
• 최선,최악, 평균: 모두 동일하게 $O(NlogN)$의 시간복잡도를 가진다.
• Stable 정렬임

---

 

힙정렬

• 입력받은 숫자를 힙구조로 만들어 가장 작거나 큰 값을 차례로 뽑아내어 정렬문제를 해결하는 알고리즘
• 힙에 원소를 삽입하는 수행시간 logN
• Heapify 의 수행시간: 힙의 높이가 logN이기 때문에 전체 수행시간은 $O(logN)$
• 즉, heapify 호출마다 logn, 값추출횟수는 n이므로 시간복잡도는 $O(nlogn)$이다.
• Not Stable 정렬임

 

---

 

퀵정렬

• 퀵정렬은 pivot과 partition을 이용하여 크기가 작은 숫자는 계속 앞쪽으로 이동시키고 크기가 큰 숫자는 계속 뒤쪽으로 이동시켜 정렬문제를 해결하는 알고리즘이다.
• 재귀트리로 절반씩 나눠 내려오면서 높이 logN마다 n번의 비교가 이루어져 시간복잡도는 $O(NlogN)$
• 최악의 경우는 재귀트리의 형태가 한쪽으로 치우쳐 지는 경우
  (즉, 이미 정렬되어 있는 경우와 동시에 피벗의 설정이 가장 작은값이나 큰값으로 지정되었을 경우)
• 최악의 경우를 해결하기 위해 피벗을 임의의값으로 설정하는 방법이 있다.
• Not Stable 정렬임

 

---

 

추후 추가 예정···