Bubble Sorting
Algoritma Bubble Sorting
Bubble sort atau yang disebut dengan metode gelombang adalah metode mengurutkan data dengan cara membandingkan masing-masing elemen kemudian menukarkannya jika perlu. Penukaran data ini dilakukan terus-menerus sampai data terurut dan tidak ada perubahan.
Metode ini terinspirasi dari gelembung sabun yang berada di permukaan air. Pada dasarnya berat jenis gelembung sabun lebih ringan dari berat jenis air, maka gelembung sabun akan mengapung di atas permukaan air.
Kelebihan metode bubbe sort yaitu metode ini sederhana dan mudah dipahami, namun metode ini adalah metode yang tidak efisen pada saat mengurutkan data yang sangat besar maka akan mengalami kelambatan dan kinerja memburuk yang cukup signifikan.
Algoritma ini termasuk dalam algoritma comparison sort karena menggunakan perbandingan antar elemen.
Algoritma bubble sort yaitu:
a. Menbandingkan data ke-1 dengan data ke-(i+1). Apabila tidak sesuai (data ke-i > data ke(i+1) atau data ke-i < data ke(i+1)) maka akan terjadi pertukaran data (data ke-1 = data ke-(i+1) dan data ke-(i+1) = data ke-1).
b. Membandingkan data ke (i+1) dengan data ke-(i+2) dan seterusnya.
c. Selesai membandingkan satu iterasi antara (n-1) dengan n maka program akan melanjutkan ke iterasi berikutnya yaitu (n-1) sampai dengan seterusnya.
d. Proses akan berhenti apabila tidak ada pertukaran dalam satu iterasi.
Berikut adalah contoh algotitma bubble sort yaitu:
Proses yang akan terjadi apabila mengurutkan data " 4 2 5 3 9 " menggunakan algoritma bubble sort adalah sebagai berikut.
Pass pertama
4 2 5 3 9 menjadi 2 4 5 3 9
2 4 5 3 9 menjadi 2 4 5 3 9
2 4 5 3 9 menjadi 2 4 3 5 9
2 4 3 5 9 menjadi 2 4 3 5 9
Pass kedua
2 4 3 5 9 menjadi 2 4 3 5 9
2 4 3 5 9 menjadi 2 3 4 5 9
2 3 4 5 9 menjadi 2 3 4 5 9
2 3 4 5 9 menjadi 2 3 4 5 9
Pass kedua
2 3 4 5 9 menjadi 2 3 4 5 9
2 3 4 5 9 menjadi 2 3 4 5 9
2 3 4 5 9 menjadi 2 3 4 5 9
2 3 4 5 9 menjadi 2 3 4 5 9
Contoh Program
#include <iostream>#include <conio.h>
using namespace std;
int main()
{
int i,j,n,data[10],simpan,k;
cout<<"\tBUBBLE SORT MENGGUNAKAN C++"<<endl;
cout<<"\t============================"<<endl;
cout<<"\nmasukkan banyak data= ";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"data "<<i<<" = ";cin>>data[i];
}
cout<<"awal = ";
for(i=1;i<=n;i++)
cout<<data[i]<<" ";
cout<<endl;
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(data[j]>data[j+1])
{
simpan=data[j];
data[j]=data[j+1];
data[j+1]=simpan;
}
}
}
cout<<"hasil= ";
for(i=1;i<=n;i++)
cout<<data[i]<<" ";
getch();
}
Hasil Running:
Quick Sort
Algoritma Quick Sort
Quick sort adalah metode pengurutan cepat yang memiliki efektifitas tinggi dengan menukarkan dua elemen dengan jarak yang cukup besar. Pengurutan cepat ini membandingkan suatu elemen (pivot) dengan elemen lain sehingga elemen lin yang lebih kecil dari pivot maka akan terjadi pertukaran antara elemen sebelah kiri pivot fan elemen lain yang besar dari pivot terletak disebelah kanan.
Pada algoritma quick sort, pemilihan sort ialah hal yang paling menentukan. Apakah akan memberikan performa yang baik atau buruk.
Berikut cara pemilihan pivot:
1. Pivot merupakan elemen tengah dalam array. Cara ini bagus pada tabel acak namun tidak bagus pada tabel yang sudah terurut.
2. Pivot dipilih acak dari salah satu elemen array.
3. Pivot adalah elemen median tabel. Cara ini yaitu cara yang paling bagus, sebab hasil pembagian partisi pada tabel seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum.
Contoh Program
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int Data[MAX];
// Prosedur menukar data
void Tukar (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
} // Prosedur pengurutan metode Quick Sort
void QuickSortRekursif(int L, int R)
{
int i, j, x;
x = Data[(L+R)/2];
i = L;
j = R;
while (i <= j){
while(Data[i] < x)
i++;
while(Data[j] > x)
j--;
if(i <= j){
Tukar(&Data[i], &Data[j]);
i++;
j--;
}
}
if(L < j)
QuickSortRekursif(L, j);
if(i < R)
QuickSortRekursif(i, R);
}
int main()
{
int i;
srand(0);
// Membangkitkan bilangan acak
printf("DATA SEBELUM TERURUT");
for(i=0; i<MAX; i++)
{
Data[i] = (int) rand()/1000+1;
printf("\nData ke %d : %d ", i, Data[i]);
}
QuickSortRekursif(0, MAX-1);
// Data setelah terurut
printf("\nDATA SETELAH TERURUT");
for(i=0; i<MAX; i++)
{
printf("\nData ke %d : %d ", i, Data[i]);
}
}
Hasil Running:
Referensi
http://yuliana.lecturer.pens.ac.id/Struktur%20Data%20C/Prak%20SD%20-%20pdf/Praktikum%208.pdf
https://docplayer.info/50754841-Analisis-algoritma-bubble-sort.html
https://www.academia.edu/17143309/Struktur_Data_-_SORTING_PENGURUTAN_
http://yuliana.lecturer.pens.ac.id/Struktur%20Data%20C/Prak%20SD%20-%20pdf/Praktikum%209.pdf
https://www.academia.edu/10450333/Laporan_Quick_Sort
https://www.academia.edu/10072435/metode_Quick_Sort_C_
0 komentar:
Posting Komentar