MergeSort algoritms C un Java

Informatec Digital » Algoritmi » MergeSort algoritms C un Java

Datu šķirošana ir programmēšanas un algoritmu analīzes pamatuzdevums. Ir pieejamas daudzas šķirošanas metodes, un viena no efektīvākajām ir MergeSort algoritms. Šis algoritms izmanto "skaldi un valdi" pieeju, lai rekursīvi kārtotu elementu sarakstu.

Šajā rakstā mēs pievērsīsimies MergeSort algoritma ieviešanai C un Java programmēšanas valodās. Mēs soli pa solim izpētīsim, kā šis algoritms darbojas un kā jūs to varat izmantot savos projektos. Mēs arī apspriedīsim MergeSort laika sarežģītību un salīdzināsim tā veiktspēju ar citiem kārtošanas algoritmiem.

MergeSort algoritms C un Java

MergeSort algoritms izmanto “skaldi un valdi” stratēģiju, lai kārtotu elementu sarakstu. Process tiek veikts trīs galvenajos posmos: dali, valdi un apvieno. Apskatīsim, kā ieviest šo algoritmu C un Java programmēšanas valodās.

MergeSort ieviešana C

Šeit ir MergeSort algoritma ieviešana 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;
}

Šajā īstenošanā mēs vispirms definējam funkciju merge kas ir atbildīgs par divu sakārtotu apakšmasīvu apvienošanu galvenajā masīvā. Pēc tam funkcija mergeSort rekursīvi sadala masīvu mazākos apakšblokos un sakārto tos, izmantojot funkciju merge. Visbeidzot, funkcijā main, mēs izveidojam testa masīvu, mēs izsaucam mergeSort un mēs parādām pasūtīto izkārtojumu uz ekrāna.

MergeSort ieviešana Java

Tagad apskatīsim, kā Java ieviest MergeSort algoritmu:

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

Šajā MergeSort ieviešanā Java mēs izmantojam statiskas metodes funkcijai merge y mergeSort. Funkcija merge veic to pašu uzdevumu kā C implementācijā, un funkciju mergeSort ievēro to pašu apakšgrupu sadalīšanas un apvienošanas loģiku. Pasākumā main, mēs izveidojam testa masīvu, mēs izsaucam mergeSort un mēs parādām sakārtoto masīvu konsolē.

Kāda ir MergeSort algoritma laika sarežģītība?

MergeSort algoritma laika sarežģītība ir O(n log n), kur “n” apzīmē kārtojamā masīva elementu skaitu. Tas nozīmē, ka algoritma darbības laiks palielinās proporcionāli "n" reizinājumam un "n" 2. bāzes logaritmam. Šī sarežģītība padara MergeSort par vienu no efektīvākajiem pieejamajiem šķirošanas algoritmiem.

MergeSort salīdzinājums ar citiem šķirošanas algoritmiem

MergeSort izceļas ar savu efektivitāti datu kārtošanā. Salīdzinot ar citiem populāriem algoritmiem, piemēram, Bubble Sort vai Selection Sort, MergeSort ir daudz sarežģītāka laika ziņā. Lai gan burbuļu kārtošanas un atlases kārtošanas laika sarežģītība ir O(n^2), tad MergeSort laika sarežģītība ir O(n log n). Tas nozīmē, ka MergeSort spēj apstrādāt lielus datu apjomus efektīvāk un ātrāk nekā šie mazāk efektīvie algoritmi.

Bieži uzdotie jautājumi

1: Kāpēc izmantot MergeSort, nevis citus šķirošanas algoritmus?

MergeSort ir priekšroka salīdzinājumā ar citiem šķirošanas algoritmiem, pateicoties tā efektivitātei un veiktspējai. Ar laika sarežģītību O(n log n), MergeSort spēj kārtot lielas datu kopas ātrāk un efektīvāk nekā algoritmi ar kvadrātisko sarežģītību, piemēram, burbuļu kārtošana vai atlases kārtošana. Turklāt MergeSort ir stabils algoritms, kas nozīmē, ka tas saglabā elementu relatīvo secību ar vienādām vērtībām, kas var būt svarīgi noteiktos kontekstos.

