Quicksort

แบ่งและพิชิต

ขั้นตอนการแบ่งส่วน

รูปแบบการแบ่งส่วนแบบ Lomuto

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    int p = partition(a, 0, 4);
    printf("pivot index = %d\n", p);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

การเรียงลำดับแบบเรียกซ้ำ

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
    return i + 1;
}

void quicksort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quicksort(a, lo, p - 1);
        quicksort(a, p + 1, hi);
    }
}

int main(void) {
    int a[] = {9, 3, 7, 1, 8, 2, 5};
    quicksort(a, 0, 6);
    for (int i = 0; i < 7; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

การเลือกจุดหมุนที่ดี

ค่ามัธยฐานจากสามตัว

#include <stdio.h>

int median_of_three(int a[], int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
    if (a[hi] < a[lo])  { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
    if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
    return mid;
}

int main(void) {
    int a[] = {7, 1, 5, 3, 9};
    int m = median_of_three(a, 0, 4);
    printf("median value = %d\n", a[m]);
    return 0;
}

การวิเคราะห์กรณีเลวร้ายที่สุด

จุดหมุนแบบสุ่ม

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    int lo = 0, hi = 4;
    srand(42);
    int r = lo + rand() % (hi - lo + 1);
    int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
    printf("chosen pivot = %d\n", a[hi]);
    return 0;
}

ทำงานในตำแหน่งเดิมและไม่คงเสถียร

การปรับปรุงการเรียกส่วนท้าย

การเรียงลำดับสตริง

#include <stdio.h>

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
    int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
    if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}

int main(void) {
    int a[] = {42, -7, 0, 100, 13, 13};
    quicksort(a, 0, 5);
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

ตรวจสอบความเข้าใจ

สรุปทบทวน