TEKNIK INFORMATIKA: Sorting

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]<<" ";