[Urutkan-Urutkan Cepat]

2024-07-12

Penyortiran Cepat adalah algoritma pengurutan yang efisien berdasarkan strategi bagi dan taklukkan. Ide inti dari algoritma pengurutan ini adalah untuk memilih elemen benchmark, membagi array menjadi dua bagian, sehingga elemen di sebelah kiri lebih kecil atau sama dengan elemen benchmark, dan elemen di sebelah kanan lebih besar dari atau sama dengan elemen benchmark, dan kemudian menerapkan pengurutan cepat secara rekursif ke dua bagian.

Langkah-langkah algoritma:

Pilih elemen dasar : Pilih elemen dari array sebagai pivot. Biasanya elemen pertama, elemen terakhir, atau elemen acak dipilih sebagai basis.
Partisi : Menyusun ulang array sehingga elemen yang lebih kecil dari elemen dasar berada di sisi kiri elemen dasar, dan elemen yang lebih besar dari elemen dasar berada di sisi kanan. Pada saat yang sama, elemen dasar berada pada posisi pengurutan akhir.
penyortiran rekursif: Mengurutkan subarray di sisi kiri dan kanan elemen referensi dengan cepat secara rekursif.

Langkah-langkah implementasi:

Berikut kode untuk mengimplementasikan quick sort dalam bahasa C:

#include <stdio.h>

// 函数：交换数组中两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 函数：将数组分区，并返回基准元素的位置（索引）
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);
    }
}

// 函数：打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
}

// 主函数：测试快速排序的实现
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: n");
    printArray(arr, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Analisis kode:

fungsi pertukaran: Digunakan untuk menukar nilai dua elemen dalam sebuah array.
fungsi partisi: Pilih elemen terakhir dalam array sebagai basis, bagi array menjadi dua bagian, dan kembalikan indeks posisi akhir elemen dasar.
fungsi penyortiran cepat : Algoritma rekursif untuk mengimplementasikan penyortiran cepat. Dalam setiap rekursi, fungsi partisi pertama-tama digunakan untuk mempartisi array, dan kemudian dua bagian yang dipartisi diurutkan secara rekursif.
fungsi printArray: Digunakan untuk mencetak elemen array agar mudah melihat hasil pengurutan.
fungsi utama: Uji implementasi pengurutan cepat dan cetak array sebelum dan sesudah pengurutan.

kompleksitas waktu:

Kompleksitas waktu pengurutan cepat terutama bergantung pada kompleksitas waktu operasi partisi dan jumlah panggilan rekursif. Kompleksitas waktu quicksort adalah O(n^2) pada kasus terburuk, namun O(n log n) pada kasus rata-rata, menjadikannya algoritma pengurutan yang efisien.

Meringkaskan:

Penyortiran cepat mencapai penyortiran yang efisien melalui strategi bagi-dan-taklukkan dan operasi partisi. Ini tidak memerlukan ruang penyimpanan tambahan (kecuali ruang tumpukan untuk panggilan rekursif) dan memiliki kinerja yang baik dalam keadaan rata-rata. Oleh karena itu, pengurutan cepat adalah salah satu algoritma pengurutan yang umum digunakan dalam aplikasi praktis, terutama cocok untuk tugas pengurutan kumpulan data besar.

Berbagi teknologi