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

Merge sort dalam C

Bagi, urutkan, dan gabungkan array dalam O(N log N).

Merge sort membagi rentang menjadi dua hingga setiap bagian berisi satu elemen. Saat rekursi kembali, dua bagian terurut digabungkan dengan memilih elemen terkecil dari elemen depan yang belum diproses.

Setelah perulangan utama, salin sisa elemen dari salah satu bagian. Memilih elemen kiri terlebih dahulu ketika nilainya sama dapat mempertahankan stabilitas. Implementasi umum membutuhkan memori tambahan O(N) serta stack rekursi.

Uji ukuran ganjil, nilai yang sama, dan batas buffer sementara. Tanpa optimasi tambahan, waktu tetap O(N log N) meskipun masukan sudah terurut.

Kode C

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

int merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    if (L == NULL || R == NULL) {
        free(L);
        free(R);
        return 0;
    }

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
    return 1;
}

int mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        if (!mergeSort(arr, l, m) || !mergeSort(arr, m + 1, r)) return 0;
        return merge(arr, l, m, r);
    }
    return 1;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    if (!mergeSort(arr, 0, n - 1)) {
        fputs("Memory allocation failed.\n", stderr);
        return EXIT_FAILURE;
    }
    printf("MergeSorted Array:\n");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Buka di kompiler

Keluaran yang diharapkan

MergeSorted Array:
3 9 10 27 38 43 82

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.