เทคนิค Quicksort ทำได้โดยแยกรายการออกเป็นสองส่วน เริ่มแรกองค์ประกอบเดือยจะถูกเลือกโดยอัลกอริทึมการแบ่งพาร์ติชัน ส่วนด้านซ้ายของเดือยถือค่าที่น้อยกว่าเดือยและส่วนขวาถือค่าที่มากกว่า หลังจากแบ่งพาร์ติชัน แต่ละรายการแยกกันจะถูกแบ่งพาร์ติชันโดยใช้ขั้นตอนเดียวกัน
ในกรณีนี้ เรากำลังเลือกองค์ประกอบเดือยแบบสุ่ม หลังจากเลือกเดือยแล้ว เรากำลังแบ่งพาร์ติชั่น จากนั้นจัดเรียงอาร์เรย์ซ้ำๆ
ความซับซ้อนของเทคนิค Quicksort
-
ความซับซ้อนของเวลา − O(n log n) สำหรับกรณีที่ดีที่สุดและกรณีเฉลี่ย O(n 2 ) สำหรับกรณีที่เลวร้ายที่สุด
-
ความซับซ้อนของอวกาศ − O(ล็อก n)
ป้อนข้อมูล − รายการที่ไม่เรียงลำดับ:90 45 22 11 22 50
ผลผลิต − อาร์เรย์หลังการเรียงลำดับ:11 22 22 45 50 90
อัลกอริทึม
พาร์ทิชัน(อาร์เรย์, ล่าง, บน)
ป้อนข้อมูล − อาร์เรย์ชุดข้อมูล ขอบเขตล่าง และขอบเขตบน
ผลผลิต − หมุนในตำแหน่งที่ถูกต้อง
Begin index := lower pivot := higher for i in range lower to higher, do if array[i] < array[pivot], then exchange the values of array[i] and array[index] index := index + 1 done exchange the values of array[pivot] and array[index] End
random_pivot_partition(อาร์เรย์ ล่าง บน)
ป้อนข้อมูล − อาร์เรย์ชุดข้อมูล ขอบเขตล่าง และขอบเขตบน
ผลผลิต − ดัชนีสุดท้ายของเดือยที่ถูกสุ่มเลือก
Begin n := a random number pvt := lower + n mod (upper – lower + 1) exchange the values of array[pivot] and array[upper] index := Partition(array, lower, upper) return index End
quickSort(อาร์เรย์ ซ้าย ขวา)
ป้อนข้อมูล − อาร์เรย์ของข้อมูล และขอบเขตล่างและบนของอาร์เรย์
ผลผลิต − อาร์เรย์ที่จัดเรียง
Begin if lower < right then q = random_pivot_partition(array, left, right). quickSort(array, left, q-1) quickSort(array, q+1, right) End
โค้ดตัวอย่าง
#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) {
//function to shuffle the array elements into random positions
srand(time(NULL));
for (int i = MAX - 1; i > 0; i--) {
int j = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high) {
int pivot, index, i;
index = low;
pivot = high;
for(i=low; i < high; i++) {
// finding index of pivot.
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){
// Random selection of pivot.
int pvt, n, temp;
n = rand();
pvt = low + n%(high-low+1); // Randomizing the pivot value from sub-array.
swap(a[high], a[pvt]);
return Partition(a, low, high);
}
void quick_sort(int arr[], int p, int q) {
//recursively sort the list
int pindex;
if(p < q) {
pindex = RandomPivotPartition(arr, p, q); //randomly choose pivot
// Recursively implementing QuickSort.
quick_sort(arr, p, pindex-1);
quick_sort(arr, pindex+1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX; i++)
arr[i] = i + 1;
random_shuffle(arr); //To randomize the array
quick_sort(arr, 0, MAX - 1); //sort the elements of array
for (i = 0; i < MAX; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
} ผลลัพธ์
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
