metode sorting

 Tree sort

Tree sort adalah metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasik output: PreOrder,InOrder,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.

Setiap objek dalam pohon biner berisi dua pointer, biasanya disebut kiri dan kanan.Selain pointer ini tentu saja node dapat berisi tipe data lainnya. Misalnya, pohon biner integer bisa terdiri dari objek dari jenis berikut:

       struct Node {

           int item; / / Data dalam node ini.

           Node *kiri; / / Pointer ke subtree kiri.

           Node * kanan; / / ​​Pointer ke subtree kanan.

       }

Program tree sort :

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node{
int data;
node *left;
node *right;
};
node *root=NULL;

void Tambahnode(node **root, int isi) {
if((*root)==NULL){
node *baru;
baru= new node;
baru->data = isi;
baru->left = NULL;
baru->right = NULL;
(*root)=baru;
}
}

void preorder(node *root) {
if(root !=NULL) {
printf(“%i, “, root->data);
preorder(root->left);
preorder(root->right);
}
}

void inorder(node *root) {
if(root !=NULL) {
inorder(root->left);
printf(“%i, “, root->data);
inorder(root->right);
}
}

void postorder(node *root) {
if(root !=NULL) {
postorder(root->left);
postorder(root->right);
printf(“%i, “, root->data);
}
}

int main(){

int nil;
int x;
int y;
x=40;y=3;

gotoxy(x,y);
printf(“100\n”);
gotoxy(x-10,y+1);
printf(“90″);
gotoxy(x+10,y+1);
printf(“200\n”);
gotoxy(x-20,y+2);
printf(“80″);
gotoxy(x+20,y+2);
printf(“300\n”);
gotoxy(x-30,y+3);
printf(“70″);
gotoxy(x+30,y+3);
printf(“400\n”);
Tambahnode(&root,nil=100);
Tambahnode(&root->left,nil=90);
Tambahnode(&root->left->left,nil=80);
Tambahnode(&root->left->left->left,nil=70);
Tambahnode(&root->right,nil=200);
Tambahnode(&root->right->right,nil=300);
Tambahnode(&root->right->right->right,nil=400);
printf(“\nProgram By: AH. HANDOYO[1412110156]”);
printf(“\nTampilan secara PreOrder : “);
preorder(root);
printf(“\nTampilan secara InOrder : “);
inorder(root);
printf(“\nTampilan secara PostOrder : “);
postorder(root);

}

Output Program :

Exchange sort

•         Sangat mirip dengan Bubble Sort

•         Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort

•         Pebedaan : dalam hal bagaimana membandingkan antar elemen-elemennya.

•         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.

Exchange sort 2

Selection sort

•         Merupakan kombinasi antara sorting dan searching

•         Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.

•         Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).

•         Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

HOMEDAFTAR ISITUKAR LINK

Heap Sort

 Heap Sort adalah sebuah algoritma pengurutan yang paling lambat dari algoritma yang memiliki kompleksitas O(n log n). Tetapi tidak seperti algoritma Merge Sort dan Quick Sort, algoritma Heap Sort tidak memerlukan rekursif yang besar atau menggunakan banyak tabel (array). Oleh karena itu, Heap Sort adalah pilihan yang baik untuk sebuah kumpulan data yang besar.

 Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap.

Algoritma ini dimulai dengan membangun sebuah array heap dengan membangun tumpukan dari kumpulan data, lalu memindahkan data terbesar ke bagian belakang dari sebuah tabel hasil. Setelah itu, array heap dibangun kembali, kemudian mengambil elemen terbesar untuk diletakkan di sebelah item yang telah dipindahkan tadi. Hal ini diulang sampai array heap habis.

Jadi secara umum, algoritma ini memerlukan dua buah tabel; satu tabel untuk menyimpan heap, dan satu tabel lainnya untuk menyimpan hasil. Walaupun lebih lambat dari Merge Sort atau Quick Sort, algoritma ini cocok untuk digunakan pada data yang berukuran besar.

Penerapan Algoritma Pengurutan Heap Sort

  Salah satu contoh penerapan algoritma pengurutan (sorting algorithm) heap sort adalah sebagai berikut: Misalkan terdapat suatu array bilangan bulat yang terdiri dari sepuluh buah anggota dengan nilai data 11, 9, 8, 27, 16, 25, 12, 13, 34, dan 43. Kita akan mengurutkan data diatas dengan menggunakan heapsort. Pertama-tama, array di atas dapat dipandang sebagai suatu Complete Binary Tree (CBT) sebagai berikut:

 
 Selanjutnya algoritma metoda heapify dilakukan dengan iterasi dari subtree node ke-4, ke-3, dan seterusnya berturut-turut hingga mencapai root (akar). Iterasi dilakukan mulai dari node ke-4 karena N/2 dalam contoh di atas adalah 5. Dan elemen kelima dari array memiliki nilai indeks 4 sebab indeks array biasanya diawali dari 0. Penerapan algoritma metoda heapify terhadap Complete Binary Tree (CBT) pada contoh di atas menghasilkan operasi-operasi pertukaran sebagai berikut:

1. Subtree node ke-4: pertukaran 16 dengan 43

2. Subtree node ke-3: pertukaran 27 dengan 34

3. Subtree node ke-2: pertukaran 8 dengan 25

4. Subtree node ke-1: pertukaran 9 dengan 43, lalu pertukaran 9 dengan 16

5. Subtree node ke-0: pertukaran 11 dengan 43, lalu pertukaran 11 dengan 34, serta akhirnya pertukaran 11 dengan 27 Perubahan-perubahan (pertukaran) tersebut dapat digambarkan sebagai berikut:

 Semua perubahan di atas terjadi dalam array yang bersangkutan, sehingga pada akhirnya diperoleh tree terakhir yang merupakan heap tree. Sementara itu, dalam iterasi yang melakukan/menerapkan algoritma metoda remove( ) dan algoritma metoda reheapify() akan terjadi pemrosesan berikut:

1. Setelah 43 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 43, maka terjadi reheapify: penukaran 9 dengan 34, 9 dengan 27, dan 9 dengan 13.

dan data yang telah terurut adalah 43.

2. Setelah 34 di-remove dan 11 menggantikan posisi yang ditinggalkan oleh 34, maka terjadi reheapify: penukaran 11 dengan 27, dan 11 dengan 16.

dan data yang telah terurut adalah 34, 43.

3. Setelah 27 di-remove dan 9 menggantikan posisi yang ditinggalkan oleh 27, maka terjadi reheapify: penukaran 9 dengan 25, dan 9 dengan 12.

dan data yang telah terurut adalah 27, 34, 43.

4. Demikian seterusnya dilakukan algoritma metoda remove dan algoritma metoda reheapify hingga tidak ada lagi node yang tersisa. Dan pada akhirnya akan didapatkan hasil data yang telah terurut adalah 8, 9, 11, 12, 13, 16, 25, 27, 34, 43.

Program Heap Sort & Penjelasannya

<#include <>

void restoreHup(int*,int); // pemanggilan fungsi void restoreHup

void restoreHdown(int*,int,int); //pemanggilan fungsi void restoreHdown

void main()

{ // pembuka void main

int a[20],n,i,j,k; // mendeklarasikan bahwa a[20] ,n,i,j,k adalah integer

printf(" Masukkan jumlah element : ");// untuk menampilkan kelayar perintah memasukkan jumlah element

scanf("%d",&n); // untuk mengidentifikasikan nilai yang dimasukkan melalui keyboard

printf(" Masukkan element : "); //untuk menampilkan kelayar perintah untuk memasukkan element

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

scanf("%d",&a[i]); // untuk mengidentifikasi array a

restoreHup(a,i); // a , i dalam fungsi restoreHup

} // penutup fungsi for

j=n; // nilai j sama dengan n

for(i=1;i<=j;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

{ // pembuka fungsi for

int temp; // temp sebagai integer

temp=a[1]; // temp sama dengan nilai array a yang pertama

a[1]=a[n]; // nilai array a yg ke 1 sama dengan array a yang ke n

a[n]=temp; // nilai array a yang ke n sama dengan nilay temp

n--; // nilai n selalu berkurang 1

restoreHdown(a,1,n); // a , 1, n dalam fungsi restoreHdown

} // penutup fungsi for

n=j; // n sama dengan nilai j

printf(" Here is it... "); // untuk menampilkan perintah ke dalam layar

for(i=1;i<=n;i++) //funsi for dimana jika ketentuan untuk i terpenuhi maka progran di bawahnya akan dijalankan

printf("%4d",a[i]); // untuk menampilkan nilai array ke i ke layar

} // penutup void main

void restoreHup(int *a,int i) // fungsi void restore Hup

{ // pembuka fungsi foid restoreHup

int v=a[i]; // v sama dengan nilai array a yang ke i

while((i>1)&&(a[i/2]

{ // pembuka fungsi while

a[i]=a[i/2]; // nilai array a yang ke i sama dengan nilai array a yang ke i/2

i=i/2; // nilai i sama dengan nilai i/2

} //penutup fungsi while

a[i]=v; // nilai array a yang ke i sama dengan nilai v

} // penutup fungsi while

void restoreHdown(int *a,int i,int n) // fungsi void restoreHdown

{ // pembuka fungsi void restoreHdown

int v=a[i]; // v sama dengan nilai array a yang ke i sebagai integer

int j=i*2;// nilai j sama dengan i kali 2 ialah integer

while(j<=n) // fungsi while akan dijalankan bila ketentuannya terpenuhi

{ // pembuka fungsi while

if((j

j++; // nilai j akan selalu tambah 1

if(a[j]

break;

a[j/2]=a[j]; // nilai array a yang ke j/2 sama dengan nilai array a yang ke j

j=j*2; // nilai j sama dengan nilai j*2

}// penutup fungsi while

a[j/2]=v;// nilai array a yang ke j/2 sama dengan v

}// penutup fungsi void restorehdown

//Suatu program untuk mengimplementasikan Heap Sort>

Hasil Program diatas :

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 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 digunakansebagai pivot point (poin poros). (Biasanyaelemen yang paling kiri.)  

3.)    Bagi struktur data menjadi dua bagian satudengan elemen-elemen yang lebih  besar daripada pivot point, dan yang lainnya denganelemen-elemen yang lebih kecil dari pada pivot point. 4.

4.)    Ulangi algoritma secara rekursif terhadapkedua paruh struktur data.

Contoh Program Quick Sort :

#include<iostream.h>

 #include<iomanip.h>

void quickSort(int[], int);

void q_sort(int[], int, int);

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

quickSort (NumList,8);

cout<<"Data Setelah Diurutkan: \n";

for (int iii=0; iii<8; iii++)

cout<<"setw(3)"<<NumList[iii]<<endl<<endl;

}

void quickSort(int numbers[], int array_size)

{

q_sort(number, 0, array_size-1);

}

void q_sort(int number[], int left, int right)

{

int pivot, l_hold, r_hold;

 l_hold=left;

r_hold=right;

pivot = numbers[left];

while (left<right)

{

while((numbers[right]>=pivot || (left<right))

right--;

if(left != right)

{

numbers[left]=numbers[right];

left++;

}

while ((numbers[left] <=pivot) && (left<right))

left++;

if (left != right)

{

number[right]=numbers[left];

right--;

}

}

numbers[left]=pivot;

pivot=left;

left=l_hold;

right=r_hold;

if (left<pivot)

q_sort(numbers, left, pivot-1);

if (right>pivot)

q_sort(numbers, pivot+1, right);

}

Script program yang benar :

/*Quick Sort*/

#include<iostream>

#include<iomanip>

#include <conio.h>

using namespace std;

void quickSort(int[], int);

void q_sort(int[], int, int);

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

quickSort (NumList,8);

cout<<"Data Setelah Diurutkan: \n"; for (int iii=0; iii<8; iii++) cout<<setw(3)<<NumList[iii]<<endl<<endl;

}

void quickSort(int numbers[], int array_size)

{

q_sort(numbers, 0, array_size-1);

}

void q_sort(int numbers[], int left, int right)

{

int pivot, l_hold, r_hold;

l_hold=left;

 r_hold=right;

pivot = numbers[left];

 while (left<right)

{

while((numbers[right]>=pivot) &&(left<right))

right--;

if(left != right)

{

numbers[left]=numbers[right];

left++;

}

while ((numbers[left] <=pivot) && (left<right))

left++;

if (left != right)

{

numbers[right]=numbers[left];

right--;

}

}

numbers[left]=pivot;

pivot=left;

left=l_hold;

right=r_hold;

if (left<pivot)

q_sort(numbers, left, pivot-1);

if (right>pivot)

q_sort(numbers, pivot+1, right);

}

Output Program :

Algoritma :

1.       Mulai.

2.       Membaca file header.

3.       Membaca fungsi metode quick sort.

4.       Membaca fungsi numlist [8], temp.

5.       Membaca perulangan.

6.       Pemanggilan fungsi quicksort.

7.       Cetak hasil.

8.       Tampilan data sebelum diurutkan.

9.       Membaca fungsi quicksort (numlist,8).

10.   Cetak hasil.

11.   Tampilan data setelah diurutkan.

12.   Selesai.

Deskripsi :

Program diatas menggunakan metode quick sort yang sistematika quick sort adalah pertama jika struktur data terdiri dari 1/0 maka kembalikan struktur data apa adanya, jangan diubah. kemudian ambil sebuah elemen yang akan digunakan sebagai pivot biasanya elemen paling kiri. bagi struktur data menjad 2  bagian, satu dengan elemen yang lebih besar daripada pivot, dan lainnya dengan elemen yang lebih kecil dengan pivot. ulangi terus secara rekursif terhadap kedua  pruh struktur tersebut.

4.      Merge Sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebihberarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelumkemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut :

1.)    Sebuah list yang kecil membutuhkan langkahyang lebih sedikit untuk pengurutan daripadasebuah list yang besar.

2.)    Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yanglebih sedikit daripada membentuk sebuah listterurut dari dua buah list tak terurut. Contoh: hanya diperlukan satu kali traversal untukmasing-masing list  jika keduanya sudah terurut.

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

1.)    Bagi list yang tak terurut menjadi dua samapanjang atau salah satunyalebih  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.

Algoritma :

Algoritma Merge sort sebenarnya sederhana[9]: bagi larik menjadi dua sama besar, urutkan bagian pertama, urutkan bagian kedua, lalu gabungkan.

Sebagai contoh, jika terdapat data berupa 38, 27, 43, 3, 9,82, dan 10 maka ilustrasi pengurutannya adalah sebagai berikut:

Pseudocodeuntuk merge sort[6] adalah sebagai berikut:

mergesort(data)

if data memiliki setidaknya dua

elemen

mergesort (separuh kiri dari data);

mergesort (separuh kanan dari data ;

merge (kedua bagian ke dalam suatu urutan);

Sedangkan pseudocodeuntuk merge itu sendiri adalah:

merge (arrayl, pertama, terakhir)

tengah = (pertama + terakhir) / 2;

il = 0;

i2 = pertama;

i3 = tengah + 1;

while kedua sub larik dari array1 memiliki elemen

if arrayl[i2] < arrayl[i3]

temp[il++] = arrayl[i2++];

else

temp[il++] = arrayl[i3++];

masukkan ke dalam temp sisa elemen dari arrayl;

masukkan ke arrayl isi dari temp;

Contoh program merge sort :

void merge(int kiri,int tengah, int kanan)

{

int h,i,j,b[50],k;

h=kiri;

i=kiri;

j=tengah+1;

while((h<=tengah)&&

(j<=kanan))

{

if(bilangan[h]<=

bilangan[j])

{

b[i]=bilangan[h];

h++;

}

else

{

b[i]=bilangan[j];

j++;

}

i++;

}

if(h>tengah)

{

for(k=j;k<=kanan;k++)

{

b[i]=bilangan[k];

i++;

}

}

else

{

for(k=h;k<=tengah;k++)

{

b[i]=bilangan[k];

i++;

}

}

else

{

for(k=h;k<=tengah;k++)

{

b[i]=bilangan[k];

i++;

}

}

for(k=kiri;k<=kanan;k++)

bilangan[k]=b[k];

}

void merge_sort(int kiri,

int kanan)

{

int tengah;

if(kiri<kanan)

{

tengah=(kiri+kanan)/2;

merge_sort(kiri,tengah);

merge_sort(tengah+1,

kanan);

merge(kiri,tengah,

kanan);

}

}

Output program :

Shell sort (pembagian insertion)

   

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 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 jarak yang sama seperti diatas. Demikianseterusnya 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 :

                      

Program Shell Sort sebagai berikut :

/*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 shell 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. Algroitma  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 aka nada 4 data , misalnya 6 9 7 4 maka sistematika kerjanya adlaah 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.

REFERENSI:

https://siraits.files.wordpress.com/2008/04/algodanstrukturdata8.ppt (Sabtu, 11 April 2015 pukul 12.55 WIB)

http://bekompaa.blogspot.com/2013/04/contoh-laporan-dan-makalah-tentang-heap.html (Senin, 13 April 2015 pukul 11.18 WIB)

http://informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik08.pdf (Senin, 13 April 2015 pukul 11.51 WIB)

http://kael9001.blogspot.com/2013/02/bubble-sort.html (Senin, 13 April 2015 pukul 11.43 WIB)

http://nurjannahfitri.blogspot.com/2015_04_01_archive.html (Senin, 13 April 2015 pukul 12.02 WIB)