Mullisortimine
Allikas: Vikipeedia
See artikkel vajab toimetamist. |
Sorteerimine |
---|
Valikuga sortimine |
[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:
- Võrdle elementi ja talle järgnevat, kui 1 (või 2 - sortides teistpidi) on suurem, vaheta
- 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