Mestimissortimine

Allikas: Vikipeedia
Jump to navigation Jump to search
Mestimissortimist demonstreeriv animatsioon

Mestimissortimine (inglise keeles merge sort) ehk ühildusmeetodil sortimine on sortimisalgoritm, mille leiutas 1945. aastal John von Neumann.[1][2] See oli üks esimesi sorteerimisalgoritme. Sellise sorteerimise halvim, parim ja keskmine keerukus on [3].

Mestimissortimine kasutab ära asjaolu, et kahe sorditud loendi ühendamine üheks sorditud loendiks on lihtne (lineaarse keerukusega). Algoritm jagab loendi kaheks ligikaudu võrdse suurusega loendiks, mis sorditakse omakorda mestimissortimisega, seejärel ühendatakse saadud sorditud loendid.

Algoritm[muuda | muuda lähteteksti]

Ühildusmeetod on rekursiivne algoritm, mis esmalt poolitab järjendi kaheks võrdseks osaks. Kui järjend on tühi või seal on ainult üks element, siis loetakse see sorteeritud järjendiks (tegemist on rekursiooni baasiga). Kui järjendis on rohkem kui üks element, siis jaotatakse järjend taas kaheks osaks ja rekursiivselt kasutatakse ühildussorteerimise meetodit mõlemal saadud järjendil. Kui mõlemad pooled on sorteeritud, siis need ühildatakse.[3] Ühildamine tähendab kahe või enama sorteeritud järjendi kombineerimist üheks sorteeritud järjendiks. Lihtsaim viis ühe sorteeritud järjendi saavutamiseks on võrrelda ühildatavate järjendite esimesi ehk väiksemaid elemente ning väljastada neist vähim ning jätkata seda protsessi tulemuse saavutamiseni.[1] Ühildamisel tegeletakse alati kolme järjendiga, neist kaks on sorteeritud järjendid, mis tuleb tulemuseni jõudmiseks ühildada, ning kolmas on tulemusjärjend[4].
Koodi kujul näeb see välja järgmiselt[4]:

Mergesort(A[1, n]) 
    Merge(MergeSort(A[1, n/2 ]), MergeSort(A[ n/2 + 1, n]))

Ning ühildusmeetodil sorteerimise pseudokood on järgnev[4]:

mergesort(item_type s[], int low, int high) { 
    int middle; 			/* index of middle element */ 
    if (low < high) { 
        middle = (low+high)/2;
        mergesort(s,low,middle); 
        mergesort(s,middle+1,high); 
        merge(s, low, middle, high); 
    } 
}

merge(item_type s[], int low, int middle, int high) { 
    int i;                        /* counter */ 
    queue buffer1, buffer2;       /* buffers to hold elements for merging */ 

    init_queue(&buffer1); 
    init_queue(&buffer2); 

    for (i=low; i<=middle; i++) enqueue(&buffer1,s[i]); 
    for (i=middle+1; i<=high; i++) enqueue(&buffer2,s[i]);

    i = low; 
    while (!(empty_queue(&buffer1) || empty_queue(&buffer2))) 	{
        if (headq(&buffer1) <= headq(&buffer2))
            s[i++] = dequeue(&buffer1);
        else 
            s[i++] = dequeue(&buffer2);
    } 

    while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1);
    while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2); 
}

Analüüs[muuda | muuda lähteteksti]

Et analüüsida ühildusmeetodi kiirust, tuleb arvesse võtta nii järjendi poolitamise kui ka ühildamise protsessi. Esiteks jagatakse järjendit rekursiivselt pooleks, selle protsessi kiirus on , kus on elementide arv antud järjendis. Seejärel tuleb sorteeritud järjendid ühildada. Iga järjendi element pannakse lõplikus järjendis õigele kohale, seega liikme läbi vaatamine nõuab operatsiooni. Ühildusmeetodil sorteerimine on seega keerukusega algoritm.[3]
On oluline tähele panna, et järjendite poolitamise järel on vaja mäluruumi, et saadud järjendeid meeles hoida. Kuna järjendid, mida sorteerida on vaja, võivad olla suured, siis võib poolitatud järjendite hoidmiseks vajaminev vaba mälu maht olla piiratud. See teeb ühildusmeetodi kasutamise suurte andmehulkade peal problemaatiliseks.[3]

Viited[muuda | muuda lähteteksti]

  1. 1,0 1,1 Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0.
  2. Merge Sort – Wolfram MathWorld
  3. 3,0 3,1 3,2 3,3 Miller, Brad and Ranum, David (2005). „Problem Solving with Algorithms and Data Structures using Python“
  4. 4,0 4,1 4,2 Skiena, Steven S. (2008). "4.5: Mergesort: Sorting by Divide-and-Conquer". The Algorithm Design Manual (2nd ed.). Springer. pp. 120–125. ISBN 978-1-84800-069-8.