Pengertian Sorting
Sorting
merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan
tertentu. Sorting disebut juga
sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan
tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya
ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:
1. Urut naik (ascending)
Mengurutkan
dari data yang mempunyai nilai paling kecil sampai paling besar.
2. Urut turung (descending)
Mengurutkan
dari data yang mempunyai nilai paling besar sampai paling kecil.
Metode-metode sorting yaitu antara lain:
1. Bubble Sort
2. Quick Sort
3. Insert Sort
4. Marge Sort
5. Selection Sort
A. Bubble Sort
Bubble Sort
adalah salah satu metode sorting atau mengurutkan dari data terkecil ke data
terbesar ataupun dengan cara membandingkan elemen kesatu dengan elemen yang
selanjutnya.
Berikut
contoh program bubble sort pada C++
yaitu mengurutkan nilai yang terkecil hingga nilai terbesar:
1. Program Bubble Sort C++
|
#include<iostream>
#include<conio.h>
using
namespace std;
int
main()
{
int data[10];
int i, j, tmp;
cout<<"Program Mengurutkan
Data"<<endl;
cout<<"Dengan Metode Bubble
Sort"<<endl;
for(i=0; i<10; i++)
{
cout<<"Masukkan bilangan ke
"<<(i+1)<<" : ";
cin>>data[i];
}
cout<<"Data sebelum diurutkan :
"<<endl;
for(i=0; i<10; i++)
{
cout<<data[i]<<"
";
}
cout<<endl;
for(i=0; i<9; i++)
{
for(j=i+1; j<10; j++)
{
if(data[i]>data[j])
{
tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
cout<<"Data setelah diurutkan :
"<<endl;
for(i=0; i<10; i++)
{
cout<<data[i]<<"
";
}
getch();
}
|
2.
Hasil running Bubble Sort
B. Quick Sort
Quick sort merupakan salah satu
algoritma pengurutan data yang menggunakan teknik membagi data menjadi
partisi-partisi. Metode quick sort
disebut juga dengan nama partition
exchange sort.
Berikut contoh program Quick sort pada C++:
1. Program Quick Sort pada C++
|
#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 arry [Maksimal 20]"<<endl;
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<<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);
}
|
2. Hasil Running Quick Sort
C. Insert Sort
Insert Sort adalah sebuah algoritma
pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemusian
mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen
data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan
elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comprasion-based sort. Ide dasar dari
algoritma Insertion Sort ini adalah
mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian
menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses
dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai
"pass"), dengan indeks dimulai dari 0. Proses pengurutan dengan
menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data
ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data
berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan
ke depan sesuai dengan posisi yang seharusnya.
1. Program Insert Sort pada C++
|
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
int data[10], data2[10];
int n;
void tukar(int a, int b)
{
int t;
t =
data[b];
data[b] =
data[a];
data[a] =
t;
}
void insertion_sort()
{
int
temp,i,j;
for(i=1;
i<=n; i++)
{
temp =
data[i];
j =
i-1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
int main()
{
cout
<< "Masukkan Jumlah Data : "; cin >>n;
for(int
i=1; i<=n; i++)
{
cout
<< "Masukkan data ke "<< i <<" : "; cin
>> data[i];
data2[i]=data[i];
}
insertion_sort();
cout
<< "\n Data setelah di Sort : ";
for(int
i=1; i<=n; i++)
{
cout
<< " "<<data[i];
}
getch();
}
|
2. Hasil Running Insert Sort
D. Marge Sort
Marge sort 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 marge
sort c++ ini ditemukan oleh John von Neumann tepat pada tahun 1945.
1. Program Marge 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];
}
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<<"Hasil akhir pengurutan :"<<endl;
cout<<endl;
for(i=1;i<=num;i++)
cout<<a[i]<<" ";
cout<<endl<<endl<<endl<<endl;
}
|
2. Hasil Running Marge Sort
E. Selection Sort
Selection sort pencarian elemen yang tepat untuk diletakkan di
posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data
tersebut ditemukan, selection sort
dapat membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai
dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari
elemen sekarang maka di catat posisinya dan kemudian ditukar.
Pengurutan data dalam struktur data sangat penting untuk data yang
bertipe data numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun) pengurutan (sorting) adalah proses menyusun kembali
data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga
tersusun secara teratur menurut aturan tertentu.
1. Program Selection Sort pada
C++
|
#include<iostream>
using namespace std;
void seleksi(int data[],int n);/*prototipe fungsi*/
int main()
{
int i;
int
n=9;//index terbesar
int
data[]={20,10,32,100,60,12,70,25,45,65};
cout<<"Sebelum di urutkan :"<<endl;
for(i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<endl;
cout<<"___________________________________________________"<<endl;
seleksi
(data, n);
cout<<"Setelah diurutkan"<<endl;
for(i=0;i<=n;i++)
cout<<data[i]<<" ";
cout<<endl;
}
void seleksi(int Array1[],int n)
{
int
i,j,tmp,imaxs;
for(i=n;i>=1;i--)
{
imaxs=0;
for(j=1;j<=i;j++)
{
if
(Array1[j]>Array1[imaxs])
imaxs=j;
}
tmp=Array1[imaxs];
Array1[imaxs]=Array1[i];
Array1[i]=tmp;
}
}
|
2. Hasil Running Selection Sort
Sumber:
