Algoritmi MergeSort në C dhe Java

Informatec Digital » Algoritmet » Algoritmi MergeSort në C dhe Java

Renditja e të dhënave është një detyrë themelore në programim dhe analizë algoritmesh. Ka shumë teknika të renditjes në dispozicion, dhe një nga më efikaset është algoritmi MergeSort. Ky algoritëm përdor një qasje "përça dhe sundo" për të renditur një listë të elementeve në mënyrë rekursive.

Në këtë artikull, do të përqendrohemi në zbatimin e algoritmit MergeSort në gjuhët e programimit C dhe Java. Do të shqyrtojmë hap pas hapi se si funksionon ky algoritëm dhe si mund ta përdorni në projektet tuaja. Gjithashtu do të diskutojmë kompleksitetin kohor të MergeSort dhe do të krahasojmë performancën e tij me algoritme të tjera të renditjes.

Algoritmi MergeSort në C dhe Java

Algoritmi MergeSort përdor një strategji përçaj-dhe-sundo për të renditur një listë artikujsh. Procesi kryhet në tre faza kryesore: përçaj, sundo dhe bashko. Le të shohim se si ta zbatojmë këtë algoritëm në gjuhët e programimit C dhe Java.

Zbatimi MergeSort në C

Këtu është një zbatim i algoritmit MergeSort në 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;
}

Në këtë zbatim, së pari përcaktojmë një funksion merge e cila është përgjegjëse për kombinimin e dy nënvargjeve të renditura në një grup kryesor. Pastaj funksioni mergeSort në mënyrë rekursive e ndan grupin në nënvargje më të vogla dhe i rendit ato duke përdorur funksionin merge. Së fundi, në funksion main, ne krijojmë një grup testimi, ne thërrasim mergeSort dhe ne shfaqim rregullimin e renditur në ekran.

Zbatimi i MergeSort në Java

Tani, le të shohim se si të zbatojmë algoritmin MergeSort në 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 + " ");
        }
    }
}

Në këtë zbatim të MergeSort në Java, ne përdorim metoda statike për funksionin merge y mergeSort. funksion merge kryen të njëjtën detyrë si në zbatimin C, dhe funksionin mergeSort ndjek të njëjtën logjikë të ndarjes dhe kombinimit të nëngrupeve. Në funksion main, ne krijojmë një grup testimi, ne thërrasim mergeSort dhe ne shfaqim grupin e renditur në tastierë.

Sa është kompleksiteti kohor i algoritmit MergeSort?

Kompleksiteti kohor i algoritmit MergeSort është O(n log n), ku “n” përfaqëson numrin e elementeve në grup që do të renditet. Kjo do të thotë se koha e funksionimit të algoritmit rritet proporcionalisht me produktin e "n" dhe logaritmin bazë 2 të "n". Ky kompleksitet e bën MergeSort një nga algoritmet më efikase të renditjes në dispozicion.

Krahasimi i MergeSort me algoritme të tjera të renditjes

MergeSort shquhet për efikasitetin e tij në renditjen e të dhënave. Krahasuar me algoritme të tjera të njohura si Renditja me Bubble ose Renditja e Përzgjedhjes, MergeSort ka një kompleksitet më të mirë kohor. Ndërsa Renditja Bubble dhe Renditja e Përzgjedhjes kanë një kompleksitet kohor prej O(n^2), MergeSort ka një kompleksitet kohor prej O(n log n). Kjo do të thotë që MergeSort është në gjendje të trajtojë vëllime të mëdha të të dhënave në mënyrë më efikase dhe më të shpejtë se këto algoritme më pak efikase.

Pyetje të shpeshta

1: Pse të përdorni MergeSort në vend të algoritmeve të tjera të renditjes?

MergeSort preferohet mbi algoritmet e tjera të renditjes për shkak të efikasitetit dhe performancës së tij. Me një kompleksitet kohor prej O(n log n), MergeSort është në gjendje të renditë grupe të mëdha të dhënash më shpejt dhe më me efikasitet sesa algoritmet me kompleksitet kuadratik, si Renditja me flluska ose Renditja e përzgjedhjes. Për më tepër, MergeSort është një algoritëm i qëndrueshëm, që do të thotë se ruan rendin relativ të elementeve me vlera të barabarta, të cilat mund të jenë të rëndësishme në kontekste të caktuara.

