MergeSort algoritmas C ir Java

Informatec Digital » Algoritmai » MergeSort algoritmas C ir Java

Duomenų rūšiavimas yra pagrindinė programavimo ir algoritmų analizės užduotis. Yra daug rūšiavimo būdų, o vienas iš efektyviausių yra MergeSort algoritmas. Šis algoritmas naudoja „skaldyk ir valdyk“ metodą elementų sąrašui rekursyviai rūšiuoti.

Šiame straipsnyje daugiausia dėmesio skirsime „ MergeSort“ algoritmo įdiegimui C ir Java programavimo kalbomis. Žingsnis po žingsnio išnagrinėsime, kaip šis algoritmas veikia ir kaip galite jį naudoti savo projektuose. Taip pat aptarsime „MergeSort“ laiko sudėtingumą ir palyginsime jo našumą su kitais rūšiavimo algoritmais.

MergeSort algoritmas C ir Java

„ MergeSort “ algoritmas naudoja „skaldyk ir valdyk“ strategiją elementų sąrašui rūšiuoti. Procesas atliekamas trimis pagrindiniais etapais: skaidymas, valdymas ir sujungimas. Pažiūrėkime, kaip šį algoritmą įdiegti C ir Java programavimo kalbomis.

MergeSort diegimas C

Čia yra MergeSort algoritmo įgyvendinimas 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;
}

Šiame įgyvendinime pirmiausia apibrėžiame funkciją merge kuri yra atsakinga už dviejų sutvarkytų pogrupių sujungimą į pagrindinį masyvą. Tada funkcija mergeSort rekursyviai padalija masyvą į mažesnius pogrupius ir surūšiuoja juos naudodama funkciją merge. Galiausiai, funkcijoje main, sukuriame bandomąjį masyvą, iškviečiame mergeSort ir ekrane rodome užsakytą išdėstymą.

MergeSort diegimas Java

Dabar pažiūrėkime, kaip įdiegti MergeSort algoritmą 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 + " ");
        }
    }
}

Šiame „MergeSort“ įdiegime „Java“ funkcijai naudojame statinius metodus merge y mergeSort. Funkcija merge atlieka tą pačią užduotį kaip ir C įgyvendinime, ir funkciją mergeSort vadovaujasi ta pačia pogrupių skaidymo ir jungimo logika. Funkcijoje main, sukuriame bandomąjį masyvą, iškviečiame mergeSort ir konsolėje rodome surūšiuotą masyvą.

Koks yra MergeSort algoritmo laiko sudėtingumas?

MergeSort algoritmo sudėtingumas laike yra O(n log n), kur "n" reiškia elementų skaičių masyve, kurį reikia rūšiuoti. Tai reiškia, kad algoritmo veikimo laikas didėja proporcingai "n" sandaugai ir "n" 2 baziniam logaritmui. Dėl šio sudėtingumo MergeSort yra vienas iš efektyviausių rūšiavimo algoritmų.

MergeSort palyginimas su kitais rūšiavimo algoritmais

MergeSort išsiskiria efektyvumu rūšiuojant duomenis. Palyginti su kitais populiariais algoritmais, pvz., Bubble Sort arba Selection Sort, MergeSort laiko sudėtingumas yra daug geresnis. Nors burbulų rūšiavimo ir pasirinkimo rūšiavimo sudėtingumas yra O(n^2), o MergeSort laiko sudėtingumas yra O(n log n). Tai reiškia, kad MergeSort gali tvarkyti didelius duomenų kiekius efektyviau ir greičiau nei šie mažiau veiksmingi algoritmai.

Dažniausiai užduodami klausimai

1: Kodėl verta naudoti MergeSort, o ne kitus rūšiavimo algoritmus?

