Sorting
1. Pengertian Sorting
Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakanaturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulanelemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiapelemen.
Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:
a. Urut naik (ascending) Mengurutkan dari data yang mempunyai nilai paling kecilsampai paling besar.
b. Urut turun (descending) Mengurutkan dari data yang mempunyai nilai paling besarsampai paling kecil.
Ada 2 metode sorting data yang akan dubahas dalam tulisan kali ini yaitu, bubble sort danquick sort.
2. Bubble Sort
Bubble Sort merupakan cara pengurutan yang sederhana. Konsep dari ide dasarnya adalahseperti “gelembung air” untuk elemen struktur data yang semestinya berada pada posisiawal. Cara kerjanya adalah dengan berulang-ulang melakukan proses looping terhadapelemen-elemen struktur data yang belum diurutkan. Di dalam proses looping tersebut,nilai dari dua elemen struktur data dibandingkan. Jika ternyata urutannya tidaksesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sorting inidisebut juga dengan comparison sort dikarenakan hanya mengandalkan perbandingannilai elemen untuk mengoperasikan elemennya.
Algoritma bubble sort dapat diringkas sebagai berikut, jika N adalah panjang elemenstruktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
a. Lakukan looping untuk membandingkan dua elemen berdekatan. Looping inidilakukan dari belakang.
b. Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkanke proses looping berikutnya sampai bertemu dengan bagian struktur data yang telahdiurutkan.
c. Ulangi langkah di atas untuk struktur data yang tersisa.
Contoh Program Bubble Sort
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int i, j, pil, n, sementara;
cout<<"Masukkan banyak data acak : "; cin>>n;
int data[n];
for(i=0;i<n;i++)
{
cout<<"Data ke-"<<i+1<<" : "; cin>>data[i];
}pilihan :
cout<<"Data : ";
for(i=0;i<n;i++){cout<<data[i]<<", ";}
cout<<endl<<"====================================="<<endl;
cout<<"Sorting bubble : "<<endl;
cout<<"1. Ascending "<<endl;
cout<<"2. Descending "<<endl;
cout<<"Masukkan pilihan menu (1/2) : ";cin>>pil;
switch(pil)
{
case 1:
for(i=0; i<=n-2; i++)
{
for(j=n-1; j>=i+1; j--)
{
if(data[j]<data[j-1])
{
sementara=data[j];
data[j]=data[j-1];
data[j-1]=sementara;
}
}
}
cout<<"Data setelah disorting : ";
for(i=0; i<n; i++)
{
cout<<data[i]<<", ";
}
break;
case 2:
for(i=0; i<=n-2; i++)
{
for(j=n-1; j>=i+1; j--)
{
if(data[j]>data[j-1])
{
sementara=data[j];
data[j]=data[j-1];
data[j-1]=sementara;
}
}
}
cout<<"Data setelah disorting : ";
for(i=0; i<n; i++)
{
cout<<data[i]<<", ";
}
break;
default:
cout<<"Anda salah memasukkan kode "<<endl;
goto pilihan;
break;
}
getche();
return 0;
}
|
Hasil Running
3. Quick Sort
Dalam algoritma Quick Sort dikenal apa yag disebut dengan pivot, pivot merupakan suatuelemen yang dipilh dari elemen array yang akan di urutkan, pivot dapat diambil darielemen paling pinggir dari Array ataupun dari elemen yang tengah.
Dalam pengoperasiannya elemen yang lebih besar dari elemen pivot akan dipindah kesebelah kanan pivot dann yang lebih kecil akan dipindah kesebelah kiri pivot, proses inidisebut dengan proses partitioning dan akan mengasilkan dua partisi array, yaitu partisiyang lebih besar dari pivot dan partisi yang lebih kecil dari pivot. Proses diatas kemudiandilakukan lagi pada masing-masing paritisi,
Secara ringkas, algoritma Quick Sort adalah sebagai berikut:
a. Pilih elemen pivot.
b. Pindahkan elemen array yang lebih kecil dari elemen pivot ke sebelah kiri pivot, dan elemen yang lebih besar dari lemen pivot ke sebelah kanan pivot.
c. Ulangi langkah 1 dan 2 untuk masing masing partisi yang terbentuk dari langkah.
Contoh Program Bubble Sort
#include <iostream>
#define n 20
using namespace std;
int Ar[n];
void
quickSort(int arr[], int left, int right);
int main()
{
int jumlahBil=5;
cout<<"Masukkan jumlah bilangan dalam : ";
cin>>jumlahBil;
int Ar[jumlahBil];
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << " : ";
cin>>Ar[i];
}
quickSort(Ar,0,jumlahBil-1 );
cout<<"Data yang telah diurutkan"<<endl;
for(int i=0; i<jumlahBil;i++)
{
cout<<Ar[i]<<"\n";
}
cin.get();
return 0;
}
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
|
Hasil Running
Sumber :
Modul Praktikum Alpro2 Politeknik Negeri Tanah Laut 2018
