퀵 정렬(Quick Sort)



퀵정렬? 

퀵 정렬은 빠른 속도와, 간단한 구현방법 때문에

가장 많이 사용하는 정렬 방법으로 알려져 있습니다.


구현방법이 간편하다고 하지만, 개인적으로 이해하는데 시간이 좀 걸렸습니다.


퀵 정렬은 피벗으로 왼쪽에는 작은 값 오른쪽에는 큰값으로 정렬하는 방법입니다.


피벗?

특정 기준은 피벗(pivot)이라고 부릅니다.


복잡도

최악의 경우의 복잡도는 아래와 같지만 

(최악의 경우 : 피벗이 가장 작은 수 이거나 가장 큰 수가 계속 선정되는 경우)



평균적인 복잡도는 아래와 같습니다.



어떠한 방법?

피벗을 가장 마지막 인덱스로 설정했습니다.


아래와 같은 배열이 있을 때 



피벗 6을 기준으로 왼쪽과 오른쪽 끝에서부터


왼쪽은 6보다 큰 수 오른쪽은 6보다 작은 수를 찾습니다.



양쪽 다 찾은 수가 있다면 자리를 교환 해줍니다.



교환 후 계속해서 진행 한 후 


왼쪽과 오른쪽의 수가 같아 지면 종료하고 


피벗과 만난지점의 자리를 바꿔줍니다.



자리를 바꾼뒤 확인 해보면


피벗 기준으로 왼쪽에는 작은 수 오른쪽에는 큰수만 오게 됩니다.



각각 나눠진 영역에서 반복해서 같은 방법으로 진행 하면 정렬이 됩니다.


반복은 재귀호출로 진행하게 됩니다.


배열과 재귀호출을 이용한 퀵 정렬 예제


퀵 정렬 함수


if문 : 재귀 호출을 통해 종료를 위한 조건문


첫번째 while : 피벗보다 작은 수 큰 수를 찾기위한 반복문


두번째, 세번째 while : 각각 피벗보다 작은 수, 큰수를 찾는 반복문


첫번째 재귀 호출 : 피벗 기준 왼쪽을 정렬하기 위한 재귀 호출


두번째 재귀 호출 : 피벗 기준 오른쪽을 정렬하기 위한 재귀 호출


void quick_sort(int array[], int size){
int pivot, temp;
if(size>1){
pivot = array[size-1];
int left = -1;
int right = size-1;
while(1){
while(array[++left]<pivot);
while(array[--right]>pivot);
if(left>=right) break;
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
temp = array[left];
array[left] = array[size-1];
array[size-1] = temp;
quick_sort(array, left);
quick_sort(array+left+1, size-left-1);
}
}


배열 출력 함수


void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


실행 함수


정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.


void main(){
int array[] = {2,7,1,3,4,0,8,5,9,6};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
quick_sort(array, size);
printf("########### Sorting after ###########\n");
print_array(array, size);
}


실행 결과



참고 : C로 배우는 알고리즘 (이재규)

위키백과(퀵 정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20
[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19

+ Recent posts

티스토리툴바