Dėl savo efektyvumo ir našumo „MergeSort“ teikiama pirmenybė, palyginti su kitais rūšiavimo algoritmais. Laiko sudėtingumas O(n log n), MergeSort gali rūšiuoti didelius duomenų rinkinius greičiau ir efektyviau nei algoritmai su kvadratiniu sudėtingumu, pvz., burbulų rūšiavimas arba pasirinkimo rūšiavimas. Be to, MergeSort yra stabilus algoritmas, tai reiškia, kad jis palaiko santykinę vienodų reikšmių elementų tvarką, kuri gali būti svarbi tam tikruose kontekstuose.

2: Kada savo projektuose turėčiau naudoti MergeSort?

Galite apsvarstyti galimybę naudoti MergeSort, kai reikia efektyviai rūšiuoti didelius duomenų rinkinius. Jei turite nesutvarkytą prekių sąrašą ir norite gauti surūšiuotą sąrašą per trumpiausią įmanomą laiką, MergeSort yra puiki galimybė. Tačiau atminkite, kad MergeSort gali prireikti daugiau atminties vietos, palyginti su kitais rūšiavimo algoritmais, nes vykdymo metu jis sukuria papildomų pogrupių.

3: Ar yra kokių nors trūkumų naudojant MergeSort?

Galimas MergeSort trūkumas yra papildomas atminties naudojimas. Vykdant algoritmą, duomenims skaidyti ir sujungti sukuriamos papildomos posistemės, kurios gali padidinti atminties poreikį, ypač dirbant su labai dideliais duomenų rinkiniais. Tačiau daugeliu atvejų šis trūkumas yra nereikšmingas, palyginti su algoritmo efektyvumu.

4: Ar MergeSort gali tvarkyti pasikartojančius masyvo elementus?

Taip, MergeSort gali tvarkyti pasikartojančius masyvo elementus. Algoritmas yra stabilus, tai reiškia, kad jis palaiko santykinę elementų, turinčių vienodas reikšmes, tvarką. Tai svarbu, kai norite išsaugoti pradinę prekių tvarką, jei yra dublikatų. MergeSort užtikrina, kad pasikartojantys elementai būtų rodomi ta pačia santykine tvarka tiek įvesties masyve, tiek surūšiuotame masyve.

5: Ar yra kokių nors MergeSort algoritmo variantų ar patobulinimų?

Taip, yra keletas MergeSort algoritmo variantų ir patobulinimų. Kai kurie iš šių variantų apima iteracinį MergeSort, MergeSort su pogrupių sujungimo optimizavimu ir hibridinį MergeSort, kuris sujungia MergeSort su kitu rūšiavimo algoritmu, pvz., įterpimo rūšiavimu, kad tam tikrais atvejais būtų pasiektas geresnis našumas. Šiais variantais siekiama pagerinti MergeSort algoritmo veikimą ir efektyvumą konkrečiose situacijose.

6: Kur galiu sužinoti daugiau apie MergeSort ir kitus rūšiavimo algoritmus?

Jei norite sužinoti daugiau apie MergeSort ir kitus rūšiavimo algoritmus, galite peržiūrėti šiuos išteklius:

• Vikipedija – Sujungti rūšiavimą
• GeeksforGeeks – sujungimo rūšiavimas

Išvada

Šiame straipsnyje mes ištyrėme MergeSort algoritmą C ir Java programavimo kalbomis. Sužinojome, kaip įdiegti šį efektyvų duomenų rūšiavimo algoritmą ir aptarėme jo laiko sudėtingumą. Remdamiesi išsamiais pavyzdžiais ir paaiškinimais, dabar puikiai suprantate, kaip MergeSort veikia C ir Java ir kaip galite jį pritaikyti savo projektuose.

MergeSort yra galingas įrankis dideliems duomenų rinkiniams rūšiuoti, o dėl O(n log n) laiko sudėtingumo jis yra patrauklus pasirinkimas, palyginti su kitais mažiau efektyviais rūšiavimo algoritmais. Jei reikia efektyviai ir greitai rūšiuoti duomenis, apsvarstykite galimybę naudoti MergeSort kaip pasirinktą algoritmą.

Išbandykite ir eksperimentuokite su MergeSort savo projektuose, kad gautumėte jos privalumų ir mėgaukitės optimaliu duomenų rūšiavimo našumu!