Mullisortimine

Allikas: Vikipeedia

See artikkel vajab toimetamist.
Sorteerimine

Valikuga sortimine
Vahelepanemisega sortimine
Mullisortimine

[redigeeri] Mullisortimine (Bubble sort)

Mullisortimine on sortimisalgoritm, täpsemalt on tegu elementide võrdlusega järgmise elemendiga sortimisega. Ta omab Θ(n-n2) effektiivsusfaktorit, olles nõnda ebaeffektiivne suurte hulkade korral. Algoritm on efektiivne, kui algandmed on sorditud või 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)

[redigeeri] 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
        }
    }
}

[redigeeri] Vaata ka

  • sorteerimine