Mullsortimine: erinevus redaktsioonide vahel

Eemaldatud sisu Lisatud sisu
→‎Pseudokood: vorminduse parandus
Märgis: Lähteteksti muudatus (2017)
Xqbot (arutelu | kaastöö)
P Bot: Replace deprecated <source> tag and "enclose" parameter
 
45. rida:
===Pseudokood===
Algoritmi võib esitada kujul:
<sourcesyntaxhighlight lang="pascal">
procedure bubbleSort( A : list of sortable items )
do
57. rida:
while swapped
end procedure
</syntaxhighlight>
</source>
 
====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.
 
<sourcesyntaxhighlight lang="pascal">
procedure bubbleSort( A : list of sortable items )
n := length( A )
76. rida:
while swapped
end procedure
</syntaxhighlight>
</source>
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:
<sourcesyntaxhighlight lang="c">
void bubbleSort(int numbers[], int numbers_size) {
int n, i;
98. rida:
int numbers[] = { 8, 1, 5, 2, 4 };
bubbleSort(numbers, 5);
</syntaxhighlight>
</source>
 
==Praktiline kasutus==