퀵소트 기술은 목록을 두 부분으로 분리하여 수행됩니다. 처음에는 분할 알고리즘에 의해 피벗 요소가 선택됩니다. 피벗의 왼쪽 부분은 피벗보다 작은 값을 보유하고 오른쪽 부분은 더 큰 값을 보유합니다. 분할 후 동일한 절차를 사용하여 각각의 개별 목록이 분할됩니다.
퀵소트 기법의 복잡성
- 시간 복잡도:최상의 경우와 평균적인 경우는 O(n log n), 최악의 경우는 O(n^2)입니다.
- 공간 복잡도:O(log n)
입력 및 출력
Input: The unsorted list: 90 45 22 11 22 50 Output: Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90
알고리즘
파티션(배열, 하위, 상위)
입력: 데이터 세트 배열, 하한 및 상한
출력: 올바른 위치에서 회전
Begin pivot := array[lower] start := lower and end := upper while start < end do while array[start] <= pivot AND start < end do start := start +1 done while array[end] > pivot do end := end – 1 done if start < end then swap array[start] with array[end] done array[lower] := array[end] array[end] := pivot return end End
quickSort(배열, 왼쪽, 오른쪽
입력 - 데이터 배열, 배열의 하한 및 상한
출력 - 정렬된 배열
Begin if lower < right then q = partition(arraym left, right) quickSort(array, left, q-1) quickSort(array, q+1, right) End
예
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int *array, int lower, int upper) {
//Hoare partitioning technique to find correct location for pivot
int pivot, start, end;
pivot = array[lower]; //first element as pivot
start = lower; end = upper;
while(start < end) {
while(array[start] <= pivot && start<end) {
start++; //start pointer moves to right
}
while(array[end] > pivot) {
end--; //end pointer moves to left
}
if(start < end) {
swap(array[start], array[end]); //swap smaller and bigger element
}
}
array[lower] = array[end];
array[end] = pivot;
return end;
}
void quickSort(int *array, int left, int right) {
int q;
if(left < right) {
q = partition(array, left, right);
quickSort(array, left, q-1); //sort left sub-array
quickSort(array, q+1, right); //sort right sub-array
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
quickSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
} 출력
Enter the number of elements: 6 Enter elements: 90 45 22 11 22 50 Array before Sorting: 90 45 22 11 22 50 Array after Sorting: 11 22 22 45 50 90