Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Quicksort dalam C

Pelajari partisi array, pemilihan pivot, dan pengurutan rekursif.

Quicksort memilih pivot dan memisahkan nilai yang lebih kecil dari yang lebih besar. Setiap bagian lalu diurutkan secara rekursif. Pada partisi Lomuto dalam contoh, elemen terakhir menjadi pivot dan sebuah indeks menandai batas bagian yang sudah diproses.

Rekursi berhenti ketika rentang berisi kurang dari dua elemen. Waktu rata-rata adalah O(N log N), tetapi dapat mencapai O(N²) jika partisi sangat tidak seimbang. Perhitungkan stack pemanggilan: tidak adanya array kedua bukan berarti tanpa penggunaan memori.

Uji nilai duplikat, array yang sudah terurut, dan urutan terbalik. Periksa batas setiap pemanggilan. Implementasi ini tidak menjamin urutan awal elemen bernilai sama tetap terjaga.

Kode C

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

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);
    }
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Buka di kompiler

Keluaran yang diharapkan

Sorted array:
10 30 40 50 70 80 90

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.