I-MergeSort Algorithm ku-C ne-Java

Informatec Digital » Ama-algorithms » I-MergeSort Algorithm ku-C ne-Java

Ukuhlunga idatha kuwumsebenzi obalulekile ekuhleleni nasekuhlaziyeni i-algorithm. Maningi amasu okuhlunga atholakalayo, futhi enye esebenza kahle kakhulu i-algorithm ye-MergeSort. Le algorithm isebenzisa indlela "yokuhlukanisa futhi unqobe" ukuze kuhlelwe uhlu lwama-elementi ngokuphindaphinda.

Kulesi sihloko, sizogxila ekusebenziseni i- algorithm ye-MergeSort ezilimini zokuhlela ze-C kanye ne-Java. Sizohlola isinyathelo ngesinyathelo ukuthi le algorithm isebenza kanjani nokuthi ungayisebenzisa kanjani kumaphrojekthi akho. Sizoxoxa nangokuba yinkimbinkimbi kwesikhathi se-MergeSort futhi siqhathanise ukusebenza kwayo namanye ama-algorithms okuhlunga.

I-MergeSort Algorithm ku-C ne-Java

I -algorithm ye-MergeSort isebenzisa isu lokuhlukanisa nokunqoba ukuhlunga uhlu lwezinto. Inqubo yenziwa ngezigaba ezintathu eziyinhloko: ukuhlukanisa, ukunqoba, nokuhlanganisa. Ake sibone ukuthi singayisebenzisa kanjani le algorithm ezilimini zokuhlela ze-C ne-Java.

Ukwenziwa Kwe-MergeSort ku-C

Nakhu ukuqaliswa kwe-algorithm ye-MergeSort ku-C:

#include <stdio.h>

void merge(int arr[], int left[], int right[], int left_size, int right_size) {
    int i = 0, j = 0, k = 0;
    
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    
    while (i < left_size) {
        arr[k] = left[i];
        i++;
        k++;
    }
    
    while (j < right_size) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int size) {
    if (size < 2) {
        return;
    }
    
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, right, mid, size - mid);
}

