Mullsortimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
41. rida:
Algoritm lõpetab töö, kuna sellel läbimisel ei tehtud ühtegi vahetust, mis tähendab, et loend on sorditud.
==Implementatsioonid==
===
Algoritmi võib esitada kujul:
<code>
'''procedure''' bubbleSort( A ''':''' list of sortable items )
'''do'''
swapped := false
58. rida:
</code>
===
Mullimeetodi jõudlust saab parandada
<source lang="c">▼
void bubbleSort(int numbers[], int array_size)▼
int i, j, temp;▼
for (i = (array_size - 1); i > 0; i--)▼
for (j = 1; j <= i; j++)▼
{▼
if (numbers[j-1] > numbers[j])▼
{▼
temp = numbers[j-1];▼
numbers[j-1] = numbers[j];▼
numbers[j] = temp;▼
}▼
}▼
</source>▼
▲Mullimeetodi jõudlust saab parandada järgmisel viisil. Pärast iga läbimist jõuab suurim element oma kohale loendi lõpus (läbitud osa). Olgu meil loend suurusega ''n'', siis ''n''-is element on oma lõplikul positsioonil pärast esimest läbimist. Seega jääb sorteerida ''n - 1'' elementi. Pärast teist läbimist on ''n - 1''-ne element oma lõplikul positsioonil ja nii edasi. Iga läbimine võib olla ühe sammu võrra lühem, kui eelmine, selle asemel, et igal läbimisel võrrelda viimaseid elemente, mis on juba oma õigetel positsioonidel ning vahetust niikuinii ei toimu.
<code>
▲ '''procedure''' bubbleSort( A ''':''' list of sortable items ) '''defined as:'''
n := length( A )
'''do'''
102. rida ⟶ 76. rida:
'''end procedure'''
</code>
Selle asemel, et teha <math>n \cdot (n-1)</math> võrdlust, tehakse maksimaalselt <math>(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}</math> võrdlust. Täitmisaeg on ikka <math>O(n^2)</math>, kuid halvimal juhul (sisendandmed on
===C===
Näidislahendus [[C (programmeerimiskeel)|C]]-s:
▲<source lang="c">
if (left > right) {
▲ }
▲}
int numbers[] = { 8, 1, 5, 2, 4 };
bubbleSort(numbers, 5);
▲</source>
==Praktiline kasutus==
| |||