알고리즘 요약
퀵정렬 (quick sort)
- 피벗값을 중심으로 작은값 리스트와, 큰값 리스트로 계속 나누어 정렬.
- 피벗(리스트에서 기준이 되는 요소를 고르는 것)값의 선택이 성능에 큰 영향.
- 시간복잡도: O(n log n)
정렬과정 설명
① ② ③ ④ ⑤ : 위치번호
[2, 6, 3, 4, 1] :숫자열이 있을 경우,
L R : 좌측 비교시작점 L, 우측 비교시작점 R
-중앙값 ③3을 피벗으로 선택해서 피벗값(기준값)으로 정한다.
[2, 6, 3, 4, 1]
-좌측시작(L)을 우측으로 이동하며 피벗값보다 크면(6) 멈추고,
-우측시작(R)을 좌측으로 이동하며 피벗값보다 작으면(1) 멈춘다.
[2, 1, 3, 4, 6]
-L이 R보다 작다면 서로 값을 교환한다(피벗값을 중심으로 좌측 작은값, 우측 큰값 정렬이 됨).
[2, 1], [3], [4, 6]
L R L R
-피벗값 위치를 중심으로 다시 배열을 나누어 배열갯수가 한 개가 될 때까지 반복한다.
[1, 2, 3, 4, 6] # 각 부분 정렬들이 끝나면 전체 배열이 정렬된다
# 재귀함수로 작성한 예
def quick_sort(a, L, R):
left, right = L, R
pivot = a[(L + R) // 2] # 피벗값 선택(중간위치값)
while left <= right: # left가 right 보다 작으면 계속 루프
while a[left] < pivot:
left += 1 # 피벗보다 작은 값이면 계속 우로 이동
while a[right] > pivot:
right -= 1 # 피벗보다 큰 값이면 계속 좌로 이동
if left <= right : # left 가 right 보다 작으면 값을 서로 교환
a[left], a[right] = a[right], a[left]
left += 1 # left 한칸 우측 이동
right -= 1 # right 한칸 좌측 이동
if right > L: quick_sort(a, L, right) # 좌측배열 재귀호출
if left < R: quick_sort(a, left, R) # 우측배열 재귀호출
# 함수 테스트
a = [6, 2, 3, 4, 1]
quick_sort(a, 0, len(a) - 1)
print(a) # 결과는 [1, 2, 3, 4, 6]
#include <stdio.h>
void quick_sort(int a[], int L, int R) {
int left = L, right = R;
int pivot = a[(L+R) / 2]; //피벗값 설정 (중간값)
int tmp;
do {
while (a[left] < pivot) ++left; // 피벗과 같거나 큰 값 만날때 까지 우로 이동
while (a[right] > pivot) --right; //피벗과 같거나 작은 값을 만날때 까지 좌로 이동
if (left <= right) { //left가 right과 같거나 왼쪽에 있다면 값 교환
tmp = a[left]; a[left] = a[right]; a[right] = tmp; // 값교환
++left; --right; // 교환 후 1씩 이동
}
} while (left <= right); // left가 right 보다 커질때 까지 계속 루프
//재귀호출
if (right > L) quick_sort(a, L, right); //왼쪽 배열 재귀호출
if (left < R) quick_sort(a, left, R); //우측 배열 재귀호출
}
int main() {
int i, a[] = {6, 2, 3, 4, 1}, len = sizeof(a) / sizeof(a[0]);
quick_sort(a, 0, len - 1);
for (i = 0; i < len; i++) printf("%d ", a[i]); // 결과: 1 2 3 4 6
return 0;
}