Giải thích thuật toán sắp xếp nhanh (quick sort) trong C

Sắp xếp là sắp xếp phần tử tăng/giảm dần.

Loại sắp xếp

C cung cấp 5 kỹ thuật:

• Nổi bọt
• Chọn
• Chèn
• Nhanh (Quick/Partition exchange)
• Trộn (Merge/External)

Quick Sort

Thuật toán chia để trị.

• Bước 1 - Chọn phần tử pivot.
• Bước 2 - Chia mảng thành hai mảng con.
• Bước 3 - Giá trị < pivot -> mảng con 1, > pivot -> mảng con 2.

Ví dụ: 6, 3, 7, 2, 4, 5. P=pivot, L=trái, R=phải.

Pivot cố định, trái nhỏ hơn, phải lớn hơn. Chia 2 partition, đệ quy.

Kết quả: 2, 3, 4, 5, 6, 7

Ví dụ

Chương trình C quick sort:

#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("Nhap so phan tu: "); 
    scanf("%d", &count); 
    printf("Nhap %d phan tu: ", count); 
    for(i = 0; i < count; i++) scanf("%d", &number[i]); 
    quicksort(number, 0, count - 1); 
    printf("Thu tu sap xep: "); 
    for(i = 0; i < count; i++) printf(" %d", number[i]); 
    return 0; 
}

Đầu ra

Kết quả chạy chương trình:

Nhap so phan tu: 10 
Nhap 10 phan tu: 2 3 5 7 1 9 3 8 0 4 
Thu tu sap xep: 0 1 2 3 3 4 5 7 8 9