Quicksort เป็นเทคนิคการจัดเรียงที่ใช้การเปรียบเทียบเพื่อจัดเรียงรายการที่ไม่เรียงลำดับ ( array ) Quicksort เรียกอีกอย่างว่าการเรียงลำดับการแลกเปลี่ยนพาร์ติชั่น
ไม่ใช่การเรียงลำดับที่เสถียร เนื่องจากลำดับสัมพัทธ์ของรายการเรียงลำดับที่เท่ากันจะไม่ถูกรักษาไว้ Quicksort สามารถทำงานบนอาร์เรย์ ซึ่งต้องใช้หน่วยความจำเพิ่มเติมเล็กน้อยในการเรียงลำดับ มันคล้ายกับการเรียงลำดับการเลือกมาก ยกเว้นว่ามันไม่ได้เลือกพาร์ติชั่นตัวพิมพ์ที่แย่ที่สุดเสมอ ดังนั้นเราจึงสามารถจัดรูปแบบการเลือกได้ดีกว่า
QuickSort เป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพมากที่สุด และอิงจากการแยกอาร์เรย์ออกเป็นอันที่เล็กกว่า ชื่อนี้มาจากข้อเท็จจริงที่ว่า Quicksort สามารถเรียงลำดับรายการองค์ประกอบข้อมูลได้เร็วกว่าอัลกอริธึมการเรียงลำดับทั่วไปอย่างมีนัยสำคัญ และเช่นเดียวกับการจัดเรียงแบบผสาน การเรียงลำดับแบบด่วนยังอยู่ในหมวดหมู่ของวิธีการแบ่งและพิชิตของวิธีการแก้ปัญหา
อัลกอริธึม Quicksort ทำงานดังต่อไปนี้
-
พิจารณาสถานการณ์ที่ต้องจัดเรียงเอกสารที่มีชื่อนักเรียนตามชื่อ อาจใช้วิธีดังนี้ −
-
เลือกค่าการแยก พูด L ค่าการแยกเรียกอีกอย่างว่า Pivot
-
แบ่งกองกระดาษออกเป็นสองส่วน A-L และ M-Z ไม่จำเป็นต้องมีกองเท่ากัน
-
ทำซ้ำสองขั้นตอนข้างต้นด้วยกอง AL โดยแบ่งเป็นสองส่วนที่สำคัญ และกอง M-Z แบ่งออกเป็นสองส่วน ทำซ้ำจนกองมีขนาดเล็กพอที่จะจัดเรียงได้ง่าย
-
ในที่สุด กองขนาดเล็กสามารถวางกองหนึ่งทับอีกกองหนึ่งเพื่อผลิตชุดกระดาษที่จัดเรียงและจัดเรียงอย่างครบถ้วน
-
-
วิธีการที่ใช้ในที่นี้คือ การเรียกซ้ำ ในแต่ละแยกเพื่อไปยังอาร์เรย์องค์ประกอบเดียว
-
ทุกๆ รอยแยก กองจะถูกแบ่งและจากนั้นก็ใช้วิธีเดียวกันกับกองที่เล็กกว่า
-
เนื่องจากคุณลักษณะเหล่านี้ Quicksort จึงเรียกว่า การจัดเรียงการแลกเปลี่ยนพาร์ติชัน .
Input: arr[] = {7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7 คำอธิบาย
ตัวอย่างอาจมีประโยชน์ในการทำความเข้าใจแนวคิด พิจารณาอาร์เรย์ต่อไปนี้:50, 23, 9, 18, 61, 32
ขั้นตอนที่ 1 - ตัดสินใจว่าค่าใด ๆ จะเป็นเดือยจากรายการ (โดยทั่วไปจะเป็นค่าสุดท้าย) สมมติให้ค่าสองค่า “ต่ำ” และ “สูง” ตรงกับดัชนีแรกและดัชนีสุดท้าย
ในกรณีของเราต่ำคือ 0 และสูงคือ 5
ค่าที่ต่ำและสูงคือ 50 และ 32 และค่าของเดือยคือ 32
ดังนั้น เรียกการแบ่งพาร์ติชัน จัดเรียงอาร์เรย์ใหม่ในลักษณะที่เดือย (32) มาถึงตำแหน่งจริง และทางด้านซ้ายของเดือย อาร์เรย์มีองค์ประกอบทั้งหมดน้อยกว่านั้น และทางขวามากกว่านั้น
ในฟังก์ชันพาร์ติชั่น เราเริ่มจากองค์ประกอบแรกและเปรียบเทียบกับเดือย เนื่องจาก 50 มากกว่า 32 เราจึงไม่ทำการเปลี่ยนแปลงใดๆ และไปยังองค์ประกอบถัดไปที่ 23
เปรียบเทียบอีกครั้งกับเดือย เนื่องจาก 23 น้อยกว่า 32 เราจึงสลับ 50 และ 23 อาร์เรย์กลายเป็น 23, 50, 9, 18, 61, 32
เราไปยังองค์ประกอบถัดไป 9 ซึ่งน้อยกว่าเดือย (32) อีกครั้ง ดังนั้นการสลับกับ 50 ทำให้อาร์เรย์ของเราเป็น
23, 9, 50, 18, 61, 32.
ในทำนองเดียวกันสำหรับองค์ประกอบถัดไป 18 ซึ่งน้อยกว่า 32 อาร์เรย์จะกลายเป็น
23, 9, 18, 50, 61, 32 ตอนนี้ 61 มีค่ามากกว่าจุดหมุน (32) ดังนั้นจึงไม่มีการเปลี่ยนแปลง
สุดท้ายนี้ เราสลับเดือยเป็น 50 เพื่อให้อยู่ในตำแหน่งที่ถูกต้อง
ดังนั้นเดือย (32) จะอยู่ที่ตำแหน่งจริงและองค์ประกอบทั้งหมดทางด้านซ้ายจะน้อยกว่า และองค์ประกอบทั้งหมดทางด้านขวาจะมีค่ามากกว่าตัวมันเอง
ขั้นตอนที่ 2 − ดังนั้นอาร์เรย์หลังจากขั้นตอนแรกจะกลายเป็น
23, 9, 18, 32, 61, 50 ใช้ 32 เป็นเดือย
ขั้นตอนที่ 3 − ตอนนี้รายการถูกแบ่งออกเป็นสองส่วน:
1. Sublist ก่อน pivot: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;
} 