Sorting Algorithm: Bubble Sort (LENGKAP)

Algoritma Pengurutan: Bubble Sort

Sorting adalah suatu proses pengurutan data yang acak menjadi tersusun secara teratur berdasarkan suatu aturan tertentu.

Algoritma Bubble Sort merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat. Bubble sort mendapatkan namanya dari fakta bahwa data "bergelembung" ke bagian atas dataset. Bubble sort secara alternatif disebut "sinking sort" untuk alasan yang berlawanan, yaitu bahwa beberapa elemen data tenggelam ke bagian bawah dataset, karena itulah dinamakan Bubble yang artinya gelembung. 

Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending).

Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan yakni dengan cara membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar. 

Kelebihan dan Kekurangan

Berikut ini beberapa kelebihan yang dimiliki oleh algoritma ini:

• Algoritma ini adalah metode paling sederhana untuk mengurutkan data
• Paling simple dan mudah dipahami.

kekurangan dari algortima ini adalah sebagai berikut:

• Sangat lambat prosesnya ketika menangani data yang berjumlah besar, hal inilah yang menjadikan Bubble Sort merupakan metode pengurutan yang tidak efisien,
• Jumlah pengulangan yang dilakukan oleh algortima ini akan tetap sama jumlahnya, meskipun data yang diurutkan sudah cukup terurut.

Simulasi

Langkah Pengurutan:

1. Mulai dari indeks pertama, bandingkan elemen pertama dan kedua.
2. Jika elemen pertama lebih besar dari elemen kedua, mereka akan ditukar. 
3. Sekarang, bandingkan elemen kedua dan ketiga. Tukar jika tidak berurutan.
4. Proses di atas berlanjut hingga elemen terakhir

Kompleksitas Algoritma Bubble Sort

Kompleksitas sebuah algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.

Time Complexity
Best	O(n)
Worst	O(n2)
Average	O(n2)
Space Complexity	O(1)
Stability	Yes

1. Kondisi Waktu Terbaik (Best-Case)

Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Dalam hal ini, data yang akan diurutkan telah terurut sebelumnya. Sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali iterasi.

Contoh:

Iterasi pertama:

(9 10 11 12) menjadi (9 10 11 12)

(9 10 11 12) menjadi (9 10 11 12)

(9 10 11 12) menjadi (9 10 11 12)

Dalam proses di atas,  tidak terdapat proses pertukaran data apapun. Sehingga tidak dilakukan iterasi selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n).

Poin:

• Dalam skenario kasus terbaik, array sudah diurutkan, tetapi untuk berjaga-jaga, bubble sort melakukan perbandingan O(n).
• Akibatnya, kompleksitas waktu dari bubble sort dalam skenario kasus terbaik adalah O(n).

2. Kompleksitas Waktu Kasus Rata-rata

