DAA - Bubble Sort

Bubble Sort adalah algoritme pengurutan dasar, yang bekerja dengan bertukar berulang kali elemen yang berdekatan, jika perlu. Ketika tidak ada pertukaran yang diperlukan, file tersebut diurutkan.

Ini adalah teknik paling sederhana di antara semua algoritma pengurutan.

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]

Penerapan

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; 
      } 
}

Analisis

Di sini, jumlah perbandingannya

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

Jelas, grafik menunjukkan n² sifat dari jenis gelembung.

Dalam algoritma ini, jumlah perbandingan tidak tergantung pada kumpulan datanya, yaitu apakah elemen input yang diberikan berada dalam urutan yang diurutkan atau dalam urutan terbalik atau secara acak.

Persyaratan Memori

Dari algoritma yang disebutkan di atas, terlihat jelas bahwa bubble sort tidak membutuhkan memori tambahan.

Contoh

Unsorted list:

5	2	1	4	3	7	6

1 ^st iterasi:

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 iterasi:

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

Tidak ada perubahan di 3 ^rd , 4 ^th , 5 ^th dan 6 ^th iterasi.

Akhirnya,

the sorted list is

1	2	3	4	5	6	7