โปรแกรม C++ สำหรับ QuickSort

Quicksort เป็นเทคนิคการเรียงลำดับที่ใช้การเปรียบเทียบเพื่อเรียงลำดับรายการ (array) ที่ยังไม่เรียงลำดับ Quicksort ยังรู้จักในชื่อ Partition Exchange Sort

มันไม่ใช่ stable sort เนื่องจากลำดับสัมพัทธ์ของรายการที่มีค่าเท่ากันไม่ได้ถูกเก็บรักษาไว้ Quicksort สามารถทำงานบนอาร์เรย์ได้ โดยต้องการหน่วยความจำเพิ่มเติมเพียงเล็กน้อยในการเรียงลำดับ มันคล้ายกับ Selection Sort มาก แต่ไม่ได้เลือก worst-case partition ทุกครั้ง ดังนั้นจึงสามารถมองว่าเป็นรูปแบบที่ดีกว่าของ Selection Sort

QuickSort เป็นหนึ่งในอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพมากที่สุด และอิงตามการแบ่งอาร์เรย์ออกเป็นส่วนย่อยๆ ชื่อมาจากข้อเท็จจริงที่ว่า quicksort สามารถเรียงลำดับรายการข้อมูลได้เร็วกว่าอัลกอริทึมการเรียงทั่วไปอย่างมีนัยสำคัญ และเช่นเดียวกับ Merge sort, Quick sort ก็อยู่ในหมวดหมู่ Divide and Conquer (แบ่งแยกและเอาชนะ) ของวิธีแก้ปัญหา

วิธีการทำงานของ Quicksort

• มองในมุมมองแบบเปรียบเทียบ พิจารณาสถานการณ์ที่ต้องเรียงกระดาษที่มีชื่อนักเรียน ตามชื่อ อาจใช้วิธีดังนี้ −

  • เลือกค่าแบ่ง (splitting value) เช่น L ค่าแบ่งนี้เรียกว่า Pivot (พิวท)

  • แบ่งกองกระดาษเป็นสองกอง A-L และ M-Z ไม่จำเป็นต้องมีขนาดเท่ากัน

  • ทำซ้ำสองขั้นตอนข้างต้นกับกอง A-L แบ่งเป็นสองครึ่งที่สำคัญ และกอง M-Z แบ่งเป็นครึ่งเช่นกัน กระบวนการทำซ้ำจนกว่ากองจะเล็กพอที่จะเรียงง่าย

  • สุดท้าย กองเล็กๆ สามารถวางซ้อนกันเพื่อสร้างชุดที่เรียงลำดับและมีระเบียบสมบูรณ์

• วิธีการที่ใช้คือ recursion (การเรียกซ้ำ) ในแต่ละการแบ่งเพื่อไปสู่อาร์เรย์ที่มีองค์ประกอบเดียว

• ในแต่ละการแบ่ง กองจะถูกแบ่ง และใช้วิธีการเดียวกันกับกองย่อย

• เนื่องจากคุณสมบัติเหล่านี้ quicksort จึงเรียกอีกอย่างว่า Partition Exchange Sort

Input: arr[] = {7,4,2,6,3,1,5} Output: 1 2 3 4 5 6 7

คำอธิบาย

ตัวอย่างอาจช่วยให้เข้าใจแนวคิดได้ พิจารณาอาร์เรย์ต่อไปนี้: 50, 23, 9, 18, 61, 32

ขั้นตอน 1− เลือกค่าใดค่าหนึ่งเป็น pivot จากรายการ (โดยทั่วไปค่าสุดท้าย) สมมติสำหรับค่าสองค่า "Low" และ "High" ที่สอดคล้องกับดัชนีแรกและดัชนีสุดท้าย

ในกรณีของเรา low คือ 0 และ high คือ 5

ค่าที่ low และ high คือ 50 และ 32 และค่า pivot คือ 32

ดังนั้น เรียกฟังก์ชัน partition เพื่อจัดเรียงอาร์เรย์ใหม่ ให้ pivot (32) อยู่ในตำแหน่งจริงของมัน และทางซ้ายของ pivot อาร์เรย์มีองค์ประกอบทั้งหมดน้อยกว่ามัน และทางขวา มากกว่ามัน

ในฟังก์ชัน partition เริ่มจากองค์ประกอบแรกและเปรียบเทียบกับ pivot เนื่องจาก 50 มากกว่า 32 จึงไม่เปลี่ยนแปลงและไปยังองค์ประกอบถัดไป 23

เปรียบเทียบอีกครั้งกับ pivot เนื่องจาก 23 น้อยกว่า 32 จึงสลับ 50 และ 23 อาร์เรย์กลายเป็น 23, 50, 9, 18, 61, 32

ไปยังองค์ประกอบถัดไป 9 ซึ่งน้อยกว่า pivot (32) อีกครั้ง การสลับกับ 50 ทำให้อาร์เรย์เป็น 23, 9, 50, 18, 61, 32

เช่นเดียวกัน สำหรับองค์ประกอบถัดไป 18 ซึ่งน้อยกว่า 32 อาร์เรย์กลายเป็น 23, 9, 18, 50, 61, 32 ตอนนี้ 61 มากกว่า pivot (32) จึงไม่มีการเปลี่ยนแปลง

สุดท้าย สลับ pivot กับ 50 เพื่อให้มันอยู่ในตำแหน่งที่ถูกต้อง

ดังนั้น pivot (32) อยู่ในตำแหน่งจริง และองค์ประกอบทั้งหมดทางซ้ายมีค่าน้อยกว่า และทางขวามากกว่าตัวมันเอง

ขั้นตอน 2− ดังนั้น อาร์เรย์หลังขั้นตอนแรกกลายเป็น 23, 9, 18, 32, 61, 50 โดยใช้ 32 เป็น pivot

ขั้นตอน 3− ตอนนี้รายการแบ่งเป็นสองส่วน:

1. Sublist ก่อน pivot: 23, 9, 18

2. Sublist หลัง pivot: 61, 50

ขั้นตอน 4− ทำซ้ำขั้นตอนสำหรับ sublists อีกครั้ง

อาร์เรย์สุดท้ายจึงกลายเป็น 9, 18, 23, 32, 50, 61

ตัวอย่างโค้ด C

#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;
}