퀵정렬

[알고리즘]퀵 정렬(Quick Sort)

퀵정렬이란? 퀵정렬은 이름그대로 빠른정렬, 즉 다른 정렬알고리즘에 비해 빠르다고 할 수 있습니다. 다른원소와의 비교를 통해 정렬이 이루어지므로 비교정렬에 속하고, 같은 수가 있는 경우 같은 수의 순서가 달라질 수 있어서 불안정 정렬에 속합니다. ex) 5(1), 5(2), 3, 2, 1 -> 1, 2, 3, 5(2), 51(1) 시간복잡도 최악의 경우 O(n^2) 평균 O(n log n) 알고리즘 임의의 수(pivot)를 고른다. 피벗을 기준으로 두 수를 비교하여 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다. 분할된 리스트 가운데에 피벗을 위치 시키고, 양쪽 리스트에 대해 재귀적으로 수행한다. 예제 가장 오른쪽에 있는 4를 pivot으로 정함. pivot을 제외하고..