퀵소트는 정렬되지 않은 목록(배열)을 정렬하기 위해 비교를 사용하는 정렬 기술입니다. 퀵정렬은 파티션 교환 정렬이라고도 합니다.
동일한 정렬 항목의 상대적 순서가 유지되지 않기 때문에 안정적인 정렬이 아닙니다. Quicksort는 배열에서 작동할 수 있으므로 정렬을 수행하는 데 약간의 추가 메모리가 필요합니다. 항상 최악의 경우 파티션을 선택하지 않는다는 점을 제외하면 선택 정렬과 매우 유사합니다. 따라서 선택 정렬의 더 나은 형태로 간주할 수 있습니다.
QuickSort는 가장 효율적인 정렬 알고리즘 중 하나이며 배열을 더 작은 것으로 분할하는 것을 기반으로 합니다. 이름은 퀵정렬이 일반적인 정렬 알고리즘보다 훨씬 빠르게 데이터 요소 목록을 정렬할 수 있다는 사실에서 유래했습니다. 그리고 병합 정렬과 마찬가지로 퀵 정렬도 문제 해결 방법론의 분할 정복 방식의 범주에 속합니다.
Quicksort 알고리즘은 다음과 같은 방식으로 작동합니다.
-
유추적인 관점에서 학생들의 이름이 포함된 서류를 이름별로 분류해야 하는 상황을 생각해 보십시오. 다음과 같이 접근 방식을 사용할 수 있습니다. -
-
분할 값(예:L)을 선택합니다. 분할 값은 피벗이라고도 합니다.
-
종이 더미를 둘로 나눕니다. A-L 및 M-Z. 더미가 같아야 하는 것은 아닙니다.
-
A-L 파일로 위의 두 단계를 반복하여 중요한 두 부분으로 나눕니다. 그리고 M-Z 더미는 반으로 나뉩니다. 더미가 쉽게 분류될 수 있을 만큼 작아질 때까지 이 과정을 반복합니다.
-
궁극적으로 더 작은 더미를 다른 더미 위에 올려 완전히 분류되고 정렬된 종이 세트를 만들 수 있습니다.
-
-
여기에 사용된 접근 방식은 재귀입니다. 각 분할에서 단일 요소 배열에 도달합니다.
-
분할할 때마다 더미를 나눈 다음 더 작은 더미에 대해 동일한 접근 방식을 사용했습니다.
-
이러한 기능으로 인해 퀵 정렬을 파티션 교환 정렬이라고도 합니다. .
Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 설명
예는 개념을 이해하는 데 유용할 수 있습니다. 다음 배열을 고려하십시오. 50, 23, 9, 18, 61, 32
1단계 − 목록에서 피벗이 될 값을 결정합니다(일반적으로 마지막 값). 첫 번째 인덱스와 마지막 인덱스에 해당하는 두 개의 값 "Low"와 "High"가 있다고 가정합니다.
우리의 경우 low는 0이고 high는 5입니다.
낮음과 높음의 값은 50과 32이고 피벗 값은 32입니다.
따라서 피벗(32)이 실제 위치에 오도록 배열을 재정렬하고 분할을 요청합니다. 그리고 피벗의 왼쪽에는 배열보다 작은 모든 요소가 있고 오른쪽에는 그보다 큰 요소가 있습니다.
파티션 함수에서 첫 번째 요소부터 시작하여 피벗과 비교합니다. 50은 32보다 크므로 변경하지 않고 다음 요소 23으로 이동합니다.
피벗과 다시 비교하십시오. 23은 32보다 작기 때문에 50과 23을 바꿉니다. 배열은 23, 50, 9, 18, 61, 32가 됩니다.
다시 피벗(32)보다 작은 다음 요소 9로 이동하여 50으로 바꾸면 배열이 다음과 같이 됩니다.
23, 9, 50, 18, 61, 32.
마찬가지로 32보다 작은 다음 요소 18의 경우 배열은
가 됩니다.23, 9, 18, 50, 61, 32 이제 61이 피벗(32)보다 크므로 변경 사항이 없습니다.
마지막으로 올바른 위치에 오도록 피벗을 50으로 바꿉니다.
따라서 피벗(32)은 실제 위치에 있으며 왼쪽의 모든 요소는 더 작고 오른쪽의 모든 요소는 자신보다 큽니다.
2단계 − 따라서 첫 번째 단계 이후의 배열은
23, 9, 18, 32, 61, 50, 32를 중심축으로 합니다.
3단계 − 이제 목록이 두 부분으로 나뉩니다.
1. 피벗 전의 하위 목록:23, 9, 18
2. 피벗 후 하위 목록:61, 50
4단계 − 이 하위 목록에 대해 단계를 다시 반복합니다.
따라서 최종 배열은 9, 18, 23, 32, 50, 61이 됩니다.
예시
#include <stdio.h>
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[index]);
index++;
}
}
swap(&a[pivot], &a[index]);
return index;
}
int RandomPivotPartition(int a[], int low, int high) {
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1);
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high) {
return 0;
}
int main() {
int n, i;
n=7;
int arr[]={7,4,2,6,3,1,5};
int high = n-1;
int low = 0 ;
int pindex;
if(low < high) {
pindex = RandomPivotPartition(arr, low, high);
QuickSort(arr, low, pindex-1);
QuickSort(arr, pindex+1, high);
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}