สำรวจความรวดเร็วของ Quick Sort กับ C++

Quick Sort คืออะไร? หนึ่งในคำตอบหลักของการค้นหาวิธีการเรียงลำดับข้อมูลอย่างรวดเร็วในวงการคอมพิวเตอร์คือ "Quick Sort" หรือ การเรียงลำดับแบบเร็ว ซึ่งเป็น Algorithm ที่นิยมในการจัดเรียงข้อมูล ด้วยวิธีการ "แบ่งแยก" (Divide and Conquer) ทำให้มันมีความเร็วและมีประสิทธิภาพสูงในหลายๆ สถานการณ์

การทำงานของ Quick Sort:

Quick Sort เริ่มต้นด้วยการเลือก "pivot" หรือ จุดศูนย์กลาง ซึ่งจะเป็นจุดอ้างอิงในการเปรียบเทียบข้อมูล ขั้นตอนต่อไปคือการจัดเรียงข้อมูลให้แบ่งเป็นสองส่วน คือส่วนที่มีค่าน้อยกว่า pivot และส่วนที่มีค่ามากกว่า pivot หลังจากนั้น Quick Sort จะทำการเรียงลำดับแต่ละส่วนด้วยวิธีเดียวกันนี้ (เรียกว่าการ "recursive") จนกว่าข้อมูลจะถูกเรียงลำดับครบทั้งหมด

ตัวอย่าง Code ใน C++:

#include 

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void swap(int &a, int &b);

int main() {
    int data[] = {8, 7, 6, 1, 0, 9, 2};
    int n = sizeof(data)/sizeof(data[0]);

    std::cout << "Original array:\n";
    for (int h = 0; h < n; h++)
        std::cout << data[h] << " ";

    quickSort(data, 0, n - 1);

    std::cout << "\nSorted array:\n";
    for (int i = 0; i < n; i++)
        std::cout << data[i] << " ";
    return 0;
}

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Usecase ในโลกจริง:

Quick Sort มีการใช้งานในหลายโดเมน ไม่ว่าจะเป็นการจัดระเบียบฐานข้อมูล, การเรียงลำดับผลค้นหาในเว็บไซต์, การจัดส่งข้อมูลที่เรียงลำดับแล้วไปยังระบบจัดการเครือข่ายหรืออุปกรณ์ต่างๆ เช่น ในระบบขายหนังสือออนไลน์ที่ต้องจัดเรียงหนังสือตามประเภท, โดยราคา, หรือความนิยม เป็นต้น

Complexity และข้อดีข้อเสีย:

- ในกรณีที่ดีที่สุด (Best case) และกรณีเฉลี่ย (Average case): O(n log n)

- ในกรณีที่แย่ที่สุด (Worst case): O(n^2)

- มีประสิทธิภาพสูงและเร็วเมื่อเทียบกับบาง algorithm อื่นๆ เช่น Bubble Sort

- ในโปรแกรมจริงๆ สามารถทำงานได้อย่างรวดเร็วและใช้หน่วยความจำน้อยลงเมื่อเทียบกับ Merge Sort เพราะไม่ต้องจองพื้นที่พิเศษสำหรับการเรียงลำดับ

- สำหรับการเลือก pivot ที่ไม่ดีอาจทำให้ประสิทธิภาพลดลง (Worst case)

- ไม่มีความเสถียรเหมือนกับ Merge Sort (ไม่ Stable) ในกรณีเรียงข้อมูลที่มีค่าซ้ำกัน

ลงท้ายด้วยการเชิญชวนเข้าร่วมเรียนรู้ที่ EPT:

หลังจากได้ทราบถึงข้อดีและความสามารถของ Quick Sort ในการจัดการกับข้อมูลที่หลากหลายในโลกของการเขียนโปรแกรม ณ ที่นี้ เราขอเชิญชวนนักเรียนรู้ไฟแรงทุกท่าน ที่มีความสนใจและต้องการขุดลึกลงไปในโลกของการเขียนโค้ด เข้าร่วมสร้างสรรค์พื้นฐานที่แข็งแกร่งไปกับเราที่ EPT ที่นี่ไม่เพียงแค่คุณจะได้เรียนรู้ Quick Sort เท่านั้น แต่ยังรวมไปถึง Algorithm อื่นๆ ที่จะเปิดประตูสู่โอกาสใหม่ๆ ให้กับคุณ อย่ารอช้า! มาร่วมเป็นส่วนหนึ่งในสังคมของผู้เขียนโปรแกรมที่ไม่หยุดนิ่งและพร้อมก้าวหน้าไปกับเราที่ EPT วันนี้!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง