Sorting Algorithm: Bubble Sort (LENGKAP)

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).

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

2. Kompleksitas Waktu Kasus Rata-rata

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.

Karena itu, dalam kasus terburuk:

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

#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]<<" ";
	}
}