DAA - sortowanie bąbelkowe

Sortowanie bąbelkowe to elementarny algorytm sortowania, który w razie potrzeby działa poprzez wielokrotną wymianę sąsiednich elementów. Gdy nie są wymagane żadne wymiany, plik jest sortowany.

To najprostsza technika spośród wszystkich algorytmów sortowania.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Realizacja

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analiza

Oto liczba porównań

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Oczywiście wykres pokazuje n² charakter rodzaju bąbelkowego.

W tym algorytmie liczba porównań jest niezależna od zbioru danych, tj. Czy podane elementy wejściowe są w kolejności posortowanej, w kolejności odwrotnej lub losowej.

Wymagania dotyczące pamięci

Z powyższego algorytmu jasno wynika, że sortowanie bąbelkowe nie wymaga dodatkowej pamięci.

Przykład

Unsorted list:

5	2	1	4	3	7	6

1 ^st iteracja:

5 > 2 swap

2	5	1	4	3	7	6

5 > 1 swap

2	1	5	4	3	7	6

5 > 4 swap

2	1	4	5	3	7	6

5 > 3 swap

2	1	4	3	5	7	6

5 < 7 no swap

2	1	4	3	5	7	6

7 > 6 swap

2	1	4	3	5	6	7

2 ^ND iteracji:

2 > 1 swap

1	2	4	3	5	6	7

2 < 4 no swap

1	2	4	3	5	6	7

4 > 3 swap

1	2	3	4	5	6	7

4 < 5 no swap

1	2	3	4	5	6	7

5 < 6 no swap

1	2	3	4	5	6	7

Nie ma zmiany w 3 ^rd , 4 ^TH , 5 ^TH i 6 ^-go iteracji.

Wreszcie,

the sorted list is

1	2	3	4	5	6	7