int main() {
    int arr[] = {9, 5, 2, 7, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, size);
    
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

Kulokhu kuqaliswa, siqale sichaze umsebenzi merge enesibopho sokuhlanganisa ama-subarrays amabili ahlelekile abe amalungu afanayo amakhulu. Bese umsebenzi mergeSort ngokuphindaphindiwe ihlukanisa amalungu afanayo abe ama-subarray amancane futhi awahlunge kusetshenziswa umsebenzi merge. Ekugcineni, emsebenzini main, sakha uhlu lokuhlola, siyabiza mergeSort futhi sibonisa ilungiselelo elihlungiwe esikrinini.

Isebenzisa i-MergeSort ku-Java

Manje, ake sibone ukuthi singayisebenzisa kanjani i-algorithm ye-MergeSort ku-Java:

public class MergeSort {
    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length) {
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length) {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(arr, left, right);
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3};

        mergeSort(arr);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Kulokhu kuqaliswa kwe-MergeSort ku-Java, sisebenzisa izindlela ezimile zomsebenzi merge y mergeSort. Umsebenzi merge yenza umsebenzi ofanayo njengasekuqalisweni kwe-C, kanye nomsebenzi mergeSort ilandela umqondo ofanayo wokuhlukanisa nokuhlanganisa ama-subarrays. Emcimbini main, sakha uhlu lokuhlola, siyabiza mergeSort futhi sibonisa uhlu oluhleliwe ku-console.

Iyini inkimbinkimbi yesikhathi ye-algorithm ye-MergeSort?

Isikhathi esiyinkimbinkimbi se-algorithm ye-MergeSort sithi O(n log n), lapho u-“n” emelela inani lezinto kuhlelo oluzohlungwa. Lokhu kusho ukuthi isikhathi sokusebenza se-algorithm sikhuphuka ngokulingana nomkhiqizo othi "n" kanye nesisekelo esingu-2 logarithm sokuthi "n". Le nkimbinkimbi yenza i-MergeSort ibe enye yama-algorithms okuhlunga asebenza kahle kakhulu atholakalayo.

Ukuqhathaniswa kwe-MergeSort namanye ama-algorithms okuhlunga

I-MergeSort igqama ngokusebenza kahle kwayo ekuhleleni idatha. Uma kuqhathaniswa namanye ama-algorithms adumile afana nokuhlunga kwe-Bubble noma Ukukhetha Ukukhetha, i-MergeSort inobunzima besikhathi obungcono kakhulu. Ngenkathi Ukuhlunga Kwebhamuza Nokuhlunga kunokuxaka kwesikhathi kwe-O(n^2), i-MergeSort inesikhathi esiyinkimbinkimbi se-O(n log n). Lokhu kusho ukuthi i-MergeSort iyakwazi ukuphatha amavolumu amakhulu wedatha ngempumelelo nangokushesha kunalawa ma-algorithms asebenza kancane.

Imibuzo ebuzwa njalo

1: Kungani usebenzise i-MergeSort esikhundleni sokunye ukuhlela ama-algorithms?

I-MergeSort ikhethwa ngaphezu kwamanye ama-algorithms okuhlunga ngenxa yokusebenza kahle kwayo nokusebenza kwayo. Ngenkimbinkimbi yesikhathi ye-O(n log n), i-MergeSort iyakwazi ukuhlunga amasethi amakhulu edatha ngokushesha nangokuphumelelayo kunama-algorithms anobunzima obuyi-quadratic, Njengokuhlunga Kwebhamuza noma Ukuhlunga Okukhethiwe. Ukwengeza, i-MergeSort iyi-algorithm ezinzile, okusho ukuthi igcina ukuhleleka okuhlobene kwezinto ezinamavelu alinganayo, okungaba okubalulekile kuzimo ezithile.

2: Kufanele ngisebenzise nini i-MergeSort kumaphrojekthi ami?

Ungase ucabange ukusebenzisa i-MergeSort uma udinga ukuhlela amasethi amakhulu edatha kahle. Uma unohlu lwezinto ezingahlelekile futhi ufuna ukuthola uhlu oluhleliwe ngesikhathi esifushane ngangokunokwenzeka, i-MergeSort iyindlela enhle kakhulu. Kodwa-ke, qaphela ukuthi i-MergeSort ingase idinge isikhala sememori esengeziwe uma iqhathaniswa namanye ama-algorithms okuhlunga ngoba idala ama-subarrays angeziwe ngesikhathi sokwenziwa kwayo.

3: Ingabe kukhona okungalungile ngokusebenzisa i-MergeSort?

Okungase kube kubi kwe-MergeSort ukusetshenziswa kwayo okwengeziwe kwememori. Ngesikhathi sokwenziwa kwe-algorithm, ama-subarrays engeziwe adalwe ukuze ahlukanise futhi ahlanganise idatha, engakhuphula izidingo zememori, ikakhulukazi uma isebenza ngamasethi amakhulu kakhulu wedatha. Kodwa-ke, ezimweni eziningi, lokhu kungalungile akusho lutho uma kuqhathaniswa nokusebenza kahle kwe-algorithm.

4: Ingabe i-MergeSort ingakwazi ukuphatha izici eziyimpinda ohlwini?

Yebo, i-MergeSort ingaphatha izinto eziyimpinda ohlwini. I-algorithm izinzile, okusho ukuthi igcina ukuhleleka okuhlobene kwama-elementi anamanani alinganayo. Lokhu kubalulekile uma ufuna ukulondoloza i-oda langempela lezinto uma kwenzeka kuba nezimpinda. I-MergeSort iqinisekisa ukuthi ama-elementi ayimpinda avela ngokulandelana okufanayo kukho kokubili amalungu afanayo okokufaka kanye namalungu afanayo ahlungiwe.

5: Ingabe kukhona okuhlukile noma ukuthuthukiswa kwe-algorithm ye-MergeSort?

Yebo, kukhona okuhlukile nokuthuthukiswa kwe-algorithm ye-MergeSort. Okunye kwalokhu okuhlukile kufaka phakathi i-MergeSort ephindaphindayo, i-MergeSort enokuthuthukiswa kokuhlanganisa kwe-subarray, kanye ne-hybrid MergeSort ehlanganisa i-MergeSort nenye i-algorithm yokuhlunga, efana ne-Insertion Sort, ukuze kuzuzwe ukusebenza okungcono ezimeni ezithile. Lezi zinhlobonhlobo zifuna ukuthuthukisa ukusebenza nokusebenza kahle kwe-algorithm ye-MergeSort ezimeni ezithile.

6: Ngingakufunda kuphi okwengeziwe mayelana ne-MergeSort namanye ama-algorithms okuhlunga?

Uma ufuna ukufunda kabanzi mayelana ne-MergeSort namanye ama-algorithms wokuhlela, ungabheka izinsiza ezilandelayo:

• I-Wikipedia - Hlanganisa Ukuhlunga
• I-GeeksforGeeks - Hlanganisa Ukuhlunga

Isiphetho

Kulesi sihloko, sihlole i-algorithm ye-MergeSort ngezilimi zokuhlela ze-C ne-Java. Sifunde ukuthi singayisebenzisa kanjani le-algorithm yokuhlunga idatha ephumelelayo futhi saxoxa ngobunkimbinkimbi besikhathi sayo. Ngezibonelo ezinemininingwane nezincazelo, manje usunokuqonda okuqinile kokuthi i-MergeSort isebenza kanjani ku-C ne-Java, nokuthi ungayisebenzisa kanjani kumaphrojekthi akho.

I-MergeSort iyithuluzi elinamandla lokuhlunga amasethi amakhulu edatha kanye nobunkimbinkimbi besikhathi bayo be-O(n log n) kuyenza ibe inketho ekhangayo uma iqhathaniswa namanye ama-algorithms okuhlunga angasebenzi kahle. Uma udinga ukuhlunga idatha kahle futhi ngokushesha, cabanga ukusebenzisa i-MergeSort njenge-algorithm oyikhethayo.

Hlola futhi ulinge nge-MergeSort kumaphrojekthi akho ukuze uvune izinzuzo zayo futhi ujabulele ukusebenza okuhle kokuhlela idatha!