Algoritmid ja andmestruktuurid - programmeerimiskeel C/Sortimine

Sortimine

Sortimisalgoritm puhul tuleb arvestada, et:

• sorditava elementide hulk mõjutab algoritmi valikut
• minimeerida tuleb võrdluste arv (kuna need on arvutuslikult kallid)
• minimeerida tuleb väärtustamiste arv (muutub esmajärguliseks, kui tegemist on suurte struktuuridega)
• leida lahendus olukorrale, kui tuleb:
  • lisada 1 element sorditud hulka ja jääda sorditud (võimalikult vähekulukalt)
  • kustutada 1 element sorditud hulka ja jääda sorditud (võimalikult vähekulukalt)
  • tuleb sortida/seada elemendid täpselt vastupidi

Valikuga sortimine (Selection sort)

Valikuga sortimine on sortimis algoritm, täpsemalt on tegu võrdlus teel korduva minimaalse/maksimaalse elemendi sortimisega. Ta omab Θ(n²) efektiivsusfaktorit, olles nõnda ebaefektiivne suurte hulkade korral, ning üldjuhul annab tulemuslikult halvemaid või sarnaseid tulemusi, kui samalaadne vahelepanemisega sortimine. Valikuga sortimist loetakse üheks lihtsaimaks sortimsalgoritmiks, ning teatud olukordades võib ta olla efektiivseim, kui mõni keerulisem algoritm.

Algoritmi tööpõhimõte on:

1. Leia miinimum väärtus loetelust
2. Vaheta see väätusega esimesel positsioonil
3. Korda kahte esimest tegevust (võttes ületäitumisel järgmise elemendi)

Näide kuidas sortimise algoritm töötab viie elemendi korral:

31 25 12 22 11 //võrdlen 4 korda, vahetan 3 korda
11 25 12 22 31 //võrdlen 3 korda, vahetan 3 korda
11 12 25 22 31 //võrdlen 2 korda, vahetan 3 korda
11 12 22 25 31 //võrdlen 1 korra, vahetan 3 korda
//Θ(n*2)

Näide teisele poole sortimisest:

31 25 12 22 11 //võrdlen 4 korda
31 25 12 22 11 //võrdlen 3 korda
31 25 22 12 11 //võrdlen 2 korda, vahetan 3 korda
31 25 22 12 11 //võrdlen 1 korra
//Θ(n*2)

Analüüs

Valikuga sortimist pole raske analüüsida, kuna tema efektiivsus ei sõltu sorditavatest andmetest. Esimese elemendi leidmiseks tuleb uurida läbi kõik n elementi (selleks kulub n - 1 võrdlust) ja siis leitud elemendi vahetamisega elemendiga, mis asub esimesel positsioonil. Järgmise elemendi leidmiseks, tuleb läbi uurida järgi jäänud n - 1 elementi ja nõnda edasi, mis teeb kokku (n - 1) + (n - 2) + ... + 2 + 1 = Θ(n²) võrdlust. Iga võrdlemisprotseduuri lõpus toimub vahetamine, mis teeb kokku n - 1 vahetust (kuna vimane element on juba paigas).

Implementatsioon

void selection(int *array, int length){
   int max, i, temp;
   while(length > 0)
   {
     max = 0;
     for(i = 1; i < length; i++)
       if(array[i] > array[max])
         max = i;
     temp = array[length-1];
     array[length-1] = array[max];
     array[max] = temp;
     length--;
   }
}

Vahelepanemisega sortimine (Insertion sort)

NB:

Antud sortimine on mõeldud eeskätt viitavale loetelule, kus elemendi lisamiseks tuleb vahetada väiksemalt elemendilt viit endale (ja/või temale) ja luua viit suuremale/võrdsele elemendile (ja/või temalt). Lihtmassiivide puhul (kus elemendid ei viita teineteisele) tuleks iga vahelepanemisega palju elemente nihutada ja algoritm oleks tunduvalt ebaefektiivsem!

Vahelepanemisega sortimine on sortimis algoritm, täpsemalt on tegu võrdlus sortimisega, mis ehitatakse ühe sisestuse haaval. Ta omab keskmiselt Θ(n²/4) efektiivsusfaktorit, olles nõnda ebaefektiivne suurte hulkade korral, kuid omab mitmeid eeliseid:

• Lihtne implementeerida
• Efektiivne (üsna) väikeste andmehulkade puhul
• Efektiivne andmehulkade puhul mis on juba osaliselt sorditud
• Efektiivseim nn. lihtsatest Θ(n²) efektiivsusfaktorit omavatest algoritmidest
• Kindel (ei vaheta relatsioonilist järjekorda mida omavad elemendid võrdsete võtmetega)
• igale-antud-kohale tüüpi algoritm, (nõuab fikseeritud suurusega vahemäluala(buffrit) O(1))
• Online tüüpi algoritm, sortida saab siis, kui andmeid saadakse

