Bubble sort

Bubble sort este un algoritm de sortare care consta in parcurgerea unui vector si schimbarea a doua elemente adiacente daca valoarea elementului curent este mai mare decat valoarea elementului urmator. Operatia se repeta pana cand vectorul este sortat in intregime. La fiecare parcurgere a vectorului elementul cu valoarea cea mai mare ajunge ultimul in vector.

 

Sa presupunem ca avem urmatorul vector cu 10 elemente:

Dim $Array[10]
 
$Array[0] = 87
$Array[1] = 24
$Array[2] = 11
$Array[3] = 68
$Array[4] = 42
$Array[5] = 9
$Array[6] = 30
$Array[7] = 100
$Array[8] = 15
$Array[9] = 76

 

Implementarea unei functii care efectueaza o sortare folosind acest algoritm, in AutoIt, poate fi cea de mai jos:

Func BubbleSort(ByRef $aArray)
	For $i = UBound($aArray)-1 To 1 Step -1
		For $j = 1 To $i
			If ($aArray[$j-1] > $aArray[$j]) Then
				_ArraySwap($aArray[$j-1],$aArray[$j])
			EndIf
		Next
	Next
EndFunc

Nota: functia _ArraySwap este definita in Array.au3

 

Avand in vedere vectorul de mai sus, o prima trecere prin vector executand schimbari intre elementele adiacente, poate fi schitata ca in tabelul de mai jos. Cu culoarea rosu sunt reprezentate schimbarile de valori in vector iar cu albastru am reprezentat perechi adiacente care nu necesita schimbare de valori.

87

24

11

68

42

9

30

100

15

76

24

87

11

68

42

9

30

100

15

76

24

11

87

68

42

9

30

100

15

76

24

11

68

87

42

9

30

100

15

76

24

11

68

42

87

9

30

100

15

76

24

11

68

42

9

87

30

100

15

76

24

11

68

42

9

30

87

100

15

76

24

11

68

42

9

30

87

100

15

76

24

11

68

42

9

30

87

15

100

76

24

11

68

42

9

30

87

15

76

100

Se poate observa ca la finalul primei treceri prin vector, valoarea maxima ajunge pe ultima pozitie. Analog se executa treceri prin vector executand schimbari de valori, la fiecare trecere valoarea maxima ajunge in pozitie terminala (la fiecare trecere prin vector, numarul de pasi in vector se decrementeaza – plecand de la premisa ca pe ultima pozitie ajunge totdeauna valoarea maxima, nu mai este necesar ca vectorul sa fie parcurs in intregime).

Pentru o exemplificare mai buna a operatiilor efectuate de acest algoritm, urmariti animatia de mai jos:

Un exemplu de utilizare a acestei functii:

#include <Array.au3> 
 
Dim $Array[10]
 
$Array[0] = 87
$Array[1] = 24
$Array[2] = 11
$Array[3] = 68
$Array[4] = 42
$Array[5] = 9
$Array[6] = 30
$Array[7] = 100
$Array[8] = 15
$Array[9] = 76
 
_ArrayDisplay($Array,"Vector nesortat")
BubbleSort($Array)
_ArrayDisplay($Array,"Vector sortat")
 
Func BubbleSort(ByRef $aArray)
	For $i = UBound($aArray)-1 To 1 Step -1
		For $j = 1 To $i
			If ($aArray[$j-1] > $aArray[$j]) Then
				_ArraySwap($aArray[$j-1],$aArray[$j])
			EndIf
		Next
	Next
EndFunc

* Pentru orice intrebari sau nelamuriri legate de curs sau limbajul AutoIt accesati sectiunea AutoIt a forumului SkullBox sau platforma de suport tehnic NetHelp.