2. Kad savos projektos vajadzētu izmantot MergeSort?

Ja nepieciešams efektīvi kārtot lielas datu kopas, varat apsvērt iespēju izmantot MergeSort. Ja jums ir nesakārtots vienumu saraksts un vēlaties iegūt sakārtotu sarakstu pēc iespējas īsākā laikā, MergeSort ir lieliska iespēja. Tomēr ņemiet vērā, ka MergeSort var prasīt vairāk vietas atmiņā, salīdzinot ar citiem šķirošanas algoritmiem, jo ​​izpildes laikā tiek izveidoti papildu apakšbloki.

3: Vai MergeSort izmantošanai ir kādi trūkumi?

Iespējamais MergeSort trūkums ir tā papildu atmiņas izmantošana. Algoritma izpildes laikā tiek izveidoti papildu apakšbloki datu sadalīšanai un apvienošanai, kas var palielināt atmiņas prasības, īpaši strādājot ar ļoti lielām datu kopām. Tomēr vairumā gadījumu šis trūkums ir nenozīmīgs salīdzinājumā ar algoritma efektivitāti.

4. Vai MergeSort var apstrādāt masīva elementu dublikātus?

Jā, MergeSort var apstrādāt masīva elementu dublikātus. Algoritms ir stabils, tas nozīmē, ka tas saglabā elementu relatīvo secību ar vienādām vērtībām. Tas ir svarīgi, ja vēlaties saglabāt sākotnējo vienumu secību gadījumā, ja ir dublikāti. MergeSort nodrošina, ka elementu dublikāti parādās vienā relatīvā secībā gan ievades masīvā, gan sakārtotajā masīvā.

5. Vai ir kādi MergeSort algoritma varianti vai uzlabojumi?

Jā, MergeSort algoritmam ir vairāki varianti un uzlabojumi. Daži no šiem variantiem ietver iteratīvo MergeSort, MergeSort ar apakšgrupu sapludināšanas optimizāciju un hibrīda MergeSort, kas apvieno MergeSort ar citu šķirošanas algoritmu, piemēram, ievietošanas kārtošanu, lai sasniegtu labāku veiktspēju noteiktos gadījumos. Šo variantu mērķis ir uzlabot MergeSort algoritma veiktspēju un efektivitāti konkrētās situācijās.

6. Kur es varu uzzināt vairāk par MergeSort un citiem šķirošanas algoritmiem?

Ja vēlaties uzzināt vairāk par MergeSort un citiem šķirošanas algoritmiem, varat apskatīt šādus resursus:

• Wikipedia — sapludināšanas kārtošana
• GeeksforGeeks — sapludināšanas kārtošana

Secinājums

Šajā rakstā mēs esam izpētījuši MergeSort algoritmu C un Java programmēšanas valodās. Mēs esam iemācījušies ieviest šo efektīvo datu šķirošanas algoritmu un apsprieduši tā laika sarežģītību. Izmantojot detalizētus piemērus un skaidrojumus, jums tagad ir laba izpratne par to, kā MergeSort darbojas C un Java, un kā jūs varat to izmantot savos projektos.

MergeSort ir spēcīgs rīks lielu datu kopu šķirošanai, un tā laika sarežģītība O(n log n) padara to par pievilcīgu iespēju salīdzinājumā ar citiem mazāk efektīviem kārtošanas algoritmiem. Ja jums ir nepieciešams efektīvi un ātri kārtot datus, apsveriet iespēju izmantot MergeSort kā izvēlēto algoritmu.

Izpētiet un eksperimentējiet ar MergeSort savos projektos, lai gūtu labumu no tā un izbaudītu optimālu datu šķirošanas veiktspēju!