algoritma pemrograman: Nur Anita Humaida (1801301052)

Bubble Sort, Quick Sort, Merge sort.

- Bubble Sort

Bubble sort / pengurutan gelembung ini merupakan suatu metode pengurutan gelembung yang diinspirasi oleh gelembung sabun yang ada di dalam permukaan air, karena berat jenis gelembung sabun lebih ringan daripada berat jenis air maka gelembung sabun akan selalu megapung. Prinsip pengapungan ini juga dipakai pada pengurutan gelembung. Elemen yang berharga paling kecil “diapungkan”, yang artinya diangkat ke atas (atau ke ujung paling kiri) melalui pertukaran. Proses pengapungan ini dilakukan N kali langkah. Pada langkah ke 1, Larik[1….N] akan terdiri dari 2 bagian yaitu :

a. Bagian yang sudah terurut yaitu L[1]…L[i]

b. Bagian yang belum terurut L[i+1]..L[n]

Cntoh program 1 :

#include <iostream.h>
#include <conio.h>
main(){
int nilai[‘n’];
int temp;
int n;
cout<<“Banyak Data: “;
cin>>n;
cout<<endl;
for (int a=1; a<=n; a++){
cout<<“nilai[“<<a<<“]: “;
cin>>nilai[a];
}
cout<<“\n\n”;
cout<<“Data Sebelum diurutkan”<<endl;
for(int a=1; a<=n; a++){
cout<<nilai[a]<<” “;
}
for(int a=n-1; a>=1; a–){
for(int b=1; b<=a; b++){
if(nilai[b]>nilai[b+1]){
temp=nilai[b+1];
nilai[b+1]=nilai[b];
nilai[b]=temp;
}
}
}
cout<<“\n\nData Setelah Diurutkan (Ascending)”<<endl;
for (int a=1; a<=n; a++){
cout<<nilai[a]<<” “;}

cout<<“\n\n”;
cout<<“\n\nData Setelah Diurutkan (Descending)”<<endl;
for (int a=n; a>=1; a–){
cout<<nilai[a]<<” “;}
getch();
}

Outputnya :

Contoh program 2 :

Bubble sort adalah salah satu metode sorting atau mengurutkan dari data terkecil ke data terbesar ataupun dengan cara membandingkan elemen kesatu dengan elemen yang selanjutnya.

Konsep pada metode bubble sort ini adalah

Pada kesempatan kali ini kita akan membuat contoh program bubble sort pada bahasa c++ yaitu mengurutkan nilai terbesar ke nilai terkecil.

keterangan:
- baris 5 -7    = adalah pendeklarasian variabel dan array yang akan digunakan
                       dalam program
- baris 11-14 = Proses inputan yang disimpan dalam array yang dilakukan
   dalam perulangan
- baris 15-27 = Proses pengurutan antara elemen satu dengan yang lain dan
   apabila elemen satu lebih kecil daripada elemen berikutnya
                         (mengurtkan besar ke kecil) maka proses pertukaran akan
   terjadi pada pada baris 23- 25.
- baris 31-35 = Setelah pengurutan berhasil maka nilai akan dicetak/
                         ditampilkan pada baris ini.

Maka apabila di compile maka hasilnya akan menjadi :

- Quick Sort

Salah satu algoritma yang menggunakan paradigma Divide and Conquer adalah Algoritma Quick Sort. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil di sebelah kiri pivot dan semua elemen yang lebih besar di sebelah kanan pivot. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut.

Ide dari algoritma ini adalah sebagai berikut:

a. Pilih satu elemen secara acak sebagai pivot

b. Pindahkan semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya.

c. Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot.

Contoh Program