Metode-metode sorting pada pemrograman C++
1.
Bubble sort
Bubble
sort merupakan algoritma pengurutan
paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan
dengan membandingkan masing-masing item dalam suatu list secara
berpasangan, menukar item jika diperlukan, dan mengulaginya
sampai akhir list secara berurutan, sehingga tidak ada lagi item
yang dapat ditukar.
Kelebihan dan
Kekurangan Bubble Sort
a.
Kelebihan
·
Metode
Bubble Sort merupakan yang paling
simple
·
Metode
Bubble Sort muda di pahami
algoritmanya
b.
Kelemahan
·
Relative lambat untuk mengurutkan data yang
sangat besar
·
Jumlah
pengulangan akan tetap sama jumlahnya walaupun data sudah cukup terurut
Algoritma bubble sort:
#include
<iostream>
#define
N 20
using
namespace std;
int
i, j, A[N];
int
bubble (int n)
{
int temp;
for(i=1; i<=n-1; i++)
{
for(j=i; j<n; j++)
{
if(A[i-1]>A[j])
{
temp=A[i-1];
A[i-1]=A[j];
A[j]=temp;
}
}
}
}
main()
{
int jml;
cout<<" Masukkan jumlah
bilangan\t: "; cin>>jml;
for(i=0; i<jml; i++)
{
cout<<" \t\tBilangan ke
"<<i+1<<"\t: "; cin>>A[i];
}
bubble(jml);
cout<<" Data yang sudah terurut:
\n";
for(i=0; i<jml; i++)
{
cout<<"
\t\t\t\t"<<A[i]<<"\n";
}
}
2.
Quick
sort
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.
Algoritma Quick 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 : ";
cin>>jumlahBil;
int Ar[jumlahBil];
for(int
i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>Ar[i];
}
quickSort(Ar,0,jumlahBil-1 );
cout<<"Data yang telah diurutkan :"<<endl;
for(int
i=0; i<jumlahBil;i++)
{
cout<<"\t\t\t
"<<Ar[i]<<"\n";
}
}
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);
}
3.
Marge
sort
Merge
sort adalah algoritme divide-and-conquer berdasar kepada proses
memecah list menjadi beberapa sublist hingga pada akhirnya tiap sublist hanya
berisi satu elemen lalu sublist tersebut akan digabungkan dengan cara tertentu
hingga list tersortir.
Algoritma Quick sort:
#include
<iostream>
#include
<conio.h>
using
namespace std;
int a[50];
void
merge(int,int,int);
void
merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void
merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h]; h++;
}
else
{
b[i]=a[j]; j++;
} i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k]; i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k]; i++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
int main()
{
int num,i;
cout<<"------------------------"<<endl;
cout<<" MERGE SORT PROGRAM
"<<endl;
cout<<"------------------------"<<endl;
cout<<endl;
cout<<"Masukkan Banyak Bilangan:
";cin>>num;
cout<<endl;
cout<<"Sekarang masukkan"<<num<<"Bilangan
yang ingin Diurutkan :"<<endl;
for(i=1;i<=num;i++)
{
cout<<"Bilangan
ke-"<<i<<" ";cin>>a[i] ;
}
merge_sort(1,num);
cout<<endl;
cout<<"Hasil akhir pengurutan
:"<<endl;
cout<<endl;
for(i=1;i<=num;i++)
cout<<a[i]<<" ";
cout<<endl;
getch();
}
Sumber:
Komentar
Posting Komentar