Quick Sorting
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa.
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.
Algoritma Quick Sort.
Pilih satu elemen secara acak sebagai pivot
Pindahka 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.
Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot.
Proses pengurutan berhenti bila pointer kiri overlap dengan pointer kanan (langkah 8 di gambar atas), sekaligus membagi (divide) 2 bagian yang akan diurutkan selanjutnya; yaitu partisi kiri dan kanan.
Proses pengurutan dilakukan sama dengan langkah sebelumnya (rekursif) dan dilakukan pada partisi kiri dan kanan. Pembagian partisi berhenti bila tiap partisi hanya menyisakan satu elemen data saja (lihat warna hijau pada langkah 4 di atas).
Ketika proses pengurutan dilakukan secara rekursif (berulang), maka menghasilkan partisi hanya satu elemen saja dan kemudian digabung kembali sehingga terlihat bahwa data telah berurutan. Untuk lebih jelasnya, anda bisa memahami proses sorting dengan membaca Algoritma Quick Sort di bawah ini :
Contoh program dalam wujud berbeda :
#include <iostream>
using namespace std;
void quick_sort(int[],int,int);
int partition(int[],int,int);
int main()
{
int n,i;
n =7;
int a[]={9,4,2,7,10,1,5};
cout<<"\nData sebelum pengurutan:\n";
for(i=0;i<n;i++)
cout<<a[i]<<" , ";
quick_sort(a,0,n-1);
cout<<"\nData setelah dilakukan quick sort:\n";
for(i=0;i<n;i++)
cout<<a[i]<<" , ";
return 0;
}
void quick_sort(int a[],int l,int u)
{
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(int a[],int l,int u)
{
int v,i,j,temp;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
Hasil running :
Bubble Sorting
Algoritma Bubble Sort merupakan proses pengurutan yang secara berangsur-angsur memindahkan data ke posisi yang tepat. Karena itulah, algoritma ini dinamakan “bubble” atau yang jika diterjemahkan ke dalam Bahasa Indonesia, artinya yaitu gelembung. Fungsi algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar (ascending) atau sebaliknya (descending).
Metode pengurutan gelembung (Bubble Sort) ini terinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun yang lebih ringan ketimbang berat jenis air, maka gelembung sabun akan selalu terapung ke atas permukaan. Prinsip inilah yang dipakai pada algoritma pengurutan gelembung.
Secara sederhana, bisa didefinisikan bahwa algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus sampai pada satu iterasi tertentu dimana tidak ada lagi perubahan yang signifikan.
Sebelum kita masuk untuk membuat program, berikut ini adalah syarat dan langkah-langkah yang harus diperhatikan pada metode Bubble Sort:
Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.
Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.
Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan.
Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan Descending.
Untuk mempelajari algoritma Bubble Sort ini, Anda hanya perlu memahami cara yang digunakan untuk mengurutkan data. Logika sederhananya, algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Kita simak salah satu contoh di bawah ini, yang merupakan gambaran dari penerapan algoritma Bubble Sort dengan array “3 1 4 2 8”.
Proses pertama:
(3 1 4 2 8) menjadi (1 3 4 2 8)
(1 3 4 2 8) menjadi (1 3 4 2 8)
(1 3 4 2 8) menjadi (1 3 2 4 8)
(1 3 2 4 8) menjadi (1 3 2 4 8)
Proses kedua:
(1 3 2 4 8) menjadi (1 3 2 4 8)
(1 3 2 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
Proses ketiga:
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
Jika diperhatikan proses yang terjadi di atas, ketika proses kedua data di dalam array sudah terurut dengan benar. Tetapi, algoritma Bubble Sort akan terus berjalan hingga proses kedua berakhir. Proses ketiga ini akan terus berjalan, karena pada algoritma Bubble Sort, yang dimaksud “data sudah terurut” adalah tidak ada satupun pertukaran data pada suatu proses. Proses ketiga ini dimaksudkan untuk verifikasi data.
Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan. Dua hal inilah yang menjadi pertimbangan programmer ketika membuat program. Berikut ini beberapa kelebihan yang dimiliki oleh algoritma ini :
1. Algoritma ini adalah metode paling sederhana untuk mengurutkan data.
2. Selain sederhana, algoritma ini juga mudah dipahami.
3. Sedangkan, kekurangan dari algortima ini adalah sebagai berikut:
Tingkat efisiensinya yang kurang. Bubble Sort ini merupakan metode pengurutan yang tidak efisien, khususnya ketika menangani data yang berjumlah besar. Hal tersbeut karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya.
Jumlah pengulangan yang dilakukan oleh algortima ini akan tetap sama jumlahnya, meskipun data yang diurutkan sudah cukup terurut.
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat. Artinya Algoritma ini akan menggeser nilai yang terkecil atau terbesar (sesuai dengan jenis pengurutan, ascending atau descending) ke posisi ujung dari daftar. Demikian seterusnya hingga semua daftar dalam keadaan terurut. Proses dasar yang terjadi dalam algoritma ini adalah proses pertukaran nilai (swapping).
Contoh syntax program :
#include<iostream>
using namespace std;
main()
{
int i,j,n,data[100],save,k;
cout<<" Masukkan banyak data : ";cin>>n;
for(i=1;i<=n;i++)
{
cout<<" Data "<<i<<" : ";cin>>data[i];
}
cout<<" Awal : "<<endl;
for(i=1;i<=n;i++)
cout<<data[i]<<" "<<endl;
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(data[j]>data[j+1])
{
save=data[j];
data[j]=data[j+1];
data[j+1]=save;
}
}
}
cout<<" Hasilnya : "<<endl;
for(i=1;i<=n;i++)
cout<<data[i]<<" ";
}
Hasil running program :
No comments:
Post a Comment