2: Kur duhet të përdor MergeSort në projektet e mia?

Ju mund të konsideroni përdorimin e MergeSort kur keni nevojë të renditni grupe të mëdha të dhënash në mënyrë efikase. Nëse keni një listë të pa renditur artikujsh dhe dëshironi të merrni një listë të renditur në kohën më të shkurtër të mundshme, MergeSort është një opsion i shkëlqyeshëm. Megjithatë, vini re se MergeSort mund të kërkojë më shumë hapësirë ​​​​memorie në krahasim me algoritmet e tjera të renditjes, sepse krijon nëngarkesa shtesë gjatë ekzekutimit të tij.

3: A ka ndonjë disavantazh në përdorimin e MergeSort?

Një disavantazh i mundshëm i MergeSort është përdorimi i tij shtesë i memories. Gjatë ekzekutimit të algoritmit, krijohen nëngarkesa shtesë për të ndarë dhe kombinuar të dhënat, të cilat mund të rrisin kërkesat për memorie, veçanërisht kur punoni me grupe të dhënash shumë të mëdha. Megjithatë, në shumicën e rasteve, ky disavantazh është i parëndësishëm në krahasim me efikasitetin e algoritmit.

4: A mund të trajtojë MergeSort elemente të kopjuara në grup?

Po, MergeSort mund të trajtojë elemente të kopjuara në grup. Algoritmi është i qëndrueshëm, që do të thotë se ruan rendin relativ të elementeve me vlera të barabarta. Kjo është e rëndësishme kur dëshironi të ruani rendin origjinal të artikujve në rast se ka dublikatë. MergeSort siguron që elementët dublikatë të shfaqen në të njëjtin rend relativ si në grupin hyrës ashtu edhe në grupin e renditur.

5: A ka ndonjë variant ose përmirësim në algoritmin MergeSort?

Po, ka disa variante dhe përmirësime në algoritmin MergeSort. Disa nga këto variante përfshijnë MergeSort përsëritëse, MergeSort me optimizime të bashkimit të nëngrupeve dhe MergeSort hibrid që kombinon MergeSort me një algoritëm tjetër renditjeje, si p.sh. Insertion Sort, për të arritur performancë më të mirë në raste të caktuara. Këto variante kërkojnë të përmirësojnë performancën dhe efikasitetin e algoritmit MergeSort në situata specifike.

6: Ku mund të mësoj më shumë rreth MergeSort dhe algoritme të tjera të renditjes?

Nëse dëshironi të mësoni më shumë rreth MergeSort dhe algoritme të tjera të renditjes, mund të shikoni burimet e mëposhtme:

• Wikipedia – Merge Sort
• GeeksforGeeks – Merge Sort

Përfundim

Në këtë artikull, ne kemi eksploruar algoritmin MergeSort në gjuhët e programimit C dhe Java. Ne kemi mësuar se si të zbatojmë këtë algoritëm efikas të renditjes së të dhënave dhe kemi diskutuar kompleksitetin e tij kohor. Nëpërmjet shembujve dhe shpjegimeve të detajuara, tani keni një kuptim të fortë se si funksionon MergeSort në C dhe Java dhe si mund ta zbatoni atë në projektet tuaja.

MergeSort është një mjet i fuqishëm për renditjen e grupeve të mëdha të të dhënave dhe kompleksiteti i tij kohor prej O(n log n) e bën atë një opsion tërheqës në krahasim me algoritmet e tjera më pak efikase të renditjes. Nëse keni nevojë të renditni të dhënat në mënyrë efikase dhe të shpejtë, merrni parasysh përdorimin e MergeSort si algoritmin tuaj të zgjedhur.

Eksploroni dhe eksperimentoni me MergeSort në projektet tuaja për të korrur përfitimet e tij dhe për të shijuar performancën optimale të renditjes së të dhënave!