SW 꿈나무
Quick Sort (퀵 정렬) 본문
Quick Sort (퀵 정렬)
-
분할 정복 알고리즘으로 인덱스를 분할(Devide) 후, 정복(Conquer)과 결합(Combine)하는 정렬
-
피벗을 정한 후, 피벗과의 대소비교로 좌, 우를 정렬하고 각 좌, 우 정렬에 대해서도 반복하는 정렬
-
장점 : 빠르다. 평균적으로 Merge Sort 보다 빠르다.
-
단점 : 피벗 선택에 따라 시간복잡도가 바뀔 수 있다.
같은 수를 비교할 경우, 위치 이동이 일어날 수 있다. -
시간복잡도 : Best T(n) = n log_2 n
Worst T(n) = n^2 -
동작 순서
- 피벗을 선택한다.
- 피벗과 각 인덱스 대소비교 후, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다.
- 피벗을 제 위치로 이동시킨다.
- 나눈 배열의 사이즈가 1이 될 때까지 피벗 좌, 우 측 배열에 대해 반복한다.
-
Code
#include <stdio.h> // 헤더파일 선언 #define ARRAY_SIZE 10 // ARRAY_SIZE 10으로 선언 void swap(int* a, int* b); // swap function 선언 int partition(int array[], int left, int right); // partition function 선언 void quick_sort(int array[], int left, int right); // quick_sort function 선언 // main function---------------------------------------------- void main() { int Arr[ARRAY_SIZE] = {2, 8, 9, 4, 5, 7, 1, 0, 3, 6}; // 임의의 배열 선언 및 초기화 quick_sort(Arr, 0, ARRAY_SIZE-1); // quick_sort function 호출 for(int i=0;i<ARRAY_SIZE;i++) // ARRAY_SIZE 만큼 반복 { printf("%d",Arr[i]); // Arr의 각 원소들 출력 (정렬된 배열 출력) } } void swap(int* a, int* b) // swap function (정수형 포인터, 정수형 포인터) { int temp = *a; // 정수형 변수 temp 선언 및 *a의 주소값 대입 *a = *b; // *a에 *b의 주소값 대임 *b = temp; // *b에 temp 값 대입 } void quick_sort(int array[], int left, int right) // quick_sort function. (배열, 시작 인덱스, 끝 인덱스) { if(left<right) // 시작 인덱스보다 끝 인덱스가 작으면 { int pivot = partition(array, left, right); // 정수형 변수 p 선언 및 partition 함수 호출 값 대입 if(left<pivot-1) // 시작 인덱스가 pivot-1 보다 작으면 quick_sort(array, left, pivot-1); // quick_sort 호출 (배열, 시작 인덱스, 피벗-1) if(pivot+1<right) // pivot+1 이 끝 인덱스보다 작으면 quick_sort(array, pivot+1, right); // quick_sort 호출 (배열, 피벗+1, 끝 인덱스) } } int partition(int array[], int left, int right) // partition function. (배열, 시작 인덱스, 끝 인덱스) { int pivot = array[right]; // 정수형 변수 pivot 선언 및 배열의 끝 인덱스 값 대입. // 배열의 마지막 인덱스의 값을 피벗으로 선언. //int temp; // swap 함수 대입 전 swap을 위한 임시 변수로 사용. for(int i=left; i<right; i++) // 시작 인덱스부터 끝 인덱스 수만큼 반복 { if(array\[i\]<=pivot) // i번째 인덱스의 값이 피벗 값보다 작으면 { //temp = array\[i\]; //array\[i\] = array\[left\]; //array\[left\] = temp; // swap swap(&array\[i\],&array\[left\]); // i번째 인덱스의 값과 시작 인덱스 교환 left++; // 시작 인덱스++ } // 피벗보다 작은 값을 0번째, 1번째, 2번째... 에 저장시키기 위해 left++ 사용. } //temp = array\[right\]; //array\[right\] = array\[left\]; //array\[left\] = temp; // swap swap(&array\[left\],&array\[right\]); // left 번째 인덱스 (피벗이 들어갈 위치)와 right 번째 인덱스(피벗) 교환 return (left); // left 반환 (피벗의 위치) }
Output : 0 1 2 3 4 5 6 7 8 9
'Computer Science > Algorithm' 카테고리의 다른 글
Merge Sort (합병 정렬) (0) | 2020.03.31 |
---|---|
Bubble Sort (거품 정렬) (0) | 2020.03.30 |
Insertion Sort (삽입 정렬) (0) | 2020.03.29 |
Selection Sort (선택 정렬) (0) | 2020.03.28 |
Comments