퀵정렬
찰스 앤터니 리처드 호어가 1959년에 개발한 알고리즘이다.
퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다.
컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다.
C, C++, PHP, 자바 등 거의 모든 언어에서 제공하는 정렬 함수에서 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다.
방식은 적절한 원소 하나를 기준(피봇, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 피봇을 옮겨 피봇보다 작은 것,
큰 것으로 나눈뒤 나누어진 각각에서 다시 피봇을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
이렇게 피봇을 잡고 이보다 작은 원소들을 왼쪽으로, 보다 큰 원소들을 오른쪽으로 나누는걸 partition step이라 한다.
퀵 정렬에도 이 partition step을 어떻게 하느냐에 따라 바리에이션이 매우 많으며, 성능 차이도 날 수 있다.
https://youtu.be/ywWBy6J5gz8
퀵 정렬의 시간복잡도
최악의 경우에는 시간복잡도가 가 되는데, 피봇을 최솟값이나 최댓값으로 계속해서 잡게 되는 경우에 그렇다.
대표적인 예로는 피봇을 항상 배열의 첫 원소로 잡도록 구현한 알고리즘으로 이미 정렬된 배열을 정렬할 경우.
힙정렬이나 병합정렬은 이런 경우가 없지만, 데이터가 극단적이면 구현된 퀵정렬은 안 쓰느니만 못한 최악의 결과가 나온다.
이를 방지하기 위하여 여러 기법들이 개발 되었는데, 대표적인 것이 피봇을 랜덤으로 잡는 것(Random Quick sort).
또는, 무조건 배열의 위치상 중간에 있는걸 피봇으로 잡거나, 배열 중에 3개나 9개의 원소를 골라서 중앙값을 피봇으로 고르는 것이다.
이 방법을 사용하더라도 최악의 경우가 나올 수는 있지만 그 경우가 극히 드물게 된다.
다만 배열이 단순하게 비교 가능한 숫자가 아니라면 중앙값 피봇 방법이 비효율적일 수도 있다.
예를 들어서 비교하는데 연산이 아주 많이 들어가는 객체 또는 데이터 베이스의 경우.
그냥 무작위 또는 중간에 있는 원소를 피봇으로 잡는게 낫다(Random Quick sort).
피봇을 랜덤으로 정한다고 해도 정렬 시간이로 나쁜 경우가 나올 수 있다.
그래서 이런 나쁜 케이스들을 완전히 없애고 싶다면 순수 퀵 소트 보다는,
특수한 상황이 나왔을때 다른 빠른 정렬 알고리즘을 섞어서 쓰는 하이브리드 퀵 소트가 좋다.
그래서 재귀 깊이가 어느 제한 이상으로 깊어질 경우 힙 정렬 알고리즘을 사용하여.
항상 을 보장해주는 방법도 많이 쓰인다. (인트로 정렬)
퀵정렬 알고리즘 파이썬 구현(코드)
def quick_sorted(arr):
if len(arr) > 1:
pivot = arr[len(arr)-1]
left, mid, right = [], [], []
for i in range(len(arr)-1):
if arr[i] < pivot:
left.append(arr[i])
elif arr[i] > pivot:
right.append(arr[i])
else:
mid.append(arr[i])
mid.append(pivot)
print(arr)
return quick_sorted(left) + mid + quick_sorted(right)
else:
return arr
arr = [5,3,8,4,9,1,6,2,7]
print(quick_sorted(arr))결과는?
퀵 정렬 알고리즘 예제
(출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html)
피봇 값을 입력 리스트의 첫 번째 데이터로 하자. (다른 임의의 값 이어도 상관없다.)
2개의 인덱스 변수(low, high)를 이용해서 리스트를 두 개의 부분 리스트로 나눈다.
1 싸이클
피봇이 5인 경우,
low는 왼쪽에서 오른쪽으로 탐색해가다가 피봇보다 큰 데이터(8)을 찾으면 멈춘다.
high는 오른쪽에서 왼쪽으로 탐색해가다가 피봇보다 작은 데이터(2)를 찾으면 멈춘다.
low와 high가 가리키는 두 데이터를 서로 교환한다.
이 탐색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.
2 싸이클
피봇(1회전의 왼쪽 부분리스트의 첫 번째 데이터)이 1인 경우,
위와 동일한 방법으로 반복한다.
3 싸이클
피봇(1 싸이클의 오른쪽 부분리스트의 첫 번째 데이터)이 9인 경우,
위와 동일한 방법으로 반복한다.
C코드로 구현하면.
# include <stdio.h>
# define MAX_SIZE 9
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
// 1. 피벗을 기준으로 2개의 부분 리스트로 나눈다.
// 2. 피벗보다 작은 값은 모두 왼쪽 부분 리스트로, 큰 값은 오른쪽 부분 리스트로 옮긴다.
/* 2개의 비균등 배열 list[left...pivot-1]와 list[pivot+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
int partition(int list[], int left, int right){
int pivot, temp;
int low, high;
low = left;
high = right + 1;
pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택(임의의 값을 피벗으로 선택)
/* low와 high가 교차할 때까지 반복(low<high) */
do{
/* list[low]가 피벗보다 작으면 계속 low를 증가 */
do {
low++; // low는 left+1 에서 시작
} while (low<=right && list[low]<pivot);
/* list[high]가 피벗보다 크면 계속 high를 감소 */
do {
high--; //high는 right 에서 시작
} while (high>=left && list[high]>pivot);
// 만약 low와 high가 교차하지 않았으면 list[low]를 list[high] 교환
if(low<high){
SWAP(list[low], list[high], temp);
}
} while (low<high);
// low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]를 교환
SWAP(list[left], list[high], temp);
// 피벗의 위치인 high를 반환
return high;
}
// 퀵 정렬
void quick_sort(int list[], int left, int right){
/* 정렬할 범위가 2개 이상의 데이터이면(리스트의 크기가 0이나 1이 아니면) */
if(left<right){
// partition 함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 -분할(Divide)
int q = partition(list, left, right); // q: 피벗의 위치
// 피벗은 제외한 2개의 부분 리스트를 대상으로 순환 호출
quick_sort(list, left, q-1); // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 -정복(Conquer)
quick_sort(list, q+1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 -정복(Conquer)
}
}
void main(){
int i;
int n = MAX_SIZE;
int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
// 퀵 정렬 수행(left: 배열의 시작 = 0, right: 배열의 끝 = 8)
quick_sort(list, 0, n-1);
// 정렬 결과 출력
for(i=0; i<n; i++){
printf("%d\n", list[i]);
}
}퀵 정렬 C 코드
#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];
void quickSort(int i, int j)
{
if(i>=j) return;
int pivot = quick[(i+j)/2];
int left = i;
int right = j;
while(left<=right)
{
while(quick[left]<pivot) left++;
while(quick[right]>pivot) right--;
if(left<=right)
{
swap(quick[left],quick[right]);
left++; right--;
}
}
quickSort(i,right);
quickSort(left,j);
}
int main()
{
printf("총 숫자 입력\n");{
scanf("%d",&n);
for(int i = 0; i < n; i++){
printf("값입력 ex 4,2,3,1\n");
scanf("%d",&quick[i]);
}
}
quickSort(0,n-1);
printf("결과 출력\n");
for(int j = 0; j < n; j++) {
printf("%d",quick[j]);
}
}오늘 한 퀵 정렬은 인 것이다.
