Vikipeedia

Mullsortimine: erinevus redaktsioonide vahel

Sirvi ajalugu interaktiivselt
← Vanem muudatusUuem muudatus →
Eemaldatud sisu Lisatud sisu
VisuaalneVikitekst
PResümee puudub
→‎Pseudokood: vorminduse parandus
Märgis: Lähteteksti muudatus (2017)
45. rida:
===Pseudokood===
Algoritmi võib esitada kujul:
<source lang="pascal">
<code>
'''procedure''' bubbleSort( A ''':''' list of sortable items )
'''do'''
swapped := false
'''for each''' i '''in''' 0 '''to''' length(A) - 2 '''inclusive do:'''
'''if''' A[i] > A[i+1] '''then'''
swap( A[i], A[i+1] )
swapped := true
'''end if'''
'''end for'''
'''while''' swapped
'''end procedure'''
</codesource>
 
====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.
 
<source lang="pascal">
<code>
'''procedure''' bubbleSort( A ''':''' list of sortable items )
n := length( A )
'''do'''
swapped := false
'''for each''' i '''in''' 0 '''to''' n - 1 '''inclusive do:'''
'''if''' A[ i ] > A[ i + 1 ] '''then'''
swap( A[ i ], A[ i + 1 ] )
swapped := true
'''end if'''
'''end for'''
n := n - 1
'''while''' swapped
'''end procedure'''
</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.</code>
 
===C===
Näidislahendus [[C (programmeerimiskeel)|C]]-s:
Pärit leheküljelt "https://et.wikipedia.org/wiki/Mullsortimine"