|
Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
Een andere sorteermethode is de "bubble sort".
Hierbij "borrelen" ( zoals luchtbellen ) de kleinste/lichtste waarden ( of eerst te sorteren waarden ) naar boven ( naar voren ) in de array.
Opnieuw gaan we uit van een ongesorteerd en gesorteerd deel in de tabel.
De werkwijze kan als volgt zijn :
(1) Vergelijk alle 2 opeenvolgende waarden van het ongesorteerde deel en verplaats steeds indien nodig de kleinste ( of eerst te sorteren ) waarde naar boven.
Hierbij bekom je een ongesorteerd deel die 1 element kleiner is, gezien de grootste waarde zich nu reeds onderaan bevindt.
Herhaal stap (1) totdat je een ongesorteerd deel hebt die slecht 1 element bevat.
Opnieuw veronderstellen we dezelfde ongesorteerde waarden : [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21 Ongesorteerde deel vanaf index 0 tot en met index 4.
We vergelijken 88 en 75, 88 > 75 => 88 en 75 omwisselen : [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 93 81 21 We vergelijken 88 en 93, 88 < 93 => niet omwisselen : [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 93 81 21 We vergelijken 93 en 81, 93 > 81 => 93 en 81 omwisselen : [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 75 88 81 93 21 We vergelijken 93 en 21, 93 > 21 => 93 en 21 omwisselen : [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 88 81 21 93 De grootste waarde bevindt zich nu achter-/onder-aan de tabel, dus dat element bevindt zich reeds op de juiste positie of is dus gesorteerd.
Ongesorteerde deel vanaf index 0 tot en met index 3 :
We vergelijken 75 en 88, 75 < 88 => niet omwisselen : [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 88 81 21 93 We vergelijken 88 en 81, 88 > 81 => 88 en 81 omwisselen : [-unsorted--------------------------------] [-sorted---]
index 0 1 2 3 4
value 75 81 88 21 93 We vergelijken 88 en 21, 88 > 21 => 88 en 21 omwisselen : [-unsorted---------------------] [-sorted--------------]
index 0 1 2 3 4
value 75 81 21 88 93 Ook 88 bevindt zich nu op de juiste positie, dus maakt nu deel uit van het gesorteerde deel.
Ongesorteerde deel vanaf index 0 tot en met index 2 :
We vergelijken 75 en 81, 75 < 81 => niet omwisselen : [-unsorted---------------------] [-sorted--------------]
index 0 1 2 3 4
value 75 81 21 88 93 We vergelijken 81 en 21, 81 > 21 => 81 en 21 omwisselen : [-unsorted----------] [-sorted-------------------------]
index 0 1 2 3 4
value 75 21 81 88 93 81 bevindt zich op de juist positie, dus maak deel uit van het gesorteerde deel.
Ongesorteerde deel vanaf index 0 tot en met index 1.
We vergelijken 75 en 21, 75 > 21 => 75 en 21 omwisselen : [-sorted-----------------------------------------------]
index 0 1 2 3 4
value 21 75 81 88 93 Het ene zogezegde ongesorteerde element kan nooit verkeerd gesorteerd staan ten opzichte van zichzelf, dus de volledige array is nu gesorteerd.
In deze uitwerking werden per verschuif-doorloping het grootste element naar onder in de array gebracht. Dus het is alsof de "zwaarste" elementen eerst naar de "bodem" zakten. Als je de elementen van het ongesorteerde deel in omgekeerde volgorde doorloopt ( van onder naar boven ) en steeds het kleinste bovenaan zet, dan bekom je meer het effect van de "lichtste" waarden die "opborrelen". Welke volgorde je ook gebruikt ( van boven naar onder of van onder naar boven ), het gaat in beide gevallen over een "bubble sort". Visual Basic 2010 Broncode Module BubbleSortExample Sub Main() Dim count As Integer = 5 Dim upperbound As Integer = count - 1 Dim numbers(upperbound) As Integer Dim index As Integer For index = 0 To upperbound numbers(index) = (count ^ index) * 93 Mod 97 - (count \ (index + 1)) Next Console.Write( "unsorted array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.WriteLine() Dim unsortedCount As Integer = count Do While unsortedCount > 1 Dim endIndexUnsortedPart As Integer = unsortedCount - 2 For index = 0 To endIndexUnsortedPart If numbers(index) > numbers(index + 1) Then Dim backup As Integer = numbers(index) numbers(index) = numbers(index + 1) numbers(index + 1) = backup End If Next unsortedCount -= 1 Console.Write( "temporary array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.WriteLine() Loop Console.Write( "sorted array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.ReadLine() End SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
Console Application Output unsorted array : 88 75 93 81 21
temporary array : 75 88 81 21 93
temporary array : 75 81 21 88 93
temporary array : 75 21 81 88 93
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
| 
6. 