Quick Sort (การจัดเรียงแบบควิก)

Quick Sort เป็นอัลกอริทึมจัดเรียงแบบ Divide and Conquer ที่ได้รับความนิยมมากที่สุดในทางปฏิบัติ เนื่องจากเร็วที่สุดในเฉลี่ย (Cache-friendly, In-place)

ความซับซ้อน (Complexity)

กรณี	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²) - เมื่อ Pivot ต่างเป็นค่าสูงสุด/ต่ำสุดเสมอ

Space Complexity: O(log n) (Stack สำหรับ Recursion)

แนวคิดการทำงาน

Partition: เลือก Pivot, จัดข้อมูล: น้อยกว่า Pivot ซ้าย, มากกว่า Pivot ขวา
Pivot อยู่ในตำแหน่งสุดท้ายที่ถูกต้อง
เรียก Quick Sort เรียกซ้ำ (Recursive) ด้านซ้ายและขวาของ Pivot
Base case: Sub-array ขนาด 0 หรือ 1

Partition Schemes

Scheme	Pivot Selection	คุณสมบัติ
Hoare (Original)	First element	Swaps น้อยกว่า, ซับซ้อนกว่า
Lomuto	Last element	เข้าใจง่าย, Swaps มากกว่า
Median-of-Three	Median of first, mid, last	หลีกเลี่ยง Worst case บนข้อมูลเรียงแล้ว
Randomized	Random element	Expected O(n log n) เสมอ

ตัวอย่างข้อมูล

Input:  90 45 22 11 22 50
Output: 11 22 22 45 50 90

อัลกอริทึม (Pseudocode - Hoare Partition)

partition(array, low, high)
  pivot = array[low]
  i = low, j = high
  while i < j:
    while array[i] <= pivot AND i < j: i++
    while array[j] > pivot: j--
    if i < j: swap(array[i], array[j])
  array[low] = array[j]
  array[j] = pivot
  return j

quickSort(array, low, high)
  if low < high:
    p = partition(array, low, high)
    quickSort(array, low, p-1)
    quickSort(array, p+1, high)

ตัวอย่างโค้ด C++ (Hoare Partition)

#include <iostream>
#include <algorithm>
using namespace std;

int partition(int *array, int low, int high) {
    int pivot = array[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && array[i] <= pivot) i++;
        while (array[j] > pivot) j--;
        if (i < j) swap(array[i], array[j]);
    }
    swap(array[low], array[j]);
    return j;
}

void quickSort(int *array, int low, int high) {
    if (low < high) {
        int p = partition(array, low, high);
        quickSort(array, low, p-1);
        quickSort(array, p+1, high);
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    quickSort(arr, 0, n-1);
    cout << "After: "; display(arr, n);
}

การปรับปรุงประสิทธิภาพ (Optimizations)

Randomized Pivot: สุ่ม Pivot ป้องกัน Worst case
Median-of-Three: เลือก Median ของ First, Mid, Last
Insertion Sort for small arrays: สลับไป Insertion Sort เมื่อ n < 10-20
Tail Recursion Elimination: เรียก Recursive ด้านเล็กก่อน แล้ว Loop ด้านใหญ่
3-way Partition (Dutch National Flag): จัดการ Duplicate keys ดีขึ้น

คุณสมบัติ

In-place: O(log n) stack space
Not Stable: การสลับข้าม Pivot เปลี่ยนลำดับค่าเท่ากัน
Cache-friendly: Sequential memory access