kondisi average-case, jumlah iterasi ditentukan dari data mana yang mengalami pergeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja deretan bilangan (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseran paling banyak adalah elemen 2, yaitu sebanyak dua kali.

Iterasi Pertama:

(1 8 6 2) menjadi (1 8 6 2)

(1 8 6 2) menjadi (1 6 8 2)

(1 6 8 2) menjadi (1 6 2 8)

Iterasi Kedua:

(1 6 2 8) menjadi (1 6 2 8)

(1 6 2 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

Iterasi Ketiga:

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

(N^2) adalah Kompleksitas Waktu Kasus Rata-rata dari Bubble Sort. Jumlah perbandingan konstan dalam Bubble Sort sehingga dalam kasus rata-rata, ada perbandingan O(N^2). Ini karena terlepas dari susunan elemen, jumlah perbandingan C(N) adalah sama.

Untuk jumlah swap, pertimbangkan poin-poin berikut:

• Jika sebuah elemen berada dalam indeks I1 tetapi seharusnya berada dalam indeks I2, maka dibutuhkan minimal pertukaran I2-I1 untuk membawa elemen ke posisi yang benar.
• Elemen E akan berada pada jarak I3 dari posisinya dalam larik terurut. Nilai maksimum I3 adalah N-1 untuk elemen tepi dan N/2 untuk elemen di tengah.

Jumlah perbedaan posisi maksimum di semua elemen adalah:

(N-1) + (N-3) + (N-5) ... + 0 + ... + (N-3) + (N-1)

= N x N - 2 x (1 + 3 + 5 + ... + N/2)

= N^2 - 2 x N^2 / 4

= N^2 - N^2 / 2

= N^2 / 2

• rata-rata jumlah swap = O(N^2).

Oleh karena itu, dalam kasus rata-rata kompleksitas waktu dari Bubble sort:

• Jumlah Perbandingan: O(N^2) waktu
• Jumlah swap: O(N^2) waktu

3. Kompleksitas Waktu Kasus Terburuk (Worst-Case)

(N^2) adalah Kompleksitas Waktu Kasus Terburuk dari Bubble Sort.

Jika kita ingin mengurutkan dalam urutan menaik dan array dalam urutan menurun dan data terkecil berada dalam ujung barisan maka kasus terburuk terjadi.

Jumlah pertukaran dua elemen sama dengan jumlah perbandingan dalam hal ini karena setiap elemen tidak pada tempatnya.

${T(N) = C(N) = S(N) = \frac{N*(N-1)}{2}}$ persamaan 2 dan 4

Karena itu, dalam kasus terburuk:

• Jumlah Perbandingan: O(N^2) waktu
• Jumlah swap: O(N^2) waktu

Contoh dari kasus ini dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini:

Iterasi Pertama:

(4 3 2 1) menjadi (3 4 2 1)

(3 4 2 1) menjadi (3 2 4 1)

(3 2 4 1) menjadi (3 2 1 4)

Iterasi Kedua:

(3 2 1 4) menjadi (2 3 1 4)

(2 3 1 4) menjadi (2 1 3 4)

(2 1 3 4) menjadi (2 1 3 4)

Iterasi Ketiga:

(2 1 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Iterasi Keempat:

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Proses di atas menunjukan bahwa setiap kali melakukan satu iterasi, data terkecil akan bergeser ke arah awal sebanyak satu step. Jadi, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan iterasi sebanyak tiga kali, ditambah satu kali iterasi untuk verifikasi data. 

Space Complexity

Algoritma ini hanya membutuhkan variabel tambahan untuk flag, variabel sementara dan dengan demikian kompleksitas ruangnya adalah O(1).

Algoritma

bubbleSort(array)

  for i <- 1 to indexOfLastUnsortedElement-1

    if leftElement > rightElement

      swap leftElement and rightElement

end bubbleSort

Pseudocode

1 2 3 4 5 6 7 8 9 10 11 12

procedure bubbleSort(A : list of sortable items) n := length(A) for i := 0 to n-1 inclusive do for j := 0 to n-i-1 inclusive do // the elements aren't in the right order if A[j] > A[j+1] then // swap the elements swap(A[j], A[j+1]) end if end for end for end procedure

Implementasi Bubble Sort Kedalam Bahasa Pemrograman C++

 1. Source Code

#include <iostream>
using namespace std;

int main(){
	//disini kita melakukan pembuatan array yang mana berasal dari inputan user
	int banyakA;
	int x[100];
	cout<<"masukann banyak array :";
	cin>>banyakA;
	for(int m=0;m<banyakA;m++){
		cout<<"masukan array ke "<<m<<" :";
		cin>>x[m];
	}
	//proses pembuatan array
	//menampilkan array sebelum disorting
	cout<<"array awal adalah:"<<endl;
	int y=banyakA-2;
	int param;
	for(int m=0;m<banyakA;m++){
		cout<<x[m]<<" ";
	}
	cout<<endl<<endl<<"mulai proses sorting"<<endl;
	
	//memulai proses sorting
	while(y >= 0){
		int index = 0;
		while(index <= y){
			if(x[index] > x[index+1]){
				param = x[index];
				x[index] = x[index+1];
				x[index+1] = param;
						
			} 
			index++;
		}
		//di sini kita melakukan pengecekan hasil disetiap tahapan sort
		for(int m=0;m<banyakA;m++){
		cout<<x[m]<<" ";
	}
	cout<<endl;
		y--;
	}
	//processing end
	
	//disini kita melakukan looping untuk mengeluarkan hasil sorting
	cout<<"hasil sortingnya adalah:"<<endl;
	
	for(int m=0;m<banyakA;m++){
		cout<<x[m]<<" ";
	}
}

 2. Output: 

---

Daftar Referensi:

• "Belajar Algoritma Bubble Sort Untuk Pengurutan" Diakses dari https://teknojurnal.com/pengertian-algoritma-bubble-sort. Pada13 Agustus 2022
• "Buble Sort". Diakses dari https://www.programiz.com/dsa/bubble-sort. Pada 13 Agustus 2022
• "Apa itu Algoritma Bubble Sort?" https://dosenit.com/kuliah-it/rpl/algoritma-bubble-sort
• "Contoh Program Bubble Sort C++". Diakses dari https://kelasprogrammer.com/contoh-program-bubble-sort-cpp
• "Bubble Sort Algorithm: Overview, Time Complexity, Pseudocode and Applications".  Diakses dari https://www.simplilearn.com/tutorials/data-structure-tutorial/bubble-sort-algorithm#:~:text=The%20bubble%20sort%20algorithm%20is,pairs%20in%20the%20given%20array
• "Time and Space complexity of Bubble Sort".  Diakses dari https://iq.opengenus.org/time-space-complexity-bubble-sort/