MergeSorti algoritm C-s ja Javas

Informatec Digital » Algoritmid » MergeSorti algoritm C-s ja Javas

Andmete sorteerimine on programmeerimise ja algoritmide analüüsimise põhiülesanne. Saadaval on palju sortimistehnikaid ja üks tõhusamaid on MergeSorti algoritm. See algoritm kasutab elementide loendi rekursiivseks sortimiseks "jaga ja valluta" lähenemisviisi.

Selles artiklis keskendume MergeSorti algoritmi rakendamisele C ja Java programmeerimiskeeltes. Uurime samm-sammult, kuidas see algoritm töötab ja kuidas saate seda oma projektides kasutada. Samuti arutame MergeSorti ajakulu ja võrdleme selle jõudlust teiste sortimisalgoritmidega.

MergeSorti algoritm C-s ja Javas

MergeSort algoritm kasutab üksuste loendi sortimiseks jaga-ja-valitse strateegiat. Protsess toimub kolmes põhietapis: jaga, valluta ja ühenda. Vaatame, kuidas seda algoritmi C- ja Java-programmeerimiskeeles rakendada.

MergeSorti juurutamine C-s

Siin on MergeSorti algoritmi rakendamine C-s:

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

Selles teostuses määratleme kõigepealt funktsiooni merge mis vastutab kahe järjestatud alammassiivi ühendamise eest põhimassiiviks. Siis funktsioon mergeSort jagab massiivi rekursiivselt väiksemateks alammassiivideks ja sorteerib need funktsiooni abil merge. Lõpuks funktsioonis main, loome testmassiivi, kutsume mergeSort ja näitame tellitud paigutust ekraanil.

MergeSorti rakendamine Javas

Nüüd vaatame, kuidas MergeSorti algoritmi Java-s rakendada:

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

MergeSorti selles Java-rakenduses kasutame funktsiooni jaoks staatilisi meetodeid merge y mergeSort. Funktsioon merge täidab sama ülesannet nagu C-rakenduses ja funktsiooni mergeSort järgib sama alamkihtide tükeldamise ja kombineerimise loogikat. Funktsioonil main, loome testmassiivi, kutsume mergeSort ja kuvame konsoolis sorteeritud massiivi.

Milline on MergeSorti algoritmi ajaline keerukus?

MergeSort algoritmi ajaline keerukus on O(n log n), kus “n” tähistab sortitava massiivi elementide arvu. See tähendab, et algoritmi tööaeg pikeneb proportsionaalselt "n" ja "n" 2. baasi logaritmi korrutisega. See keerukus muudab MergeSorti üheks kõige tõhusamaks saadaolevaks sortimisalgoritmiks.

MergeSorti võrdlus teiste sortimisalgoritmidega

MergeSort paistab silma oma tõhususe poolest andmete sortimisel. Võrreldes teiste populaarsete algoritmidega, nagu mullsorteerimine või valikusorteerimine, on MergeSort palju keerulisem ajaliselt. Kui mullsortimise ja valikusortimise ajaline keerukus on O(n^2), siis MergeSorti ajaline keerukus on O(n log n). See tähendab, et MergeSort suudab käsitleda suuri andmemahtusid tõhusamalt ja kiiremini kui need vähem tõhusad algoritmid.

Preguntas frecuentes

1: Miks kasutada MergeSorti muude sortimisalgoritmide asemel?

MergeSorti eelistatakse selle tõhususe ja jõudluse tõttu teistele sortimisalgoritmidele. Ajalise keerukusega O(n log n) suudab MergeSort sorteerida suuri andmekogumeid kiiremini ja tõhusamalt kui ruutkeskmise keerukusega algoritmid, näiteks mullsortimine või valikusorteerimine. Lisaks on MergeSort stabiilne algoritm, mis tähendab, et see säilitab võrdsete väärtustega elementide suhtelise järjekorra, mis võib teatud kontekstides olla oluline.

2: Millal peaksin oma projektides kasutama MergeSorti?

Kui teil on vaja suuri andmekogumeid tõhusalt sortida, võite kaaluda MergeSorti kasutamist. Kui teil on järjestamata üksuste loend ja soovite saada sorteeritud loendi võimalikult lühikese aja jooksul, on MergeSort suurepärane võimalus. Pange tähele, et MergeSort võib teiste sortimisalgoritmidega võrreldes nõuda rohkem mäluruumi, kuna see loob täitmise ajal täiendavaid alamkihte.

3: Kas MergeSorti kasutamisel on puudusi?

MergeSorti võimalik puudus on selle täiendav mälukasutus. Algoritmi täitmise käigus luuakse andmete jagamiseks ja kombineerimiseks täiendavad alamkiibid, mis võib suurendada mäluvajadust, eriti kui töötate väga suurte andmehulkidega. Kuid enamikul juhtudel on see puudus algoritmi efektiivsusega võrreldes tähtsusetu.

4. Kas MergeSort saab käsitleda massiivi dubleerivaid elemente?

Jah, MergeSort saab käsitleda massiivi dubleerivaid elemente. Algoritm on stabiilne, mis tähendab, et see säilitab võrdsete väärtustega elementide suhtelise järjekorra. See on oluline, kui soovite duplikaate korral säilitada üksuste algse järjestuse. MergeSort tagab, et duplikaatelemendid ilmuvad nii sisendmassiivis kui ka sorteeritud massiivis samas suhtelises järjekorras.

5. Kas MergeSorti algoritmis on mingeid variante või täiustusi?

Jah, MergeSorti algoritmil on mitu varianti ja täiustusi. Mõned neist variantidest hõlmavad iteratiivset MergeSortit, MergeSortit koos alamribade ühendamise optimeerimisega ja hübriidset MergeSortit, mis kombineerib MergeSorti teise sortimisalgoritmiga, näiteks sisestussortimisega, et saavutada teatud juhtudel parem jõudlus. Nende variantide eesmärk on parandada MergeSorti algoritmi jõudlust ja tõhusust konkreetsetes olukordades.

6. Kust ma saan MergeSorti ja muude sortimisalgoritmide kohta lisateavet?

Kui soovite MergeSorti ja muude sortimisalgoritmide kohta lisateavet, vaadake järgmisi ressursse.

• Wikipedia – ühendamise sortimine
• GeeksforGeeks – ühendamise sortimine

Järeldus

Selles artiklis oleme uurinud MergeSorti algoritmi C- ja Java programmeerimiskeeltes. Oleme õppinud seda tõhusat andmesorteerimisalgoritmi rakendama ja arutanud selle ajalist keerukust. Üksikasjalike näidete ja selgituste kaudu on teil nüüd hea arusaam sellest, kuidas MergeSort töötab C- ja Java-vormingus ning kuidas saate seda oma projektides rakendada.

MergeSort on võimas tööriist suurte andmehulkade sortimiseks ja selle ajaline keerukus O(n log n) muudab selle teiste vähem tõhusate sortimisalgoritmidega võrreldes atraktiivseks. Kui teil on vaja andmeid tõhusalt ja kiiresti sorteerida, kaaluge MergeSorti kasutamist oma valitud algoritmina.

Avastage ja katsetage MergeSorti oma projektides, et saada sellest kasu ja nautida optimaalset andmete sortimise jõudlust!