Mullsortimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
→Pseudokood: vorminduse parandus Märgis: Lähteteksti muudatus (2017) |
P Bot: Replace deprecated <source> tag and "enclose" parameter |
||
45. rida:
===Pseudokood===
Algoritmi võib esitada kujul:
<
procedure bubbleSort( A : list of sortable items )
do
57. rida:
while swapped
end procedure
</syntaxhighlight>
====Jõudluse parandus====
Mullimeetodi jõudlust saab parandada, kui arvestada, et pärast igat läbimist jõuab võrreldud elementidest suurim oma lõplikule kohale loendi lõpuosas. Loendi lõppu jõudnud elemendid on sorditud ja neid enam läbima ei pea. Näiteks suurusega ''n'' loendi korral on ''n''-is element on oma lõplikul positsioonil pärast esimest läbimist. Teisel läbimisel jääb sortida ''n - 1'' elementi. Pärast teist läbimist on element ''n - 1'' oma lõplikul positsioonil ja nii edasi.
<
procedure bubbleSort( A : list of sortable items )
n := length( A )
76. rida:
while swapped
end procedure
</syntaxhighlight>
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 kahanevas järjestuses) on mullimeetod selle täiendusega kaks korda kiirem.
===C===
Näidislahendus [[C (programmeerimiskeel)|C]]-s:
<
void bubbleSort(int numbers[], int numbers_size) {
int n, i;
98. rida:
int numbers[] = { 8, 1, 5, 2, 4 };
bubbleSort(numbers, 5);
</syntaxhighlight>
==Praktiline kasutus==
|