Algoritmi tööpõhimõte on:

1. Kustuta elemendi viidad
2. Võta järgmine element
3. Kustuta järgmise elemendi viidad
4. Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele eraldatud elemendiga
5. Kustuta järgmise elemendi viidad
6. Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele nn. uute sorditud loetellu
7. Korda kahte viimast tegevust

Näide kuidas sortimise algoritm töötab viie elemendi korral(->sümboliseeerib ühepoolset viitamist):

31->25->12->22->11 //kustutan 1 viida
31  25->12->22->11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida
25->31  12->22->11 //kustutan 1 viida, võrdlen 2 korda, loon 1 viida
12->25->31  22->11 //kustutan 1 viida, võrdlen 2 korda, loon 2 viita
12->22->25->31  11 //kustutan 1 viida, võrdlen 4 korda, loon 1 viida  
11->12->22->25->31 
//Θ(n*1,8)

Näide teisele poole sortimisest:

31->25->12->22->11 //kustutan 1 viida
31  25->12->22->11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida
31->25  12->22->11 //kustutan 1 viida, võrdlen 2 korda, loon 1 viida
31->25->12  22->11 //kustutan 1 viida, võrdlen 1 korra, loon 2 viita
31->25->22->12  11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida  
31->25->22->12->11
//Θ(n)

Analüüs

Parimal juhul, kui andmed on juba sorditud, on implementasitoonil sortimise efektiivväärtus: Θ(n): iga iteratsiooni (tsükli ületäitumise) korral, võrreldakse ainult 1 kord (seda viimase elemndiga), nõnda kogu andmehulga korral. See on muide kiirsordi kõige ebameeldivaim juhtum. Kui andmed on peaaegu sorditud, annab algoritm märgatavalat paremaid tulemusi kui kiirsortimine.

Kõige ebameeldivaim juhtum oleks, kui andmed oleksid sorditud tagurpidi, kuna iga element peab otsima kõik sorditud andmed läbi, et leida endale koht. Antud juhul oleks oleks algoritmi efektiivsusfaktor Θ(n²), mis neelkord näitab algoritmi ebapraktilisust suurte andmekoguste korral. Siiski, on vahelepanemisega sortimise sisemine kordus väga kiire, mis teeb ta üheks kiiremaks sortimis algoritmiks väheste elementidega, tüüpiliselt 10 või umbes nõndapalju.

Lisaks:

Üks universaalne sortimisprotseduur oleks: sortida keeruka sortimisalgoritmiga algselt andmed ära ja lõpetada vahelepanemisega sortimisega.

Implementatsioon

void insertSort(int a[], size_t length) {
   int i, j, value;
  
   for(i = 1; i < length; i++) {
       value = a[i];

       for (j = i - 1; j >= 0 && a[j] > value; j--) {
          a[j + 1] = a[j];
       }

       a[j + 1] = value;
   }
}

Mullisortimine (Bubble sort)

Mullisortimine on sortimis algoritm, täpsemalt on tegu elementide võrdlusega järgmise elemendiga sortimisega. Ta omab Θ(n-n²) efektiivsusfaktorit, olles nõnda ebaefektiivne suurte hulkade korral. Algoritm on efektiivne, kui algandmed on sorditud või on, kui sortimata algandmed on õige väärtuse läheduses.

Algoritmi tööpõhimõte on:

1. Võrdle elementi ja talle järgnevat, kui 1 (või 2 - sortides teistpidi) on suurem, vaheta
2. Kui elementide läbikäimisel väärtust muudeti, korda tegevust (võttes järgmise elemendi)

Näide kuidas sortimise algoritm töötab viie elemendi korral:

31 25 12 22 11 //võrdlen 4 korda, vahetan 12 korda
25 12 22 11 31 //võrdlen 3 korda, vahetan 9 korda
12 22 11 25 31 //võrdlen 2 korda, vahetan 3 korda
12 11 22 25 31 //võrdlen 1 korra, vahetan 3 korda
11 12 22 25 31 
//Θ(n*2)

Näide teisele poole sortimisest:

31 25 12 22 11 //võrdlen 4 korda, vahetasin 3 korda
31 25 22 12 11 //võrdlen 3 korda
//Θ(n*1,4)

Implementatsioon

void bubbleSort( int* array, int size){
    bool swaped;
    int temp;
    for(int i = 1; i < size; i++)
    {
        swaped = false;    //lipp on kontrolliks kas andmed on juba sorditud
        for( int j = 0; j < size - i; j++)
        {
            if(array[j] > array[j+1])
            {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swaped = true;
            }
        }
        if(!swaped){
            break; //kui andmed on sorditud peata tsükkel
        }
    }
}

Teine, kirjapildilt pisut lühem võimalus:

void bubbleSort( int* array, int size){
    int temp;
    for(int i = 0; i < size - 1; i++)
        for( int j = i + 1; j < size; j++)
            if(array[i] > array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
}