SELECTION SORT
Metode seleksi adalah pengurutan data dengan cara mencari data yang terkecil kemudian menukarnya dengan data yang digunakan sebagai acuan (pivot).
Proses dari Selection Sort Ascending adalah sebagai berikut :
1. Mencari data terkecil dari data pertama sampai dengan data yang terakhir. Kemudian posisinya ditukar dengan data yang pertama.
2. Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian posisinya ditukar dengan data yang kedua.
3. Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian posisinya ditukar dengan data yang ketiga.
4. Begitu seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dengan data terakhir, yaitu data ke n tidak perlu diurutkan karena hanya tinggal data satu-satunya.
Untuk proses dari Selection Sort Descending (mencari data terbesar) adalah kebalikan dari proses di atas.
Sebagai contoh :
Terdapat suatu variable array dimana nilai dalam array tersebut :
NILAI[8] = { 44, 55, 12, 42, 94, 18, 6, 67 }
Penyelesaiannya adalah :
Agar lebih jelasnya kita langsung saja ke studi kasusnya dan source codenya pada borland C++ :
Selection Sort Ascending
Inputkan banyaknya data yang akan dilakukan sorting (max. 10). Inputkan data sesuai dengan banyaknya data yang diminta, kemudian urutkanlah data tersebut dari yang terkecil ke yang terbesar!
Source code :
#include<iostream.h>
#include<conio.h>
int data[10];
int n;
void tukar(int a, int b)
{
int t;
t=data[b];
data[b]=data[a];
data[a]=t;
}
void main()
{
int pos,i,j;
cout<<"-------------------------------------------------"<<endl;
cout<<"SELECTION SORT ASCENDING"<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAK DATA = ";
cin>>n;
cout<<"-------------------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"INPUTKAN DATA KE-"<<(i+1)<<" = " ;
cin>>data[i];
}
cout<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN :"<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"-------------------------------------------------"<<endl;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(data[j]<data[pos])pos=j;
}
if(pos!=i) tukar(pos,i);
}
cout<<"DATA YANG TELAH DIURUTKAN SECARA ASCENDING : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"SELECTION SORT SELESAI !"<<endl;
cout<<"-------------------------------------------------"<<endl;
getch();
}
Berikut ini hasil dari source code di atas :
Selection Sort Descending
Buatlah program seperti diatas, tetapi urutkan data dari yang terbesar ke terkecil.
Source code :
#include<iostream.h>
#include<conio.h>
int data[10];
int n;
void tukar(int a, int b)
{
int t;
t=data[b];
data[b]=data[a];
data[a]=t;
}
void main()
{
int pos,i,j;
cout<<"-------------------------------------------------"<<endl;
cout<<"SELECTION SORT DESCENDING"<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAK DATA = ";
cin>>n;
cout<<"-------------------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"INPUTKAN DATA KE-"<<(i+1)<<" = " ;
cin>>data[i];
}
cout<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN :"<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"-------------------------------------------------"<<endl;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(data[j]>data[pos])pos=j;
}
if(pos!=i) tukar(pos,i);
}
cout<<"DATA YANG TELAH DIURUTKAN SECARA DESCENDING : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"SELECTION SORT SELESAI !"<<endl;
cout<<"-------------------------------------------------"<<endl;
getch();
}
Hasilnya jika telah di run adalah :
INSERTION SORT
Pada metode insertion sort, proses pengurutannya dimulai dari data ke-2 (indeks ke-1), kemudian disisipkan pada tempat yang sesuai. Dan data pertama (data pada indeks ke-0) dianggap sudah pada tempatnya.
Kita coba saja langsung ke studi kasus dan source codenya :
Insertion Sort Ascending
Studi Kasus :
Buatlah program seperti selection di atas, dan urutkan data tersebut dari terkecil ke terbesar dengan menggunakan metode insertion sort.
Source code :
#include<iostream.h>
#include<conio.h>
int data[10];
int n;
void main()
{
int tmp,i,j;
cout<<"-------------------------------------------------"<<endl;
cout<<"INSERTION SORT ASCENDING"<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAKNYA DATA = ";
cin>>n;
cout<<"-------------------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"INPUTKAN DATA KE-"<<(i+1)<<" = " ;
cin>>data[i];
}
cout<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN :"<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"-------------------------------------------------"<<endl;
for(i=1;i<n;i++)
{
tmp=data[i];
j=i-1;
while(data[j]>tmp && j>=0)
{
data[j+1]=data[j];
j--;
}
data[j+1]=tmp;
}
cout<<"DATA YANG TELAH DIURUTKAN SECARA ASCENDING : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INSERTION SORT SELESAI !"<<endl;
cout<<"-------------------------------------------------"<<endl;
getch();
}
Berikut adalah hasilnya jika di run :
Insertion Sort Descending
Studi kasus :
Buatlah program yang sama, tetapi urutkan dari yang terbesar ke terkecil.
Source code :
#include<iostream.h>
#include<conio.h>
int data[10];
int n;
void main()
{
int tmp,i,j;
cout<<"-------------------------------------------------"<<endl;
cout<<"INSERTION SORT DESCENDING"<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAKNYA DATA = ";
cin>>n;
cout<<"-------------------------------------------------"<<endl;
for(int i=0;i<n;i++)
{
cout<<"INPUTKAN DATA KE-"<<(i+1)<<" = " ;
cin>>data[i];
}
cout<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN :"<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"-------------------------------------------------"<<endl;
for(i=1;i<n;i++)
{
tmp=data[i];
j=i-1;
while(data[j]<tmp && j>=0)
{
data[j+1]=data[j];
j--;
}
data[j+1]=tmp;
}
cout<<"DATA YANG TELAH DIURUTKAN SECARA DESCENDING : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INSERTION SORT SELESAI !"<<endl;
cout<<"-------------------------------------------------"<<endl;
getch();
}
Berikut hasilnya jika di run :
BUBBLE SORT :
Dalam bubble sort, prosesnya adalah selalu membandingkan 2 data yang berdekatan atau disebelahnya.
Lebih jelasnya langsung saja ke studi kasus dan source codenya.
Bubble Sort Ascending
Studi Kasus :
Buatlah program seperti selection dan insertion sort di atas dengan menggunakan metode bubble sort, dan urutkan data tersebut dari yang terkecil ke terbesar.
Source code :
#include<iostream.h>
#include<conio.h>
int data[20];
int n;
void main()
{
int i, j, tmp;
cout<<"---------------------------------------------"<<endl;
cout<<"BUBBLE SORT ASCENDING"<<endl;
cout<<"---------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAKNYA DATA : ";
cin>>n;
cout<<"---------------------------------------------"<<endl;
for(i=0; i<n; i++)
{
cout<<"INPUTKAN BILANGAN KE-["<<(i+1)<<"] : ";
cin>>data[i];
}
cout<<"---------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN : "<<endl;
for(i=0; i<n; i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"---------------------------------------------"<<endl;
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(data[i]>data[j])
{
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
cout<<"DATA SETELAH DIURUTKAN SECARA ASCENDING : "<<endl;
for(i=0; i<n; i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"---------------------------------------------"<<endl;
cout<<"BUBBLE SORT SELESAI !"<<endl;
cout<<"---------------------------------------------"<<endl;
getch();
}
Berikut hasilnya jika di run :
Bubble Sort Descending
Studi kasus :
Buatlah program seperti di atas, kemudian urutkan data dari terbesar ke terkecil.
Source code :
#include<iostream.h>
#include<conio.h>
int data[20];
int n;
void main()
{
int i, j, tmp;
cout<<"---------------------------------------------"<<endl;
cout<<"BUBBLE SORT DESCENDING"<<endl;
cout<<"---------------------------------------------"<<endl;
cout<<"INPUTKAN BANYAKNYA DATA : ";
cin>>n;
cout<<"---------------------------------------------"<<endl;
for(i=0; i<n; i++)
{
cout<<"INPUTKAN BILANGAN KE-["<<(i+1)<<"] : ";
cin>>data[i];
}
cout<<"---------------------------------------------"<<endl;
cout<<"DATA YANG DIINPUTKAN : "<<endl;
for(i=0; i<n; i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"---------------------------------------------"<<endl;
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(data[i]<data[j])
{
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
cout<<"DATA SETELAH DIURUTKAN SECARA DESCENDING : "<<endl;
for(i=0; i<n; i++)
{
cout<<data[i]<<" ";
}
cout<<endl<<"---------------------------------------------"<<endl;
cout<<"BUBBLE SORT SELESAI !"<<endl;
cout<<"---------------------------------------------"<<endl;
getch();
}
Dan berikut hasil dari source code di atas jika di run :
Quick Sort
Algoritma metode quick sort c++ diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960. Program quick sort c ++ adalah algoritma sorting yang berdasarkan pembandingan dengan metode divide and conquer (bagi dan kuasai). Disebut metode Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat. metode Quick sort c++ disebut juga dengan partition exchange sort, karena konsepnya membuat partisi-partisi, dan sorting dilakukan per partisi.
Contoh Algoritma Quick Sort C++
metode quick sort c++ mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Dapat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus. Tapi untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma metode quick sort c++.
Apa itu Pivot ?
Apa itu Pivot ?
Pada algoritma quick sort, pemilihan pivot ialah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :
- Pivot merupakan elemen pertama, elemen terakhir, atau elemen tengah dalam array. Cara ini bagus jika elemen tabel tersusun secara acak, tetapi sebaliknya atau tidak bagus jika elemen tabel semula sudah terurut.
- Pivot dipilih dengan cara acak dari salah satu elemen array. Cara ini baik tapi belum tentu maksimal, sebab diperlukan prosedur khusus untuk menentukan pivot secara acak.
- Pivot adalah elemen median tabel. Cara ini yaitu cara paling bagus, sebab pada hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri
Contoh program quick sort
#include <iostream>
#include <conio.h>
using namespace std;
void quick_sort(int arr[], int left, int right)
{
int i = left, j = right;int tmp;
int pivot = arr[(left+right)/2];/* partition */
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--;
};
}; /* recursion */
if (left < j)
quick_sort(arr, left, j);
if (i < right)
quick_sort(arr, i, right);
}
int main()
{
int i,n,data[50];
cout<<"Masukan banyak data: ";cin>>n;
for(i=0;i<n;i++)
{cout<<"Masukan data ["<<i<<"] : ";cin>>data[i];}
cout<<"\nData sebelum diurutkan: "<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil pengurutan
cout<<"\nHasil pengurutan:\n";
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}getch();
}
Output program quick sort
Marge Sort
Program Merge Sort C++ merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma program merge sort c++ ini ditemukan oleh John von Neumann tepat pada tahun 1945.
Algoritma coding merge sort bahasa c++ ini membagi (split) table menjadi dua tabel sama besar.
Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk table yang terurut. Implementasi dasar dari algoritma marge sort c++ ini memakai tiga buah tabel, dua diantaranya untuk menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan elemen yang telah teurut. Namun metode program merge sort c++ ini bisa juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini merupakan algoritma metode merge sort c++ yang dilakukan pada 2 tabel.
Algoritma Merge Sort C++ Dua Tabel
Algoritma Metode Merge sort c++ ini sebenernya lebih cepat dibandingkan heap sort untuk tabel yang lebih besar. Tetapi, algoritma ini membutuhkan setidaknya ruang / memori 2x lebih besar karena dilakukan secara rekursif dan juga memakai dua tabel. Hal ini menyebabkan algoritma ini kurang banyak dipakai.
Metode Merge sort menggabungkan 2 ide utama bertujuan untuk meningkatkan runtimenya:
- Array kecil mengambil langkah-langkah untuk menyortir lebih sedikit dari array besar.
- Dan Lebih sedikit langkah yang diperlukan untuk membangun sebuah data array terurut dari dua buah array terurut dari pada dari dua buah array tak terurut.
Contoh Program Marge Sort Pada C++
#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];
}
main()
{
int num,i;
cout<<"Hardifal "<<endl;
cout<<"---------------------------"<<endl;
cout<<" ALGORITMA MERGE SORT C++ "<<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<<endl;
for(i=1;i<=num;i++)
cout<<a[i]<<" ";
cout<<endl<<endl<<endl<<endl;
}
Output Program Marge Sort
