Pengertian Sorting
Pengurutan dapat
dilakukan secara ascending (urut naik) dan descending (urut turun). Pengurutan
(Sorting) adalah proses pengurutan data yang sebelumnya disusun secara
acak sehingga tersusun secara teratur menurut aturan tertentu.
ada
banyak program sorting dalam C++, seperti bubble
sort, selection sort, insertion sort, exchange sort, merge sort, quick sort,
dan lain sebagainya.
 |
| Sorting C++ |
1. Bubble Sort
Yang pertama kita akan membahas bubble
sort. Algoritma ini merupakan salah satu algoritma pengurutan yang paling
sederhana, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma
bubble sort adalah mengulang proses pembandingan antara tiap-tiap elemen array
dan menukarnya apabila urutannya salah.
Teknik ini menyusun data yang diinginkan
secara berurutan dengan membandingkan elemen data yang ada dan terus diulang
hingga tidak perlu dilakukan penukaran lagi.
Berikut ini adalah gambaran dari algoritma
bubble sort:
Source
code
|
for
i:=1 to Jumlah_data-1 do
for j:=i+1 to Jumlah_data do
if Data[i]>Data[j] then
begin
t:=Data[i];
Data[i]:=Data[j];
Data[j]:=t;
end;
|
Kita misalkan memiliki 5 angka yang akan
kita simpan kedalam variable Data (Array).
Dengan masing-masing nilai sebagai
berikut:
Source code
|
Data[1] := 3;Data[2] := 1;Data[3] := 4;Data[4] := 2;Data[5] := 6; |
Cara Kerja:
1) Langkah
pertama: Data[1] akan dibandingkan dengan Data[2]. Jika Data[1] lebih besar
dari Data[2] maka nilai dari kedua variabel tersebut ditukar posisinya.
2) Data[1]
akan terus dibandingkan dengan data-data selanjutnya (Data[3], Data[4], dan Data[5]).
Hingga akhirnya Data[1] berisi nilai terkecil.
3) Setelah
proses perbandingan Data[1] selesai, selanjutnya kita akan membandingkan Data[2]
dengan Data[3], Data[4] dan Data[5] seperti proses sebelumnya.
4) Begitu
seterusnya sampai semua data selesai di bandingkan.
2. Quick Short
Algoritma quick short ditemukan oleh E.
Hoare. Algoritma ini menggunakan metode rekursi sampai habis. Prinsipnya
membagi data menjadi dua bagian yang sama (kiri dan kanan). Dimana data tengah
menjadi pivot (pusat operasi).
Kemudian kita akan mengumpukan data dengan
nilai lebih kecil dari pivot disebelah kiri pivot, dan di kanan untuk yang
lebih besar. Karena dimungkinkan bagian kiri dan kanan pivot tidak sama
besarnya. maka dari itu tiap bagian di bagi menjadi dua lagi sehingga mempunyai
pivot yang baru.
Source code
|
baca:=0;pusat := A[(awal+akhir) div 2];kiri := awal;kanan := akhir;
While
kiri <= kanan Do Begin While A[kiri] < pusat Do
Inc(kiri); While A[kanan] > pusat Do
Dec(kanan);
If kiri<=kanan Then
Begin
Ganti(A[kiri],A[kanan]);
Inc(kiri);
Dec(kanan);
Inc(baca);
End; End;
If
kanan>awal Then
Urut(awal,kanan); If akhir>kiri Then
Urut(kiri,akhir); |
Algoritma Quick Sort juga disebut juga
dengan partition Exchange sort karena konsepnya membuat
partisi-partisi, dan sort dilakukan per partisi.
3. Insert Short
Sesuai
namanya, pengurutan sisip adalah metode pengurutan dengan menyisipkan elemen
array / larik pada posisi yang tepat dengan cara menyisirnya.
Algoritma utamanya adalah sebagai berikut
:
Source
code
|
baca:=0;
For
i:= 2 To m Do
Begin
G:=A[i]; j:=i-1; A[0]:=G;
While G<A[j] Do
Begin
A[j+1]:=A[j];
Dec(j);
Inc(baca);
End;
A[j+1]:=G;
End;
|
4. Merge
Short
MergeSort adalah algoritma yang
berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua
bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih
kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist
tersebut.
1) Divide: membagi
masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah
semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2) Conquer: memecahkan
(menyelesaikan) masing-masing submasalah (secara rekursif), dan
3) Combine: mengabungkan
solusi masing-masing submasalah sehingga membentuk solusi masalah semula.
Source code
|
#include <iostream>
using namespace std;
void merge(int low, int mid, int up); void mergeSort(int low, int up); int a[50]; int main() { int jumlahBil,i; cout<<"Masukkan Jumlah element Array"<< endl; cin>>jumlahBil; for(int i=0; i<jumlahBil;i++) { cout<<"Bilangan ke-"<< i+1 << endl; cin>>a[i]; } mergeSort(1,jumlahBil); for(i=1;i<=jumlahBil;i++) cout<<a[i]<<" "; cout<<endl; return 0; } void merge(int low, int mid, int up) { int h, i,j,k; int b[50]; h = low; i = low; j = mid+1; while((h<=mid)&&(j<=up)) { if(a[h] < a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>mid) { for(k=j;k<=up;k++){ b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } for(k=low;k<=up;k++) a[k]=b[k]; } void mergeSort(int low, int up) { int mid;if(low<up){mid=(low+up)/2;mergeSort(low,mid);mergeSort(mid+1,up);merge(low,mid,up);}} |
5. Selection
Short
Adalah metode sorting dimana elemen-elemen
di perbandingkan satu-persatu sampai pada elemen terakhir dan disusun
berdasarkan ketentuan ketentuan berlaku (terbesar atau terkecil).
Source code
|
#include<iostream>
using
namespace std;
int
main()
{
int a,k,c,d,g;
k=4;
int b[4];
cout<<"SELECTION SORT BY
ZEFTAADETYA.BLOGSPOT.COM"<<endl;
cout<<"mengurutkan nilai dari besar ke
kecil"<<endl<<endl;
for(a=0;a<k;a++)
{
cout<<"Masukkan nilai
"<<a+1<<" : ";cin>>b[a];
}
for(a=0;a<k-1;a++)
{
c=a;
for(d=a+1;d<k;d++)
{
if(b[c]<b[d])
{
c=d;
}
}
g=b[c];
b[c]=b[a];
b[a]=g;
}
cout<<"\n setelah diurutkan akan menjadi : \n";
for(a=0;a<k;a++)
{
cout<<b[a]<<" \n";
}
}
|
Daftar Pustaka
0 komentar: