Algoritma sorting sederhana yang lain adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Algoritma selection sort dapat dirangkum sebagai berikut:
1. Temukan nilai yang paling minimum (atau sesuai keinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.
2. Tukar nilai tersebut dengan nilai pada posisi pertama di bagian struktur data yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian struktur data yang tersisa.
Script program:
/*Selection Sort*/
#include <iostream>
#include <iomanip>
using namespace std;
void SelectionSort (int array [], const int size)
{
int i,j,kecil,temp;
for (i=0; i<size; i++)
{
kecil=i;
for(j=i+1; j<size; j++)
{
if (array[kecil]>array[j])
{kecil=j;}
}temp= array [i];
array[i]=array[kecil];
array[kecil]=temp;
}
}
int main ()
{
int NumList[8]={5,34,32,25,75,42,22,2};
int temp;
cout<<"Data Sebelum Diurutkan: \n";
for(int d=0; d<8;d++)
{
cout<<setw(3)<<NumList[d];
}
cout<<"\n\n";
cout<<"Data Setelah Diurutkan : \n";
for (int iii=0; iii<8; iii++)
cout<<setw(3)<<NumList[iii]<<endl<<endl;
}
Output program:
Algoritma :
2. Membaca file header.
3. Membaca fungsi, int, kecil, temp.
4. Membaca perulangan beserta fungsi kecil dan temp.
5. Membaca fungsi utama, fungsi numlist dan temp.
6. Membaca perulangan.
7. Cetak hasil.
8. Tampilan data sebelum diurutkan.
9. Membaca fungsi metode selection sorting.
10. Membaca perulangan.
11. Cetak hasil.
12. Tampilan data setelah diurutkan.
13. Selesai.
Deskripsi :
Program diatas menggunakan metode selection sort untuk mengurutkan beberapa bilangan. Penulisan file header dalam code blocks perlu diperhatikan karena tidak sama dengan penulisan script pada MinGw atau visual c++. Dalam code blocks untuk penulisan fungsi atau rumus biasanya berwarna, jika terdapat kesalahan pada saat pengeksekusian hal lain yang perlu diperhatikan adalah penulisan rumus. Sistematika pengurutan bilangan dengan metode selection sort adalah menemukan nilai paling minimum/maksimum sesuai dengan perintah apakah assceding atau desscending. Kemudian tukar nilai dengan nilai pada posisi pertama pada bagian struktur data yang belum diurutkan. kemudian lakukan terus penukaran nilai sampai semua struktur data tidak ada yang tidak di seleksi. Algoritma program diatas adalah menggunakan pembanding dan posisi. Angka tersebut di urutkan kemudian di posisikan barulah dilakukan pertukaran bilangan apabila memenuhi syarat. Seperti program diatas : 5 34 32 25 75 42 22 2. Pembandingnya terdiri dari 5<34 maka posisinya 0 karena sudah benar peletakan, kemudian 5<32 juga 0, 5<25=0, 5<75=0, 5<42=0, 5<22=0, 5<2 karena pembanding ini salah maka harus dilakukan swap ”penukaran” sebanyak 7x. Begitu seterusnya sehingga bilangan menjadi urut, karena ada 8 data maka akan terjadi tahapan sebanyak 7 kali.
EXCHANGE SORT
Metode pengurutan excahange sort mirip dengan metode pengurutan Buble Sort *bisa di katakan bersaudara. Tapi dalam cara membandingan antar elemennya tentu memiliki perbedaan.
Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
Cara pengurutan exchange sort:
void exchange_sort(int data[])
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(data[i]<data[j])
tukar(&data[i],&data[j]);
}
}
}
QUICK SORT
Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.
Algoritma Quick Sort
Algoritma ini terdiri dari 4 langkah utama:
1. Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil sebuah elemen yang akan digunakan sebagai pivot point (poin poros). (Biasanya elemen yang paling kiri.)
3. Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar dari pada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.
MERGE SORT
Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,
1. Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan dari pada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit dari pada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudah terurut.
Algoritma Merge Sort
Algoritma Merge Sort sederhananya, dapat ditulis berikut:
1. Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
2. Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3. Gabung 2 sublist kembali menjadi satu list terurut.
SHELL SORT
Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudain elemen kedua kita bandingkan dengan elemen lain dengan jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.
Contoh dari proses Sorting dengan menggunakan metode Shell Sort:
Script program :
/*shell sort*/
#include<iostream>
using namespace std;
int main(void)
{
int array[5]; // An array of integer
int length = 5; // Length of the array
int i, j, d;
int tmp, flag;
//some input
for(i=0; i<length; i++)
{
cout<<"Enter a number: ";
cin>>array[i];
}
//Algorithm
d=length;
flag=1;
while(flag || (d>1))
{
flag=0;
d=(d+1)/2;
for(i=0; i<(length -d); i++)
{
if(array[i+d]>array[i])
{
tmp=array[i+d];
array[i+d]=array[i];
array[i]=tmp;
flag=1;
}
}
}
//Some output
for(i=0; i<5; i++)
{
cout<<array[i]<<endl;
}
}
Output Program :
Algoritma :
1. Mulai.
2. Membaca file header.
3. Membaca fungsi main.
4. Membaca fungsi array yang didalamnya terdpat fungsi panjang.
5. Membaca perulangan.
6. Membaca percabangan.
7. Membaca fungsi temp.
8. Membaca perulangan.
9. Pemanggilan array[i].
10. Cetak hasil.
11. Selesai.
Deskripsi :
Program diatas menggunakan metode sheel short yang sistematika membandingkan elemen pertama dengan elemen lain yang berada dalam jarak yang sama namun yang lingkupnya paling jauh, begitu seterusnya sampai membandingkan elemen pada jarak yang berdekatan satu sama lain. Algoritma program diatas adalah karena sistematikanya membandingkan antar elemen yang letaknya berjauhan sampai terdekat maka seperti ini ilustrasinya: angka yang diinputkan tergantung pengguna. Misalnya ingin menginputkan 4 data maka akan ada 4 data, misalnya 6 9 7 4 maka sistematika kerjanya adalah 6 akan dibandingkan dengan 4, 7, 9 dari jarak terjauh-terdekat. Kemudian tentukan jika ascending atau descending pernyataan bilangannya seperti apa contoh 6<4 dan lain sebagainya.
TREE SORT
Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output:
PreOrder, InOrder, dan PostOrder.
Konsep dan Algoritma:
Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dsb. Dalam tree sort ada istilah akar atau root dan daun atau leaf.Perhatikan gambar di bawah ini.
Ketentuan dari gambar diatas adalah:
1. menjadi akar,
2. menjadi subtree kiri,
3. menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri,
6. menjadi daun dari subtree kanan.
Langsung saja bisa memahami algoritmanya lewat coding di bawah ini:
#include "iostream"
Hasil output:
1. PostOrder
2. InOrder
3. PreOrder
HEAP SORT
Heapsort adalah metode mengurutkan dengan memanfaatkan sifat yang dimiliki oleh struktur data heap. Heap sendiri adalah sebuah “binary search tree” dengan sifat parent memiliki nilai >= nilai yang ada di anaknya. Meski dikatakan ia adalah sebuah binary search tree, namun heap lebih diarahkan ke konsepsi / menganggap suatu array memiliki sifat heap.
Ambil suatu indeks dari array, misal i. Jika dianggap elemen di i sebagai node, ia akan disebut parent jika ia memiliki anak dengan indeks 2i+1 dan 2i+2. Contoh: indeks 0 akan memiliki anak di indeks 1 dan 2.
Heapsort dimulai dengan membentuk array memenuhi sifat heap untuk seluruh indeks. Setelah melakukan penataan, dipastikan elemen terbesar akan berada di root / node paling atas heap (indeks 0). Nah, selanjutnya adalah kita pindahkan elemen terbesar itu ke belakang barisan. Untuk node dari 0 hingga n-2, lakukan penataan lagi dan pemindahan elemen terbesar ke belakang. Hasilnya adalah elemen akan terurut secara ascending setelah proses ini.
Source code:
void siftDown(int arr[], int start, int end) {
/** start dan end berada dalam jangkauan array yang terdefinisi dengan start < end **/
/** Menata array dalam jangkauan sesuai kriteria sifat heap **/
/** deklarasi **/
int root=start; // pencarian dimulai dari root
int child; // menyimpan indeks anak yang diperiksa
int inswap; // indeks untuk swap
int temp;
/** sift ketika root masih memiliki anak **/
/** indeks anak ada di 2*root+1 dan 2*root+2 **/
while(2*root+1 <= end) {
child = 2*root+1; // dapatkan data anak
inswap = root;
/** Ambil elemen terbesar dan letakkan di root **/
if(arr[inswap] < arr[child])
inswap = child;
if(child+1 <= end)
if(arr[inswap] < arr[child+1])
inswap = child+1;
if(root!=inswap) {
// pertukarkan
temp = arr[root];
arr[root] = arr[inswap];
arr[inswap] = temp;
// track down, buat agar struktur heap di bawah konsisten
root = inswap;
} else return;
}
}
//————————————————————————————
void heapify(int arr[], int n) {
/** n = jumlah elemen di array **/
/** heapidy membentuk heap dengan bantuan siftdown. Hasil akhirnya adalah array yang tertata sesuai sifat heap **/
/** mulai heapify dari tengah dan terus naik hingga indeks 0 **/
int start=(n-2)/2;
for(int i=start; i>=0; i–)
siftDown(arr,i,n-1);
}
//————————————————————————————
void heapsort(int arr[], int n) {
/** n = jumlah elemen di array **/
/** lakukan heapify untuk menciptakan heap semu **/
heapify(arr,n);
/** tercipta heap, elemen terbesar ada di root (indeks 0)
* lakukan iterasi untuk setiap langkah, pindahkan root ke akhir,
* decrement indeks dan lakukan penataan ulang lagi
*/
int end=n-1;
int temp;
while(end>0) {
// pindahkan root ke akhir
temp = arr[0];
arr[0] = arr[end];
arr[end]= temp;
// majukan end
end -= 1;
// lakukan penataan ulang dengan siftDown
siftDown(arr,0,end);
}
}
TREE SORT
Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output:
PreOrder, InOrder, dan PostOrder.
Konsep dan Algoritma:
Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dsb. Dalam tree sort ada istilah akar atau root dan daun atau leaf.Perhatikan gambar di bawah ini.
Ketentuan dari gambar diatas adalah:
1. menjadi akar,
2. menjadi subtree kiri,
3. menjadi subtree kanan,
4 & 5. menjadi daun dari subtree kiri,
6. menjadi daun dari subtree kanan.
Langsung saja bisa memahami algoritmanya lewat coding di bawah ini:
#include "iostream"
#include "conio.h"
using namespace std;
struct Node {
int item; //variabel item
Node *kiri; //pointer ke subtree kiri
Node *kanan; //pointer ke subtree kanan
};
void tambah(Node **akar,intitembaru) //berisi pointer yang menunjuk ke pointer akar itu sendiri
{
if((*akar) == NULL) //jika akar kosong maka membuat item baru
{
Node *baru; //pointer baru
baru = new Node; //new node = alamat baru
baru->item = itembaru; //baru di tunjuk oleh pointer item & di isi dengan item baru
baru->kiri = NULL; //baru ditunjuk dengan pointer kiri ,dan jika masihh kosong
baru->kanan = NULL; //baru ditunjuk dengan pointer kanan & jika kosong
(*akar) = baru; //pointer akar = variabel baru dengan alamat baru
(*akar)->kiri = NULL;
(*akar)->kanan = NULL;
cout<<"Item bertambah!";
}
else if(itembaru < (*akar)->item) tambah(&(*akar)->kiri,itembaru);
// jika item yang ditambah di kiri
// jika item yang ditambah di kiri
else if(itembaru > (*akar)->item) tambah(&(*akar)->kanan,itembaru); //jika item yang ditambah item ke kanan
else if(itembaru == (*akar)->item) //jika item yang di input sama dengan item yang ditambah sebelumnya
cout<<"Item sudah ada!";
}
void tampil(Node *akar) //fungsi menampilkan seluruh item yang telah di imput
{
if(akar != NULL){
cout<<akar->item<<" ";
tampil(akar->kiri), //rekursif dengan fungsi tampil dengan mengarah ke kanan
tampil(akar->kanan); //rekursif dengan fungsi tampil dengan mengarah ke kanan
}}
void preOrder(Node *akar) //fungsi cetak preOrder
{
if(akar != NULL){
cout<< akar->item<<" "; //cetak item akar
preOrder(akar->kiri), //cetak di subtree kiri
preOrder(akar->kanan); //cetak di subtree kanan
}}
void inOrder(Node *akar) //fungsi cetak inOrder
{
if(akar != NULL){
inOrder(akar->kiri), //cetak di subtree kiri
cout<< akar->item<<" "; //cetak item akar
inOrder(akar->kanan); //cetak di subtree kanan
}}
void postOrder(Node *akar) //fungsi cetak postOrder
{
if(akar != NULL){
postOrder(akar->kiri), //cetak di subtree kiri
postOrder(akar->kanan); //cetak di subtree kanan
cout<< akar->item<<" "; //cetak item akar
}}
main()
{
int item;
Node *phn; //pointer phn untuk menghubungkan dengan link Node
phn = NULL; //alamat pointer phn pada NULL
char pil;
do {
system("cls");
cout<<"\tTREE SORT\n";
cout<<"1. Tambah\n";
cout<<"2. Pre-order\n";
cout<<"3. In-order\n";
cout<<"4. Post-order\n";
cout<<"5. Keluar\n";
cout<<"Silahkan masukkan pilihan anda (1-5)... ";
pil=getche();
if(pil=='1')
{
cout<<"\n";
cout<<"\nItem baru : ";cin>>item;
tambah(&phn,item); //fungsi tambah dengan menggunakan alamat pointer phn dengan variabel
}
if(pil=='2')
{
if(phn!=NULL) { //jika phn tidak kosong
cout<< "\n-->Item yang masuk : ";tampil (phn); //cetak item yang masuk
cout<<"\n-->preOrde : ";preOrder(phn); //cetak preOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
if(pil=='3')
{
if(phn!=NULL) {
cout<< "\n-->Item yang masuk : ";tampil(phn); //cetak item yang masuk
cout<<"\n-->inOrder : ";inOrder(phn); //cetak item inOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
if(pil=='4')
{
if(phn!=NULL) {
cout<< "\n-->Item yang masuk : ";tampil(phn); //cetak item yang masuk
cout<<"\n-->postOrder : ";postOrder(phn); //cetak item postOrder
}
else cout<<"\n-->Masih kosong!";
getch();
}
}
while(pil!='5');
cout<<"\n";
}Hasil output:
1. PostOrder
2. InOrder
3. PreOrder
HEAP SORT
Heapsort adalah metode mengurutkan dengan memanfaatkan sifat yang dimiliki oleh struktur data heap. Heap sendiri adalah sebuah “binary search tree” dengan sifat parent memiliki nilai >= nilai yang ada di anaknya. Meski dikatakan ia adalah sebuah binary search tree, namun heap lebih diarahkan ke konsepsi / menganggap suatu array memiliki sifat heap.
Ambil suatu indeks dari array, misal i. Jika dianggap elemen di i sebagai node, ia akan disebut parent jika ia memiliki anak dengan indeks 2i+1 dan 2i+2. Contoh: indeks 0 akan memiliki anak di indeks 1 dan 2.
Heapsort dimulai dengan membentuk array memenuhi sifat heap untuk seluruh indeks. Setelah melakukan penataan, dipastikan elemen terbesar akan berada di root / node paling atas heap (indeks 0). Nah, selanjutnya adalah kita pindahkan elemen terbesar itu ke belakang barisan. Untuk node dari 0 hingga n-2, lakukan penataan lagi dan pemindahan elemen terbesar ke belakang. Hasilnya adalah elemen akan terurut secara ascending setelah proses ini.
Source code:
void siftDown(int arr[], int start, int end) {
/** start dan end berada dalam jangkauan array yang terdefinisi dengan start < end **/
/** Menata array dalam jangkauan sesuai kriteria sifat heap **/
/** deklarasi **/
int root=start; // pencarian dimulai dari root
int child; // menyimpan indeks anak yang diperiksa
int inswap; // indeks untuk swap
int temp;
/** sift ketika root masih memiliki anak **/
/** indeks anak ada di 2*root+1 dan 2*root+2 **/
while(2*root+1 <= end) {
child = 2*root+1; // dapatkan data anak
inswap = root;
/** Ambil elemen terbesar dan letakkan di root **/
if(arr[inswap] < arr[child])
inswap = child;
if(child+1 <= end)
if(arr[inswap] < arr[child+1])
inswap = child+1;
if(root!=inswap) {
// pertukarkan
temp = arr[root];
arr[root] = arr[inswap];
arr[inswap] = temp;
// track down, buat agar struktur heap di bawah konsisten
root = inswap;
} else return;
}
}
//————————————————————————————
void heapify(int arr[], int n) {
/** n = jumlah elemen di array **/
/** heapidy membentuk heap dengan bantuan siftdown. Hasil akhirnya adalah array yang tertata sesuai sifat heap **/
/** mulai heapify dari tengah dan terus naik hingga indeks 0 **/
int start=(n-2)/2;
for(int i=start; i>=0; i–)
siftDown(arr,i,n-1);
}
//————————————————————————————
void heapsort(int arr[], int n) {
/** n = jumlah elemen di array **/
/** lakukan heapify untuk menciptakan heap semu **/
heapify(arr,n);
/** tercipta heap, elemen terbesar ada di root (indeks 0)
* lakukan iterasi untuk setiap langkah, pindahkan root ke akhir,
* decrement indeks dan lakukan penataan ulang lagi
*/
int end=n-1;
int temp;
while(end>0) {
// pindahkan root ke akhir
temp = arr[0];
arr[0] = arr[end];
arr[end]= temp;
// majukan end
end -= 1;
// lakukan penataan ulang dengan siftDown
siftDown(arr,0,end);
}
}