Kỹ thuật quicksort được thực hiện bằng cách tách danh sách thành hai phần. Ban đầu, một phần tử xoay được chọn bằng thuật toán phân vùng. Phần bên trái của pivot giữ các giá trị nhỏ hơn pivot và phần bên phải giữ giá trị lớn hơn. Sau khi phân vùng, mỗi danh sách riêng biệt được phân vùng theo cùng một quy trình.
Sự phức tạp của Kỹ thuật Quicksort
- Độ phức tạp về thời gian:O (n log n) cho trường hợp tốt nhất và trường hợp trung bình, O (n ^ 2) cho trường hợp xấu nhất.
- Độ phức tạp của không gian:O (log n)
Đầu vào và Đầu ra
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
Thuật toán
phân vùng (mảng, dưới, trên)
Đầu vào: Mảng tập dữ liệu, ranh giới dưới và ranh giới trên
Đầu ra: Xoay đúng vị trí
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 (mảng, trái, phải
Đầu vào - Một mảng dữ liệu và giới hạn dưới và trên của mảng
Đầu ra - Mảng được sắp xếp
Begin if lower < right then q = partition(arraym left, right) quickSort(array, left, q-1) quickSort(array, q+1, right) End
Ví dụ
#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);
} Đầu ra
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