เทคนิค Quick Sort ในภาษา C

ประเภทของการเรียงลำดับ

C มีเทคนิคเรียงลำดับ 5 แบบ:

Bubble Sort (หรือ Exchange Sort)
Selection Sort
Insertion Sort (หรือ Linear Sort)
Quick Sort (หรือ Partition Exchange Sort)
Merge Sort (หรือ External Sort)

Quick Sort

เป็นอัลกอริทึมแบ่งและเอาชนะ (Divide and Conquer)

เลือกองค์ประกอบหนึ่งเป็น pivot
แบ่งอาร์เรย์ไม่เรียงเป็นสองอาร์เรย์
ค่าน้อยกว่า pivot อยู่ซ้าย ค่ามากกว่า pivot อยู่ขวา

ตัวอย่าง: องค์ประกอบ 6, 3, 7, 2, 4, 5 (รูปภาพขั้นตอนไม่ได้รวม)

ขั้นตอน: pivot อยู่ตำแหน่งคงที่ ด้านซ้ายน้อยกว่า ด้านขวามากกว่า แบ่งเป็นสองส่วน เรียงซ้ำในแต่ละส่วน จนได้ลำดับ 2, 3, 4, 5, 6, 7

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

#include <stdio.h>

void quicksort(int number[25], int first, int last) {
    int i, j, pivot, temp;
    if(first < last) {
        pivot = first;
        i = first;
        j = last;
        while(i < j) {
            while(number[i] <= number[pivot] && i < last)
                i++;
            while(number[j] > number[pivot])
                j--;
            if(i < j) {
                temp = number[i];
                number[i] = number[j];
                number[j] = temp;
            }
        }
        temp = number[pivot];
        number[pivot] = number[j];
        number[j] = temp;
        quicksort(number, first, j - 1);
        quicksort(number, j + 1, last);
    }
}

int main() {
    int i, count, number[25];
    printf("How many elements are u going to enter?: ");
    scanf("%d", &count);
    printf("Enter %d elements: ", count);
    for(i = 0; i < count; i++)
        scanf("%d", &number[i]);
    quicksort(number, 0, count - 1);
    printf("Order of Sorted elements: ");
    for(i = 0; i < count; i++)
        printf(" %d", number[i]);
    return 0;
}

ผลลัพธ์

How many elements are u going to enter?: 10
Enter 10 elements: 2 3 5 7 1 9 3 8 0 4
Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9