NeroPendragon

Tree sort

Merupakan proses dua langkah. Pertama elemen dimasukkan kedalam suatu binary search tree. Kemudian, elemen didapatkan kembali, dalam susunan terurut menggunakan suatu inorder traversal.

Dalam metode ini pengurutan dilakukan dengan membentuk pohon. Aturan dalam membentuk pohon adalah : informasi yang tersimpan pada cabang kiri nilainya selalu lebih kecil dari simpul akar dan informasi yang tersimpan dalam simpul akar nilainya selalu lebih kecil dari yang tersimpan pada cabang kanan. Jika pohon disusun dengan cara ini, maka pada saat dilakukan kunjungan inorder akan diperoleh informasi yang dalam keadaan terurut naik berdasarkan RLO, atau urut turun berdasarkan RLO.

Gambar 3.2.1 Contoh pohon treesort

 Gambar diatas menunjukkan contoh pohon yang apabila dibaca secara inorder akan menghasilkan informasi dalam keadaan urut. Dari pohon diatas jika dilakukan kunjungan secara inorder dan RLO, akan diperoleh informasi ‘ABCDEFGHIJKLMNOPQ’; dan dengan menggunakan RLO akan diperoleh informasi ‘QPONMLKJIHGFEDCBA’

       struct Node {

           int item; / / Data dalam node ini.

           Node *kiri; / / Pointer kesubtreekiri.

           Node * kanan; / / ​​Pointer kesubtreekanan.

       }

 Berikut algoritma nya :

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

typedefstruct node{

int data;

node *left;

node *right;

};

node *root=NULL;

void Tambahnode(node **root, intisi) {

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

}

}

voidinorder(node *root) {

if(root !=NULL) {

inorder(root->left);

printf(“%i, “, root->data);

inorder(root->right);

}

}

voidpostorder(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(“\nTampilansecaraPreOrder : “);

preorder(root);

printf(“\nTampilansecaraInOrder : “);

inorder(root);

printf(“\nTampilansecaraPostOrder : “);

postorder(root);

}

  Exchange short

           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 denganelemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu.  Jadi ada elemen yang selalu menjadi elemen pusat (pivot).

•          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

Prosedur exchange:

Selection short

•         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 dilakukanpada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Prosedur Selection short

HeapSort

           
          Seperti treesort, heapsort adalah dua langkah proses. Pertama, data ditaruh kedalam heap(tumpukan), dan, kedua, data diekstrak dari heapdalam susunan terurut. Heapsort merupakan saudara dari selection sort karena algoritma keduanya select (memilih ) dan kemudian menukarkannya kedalam susunan terurut elemen yang lebih besar secara berturut-turut. Heapsort menggunakan struktur data yang lebih efisien daripada selection sort. Tetapi selection sort akan menjadi lebih cepat untuk satu set elemen yang kecil.

Heapsort akan dibangun dengan algoritma heapsort. Pemanggilan kembali dalam organisasi heap menempatkan elemen terkecil diatas, jika susunan elemen dari tumpukan disimpan sebagai elemen array r[1], r[2], …, r[n] kemudian elemen dengan kunci terkecilakan disimpan sebagai r[1]. Trik ini untuk menemukan elemen dengan kunci terbesar kedua. Akan diproses sebagai berikut :

Pertama, lintasankan data yang akan ditukar r[1] dan r[n] kemudian selidiki ke bawah r[1] dalam susunan r[1],…, r[n -1] sehingga r[1], …, r[n- 1] membentuk suatu tumpukan. Hasilnya bahwa r[n] adalah suatu list yang terurut dari deret satu dan elemen yang terkecil keduaadalah r[1]. Berikut gambarnya :

Algoritma

Procedure heapsort(n : integer);

Var j, k, temp: integer;

Begin

j := (n div 2) + 1;

while j > 1 do

begin

j := j – 1;siftdown(j,n)

yang diperlukan karena siftdown sering diaplikasikan untuk suatu heapyang lebih kecil dari n elemen.

           Dalam setiap langkah, elemen terkecil diambil ari bagian teratas heap dan dipindahkan ke list terurut. Suatu heap dibentuk dari elemen sisa yangPusat Pengembangan Pendidikan – Universitas Gadjah Mada 28 menggunakan prosedur siftdown. 

Proses kemudian diulangi.

(a) data yang akan diurutkan.

(b) konstruksi dari suatu heap.

Quick Sort (Metode Quick)

           Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962. Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar. Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut:

Mula-mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x.

          Implementasi secara non rekursif memerlukan dua buah tumpukan (stack) yang digunakan yang digunakan untuk menyimpan batas-batas subbagian. Pada prosedur ini menggunakan tumpukan yang bertipe record (struktur) yang terdiri dari elemen kiri (untuk mencatat batas kiri) dan kanan (untukmencatat batas kanan. Tumpukan dalam hal ini dideklarasikan sebagai array.

Algoritma quick sort non rekursif dapat dituliskan sebagai berikut :

1. Tumpukan[1].Kiri = 0

2. Tumpukan[1].Kanan = N-1

3. Selama ujung ≠ 0 kerjakan baris 4 sampai dengan 22

4. L = Tumpukan[ujung].Kiri

5. R = Tumpukan[ujung].Kanan

6. ujung = ujung – 1

7. Selama (R > L) kerjakan baris sampai 8 dengan 22

8. i = L

9. j = R

10. x = Data[(L + R) / 2]

11. Selama i <= j kerjakan baris 12 sampai dengan 14

12. Selama (Data[i] < x), i = i + 1

13. Selama (x < Data[j]), j = j – 1

14. Jika (i <= j) maka kerjakan baris 15 sampai dengan 17, jika tidak ke baris 11

15. Tukar Data[i] dengan Data[j]

16. i = i + 1

17. j = j –1

18. Jika (L < i) maka kerjakan baris 19 sampai dengan 21

19. ujung = ujung + 1

20. Tumpukan[ujung].Kiri = i

21. Tumpukan[ujung].Kanan = R

22. R = j

Di bawah ini merupakan prosedur yang menggunakan metode quick dengan non rekursi:

void QuickSortNonRekursif(int N)

{

const M = MaxStack;

struct tump

{

int Kiri;

int Kanan;

}

Tumpukan[M];

int i, j, L, R, x, ujung = 1;

Tumpukan[1].Kiri = 0;

Tumpukan[1].Kanan = N-1;

while (ujung!=0)

{

L = Tumpukan[ujung].Kiri;

R = Tumpukan[ujung].Kanan;

ujung--;

while(R > L)

{

i = L;

j = R;

x = Data[(L+R)/2];

while(i <= j)

{

while(Data[i] < x)

i++;

while(x < Data[j])

j--;

if(i <= j)

{

Tukar(&Data[i], &Data[j]);

i++;

j--;

}

}

if(L < i)

{

ujung++;

Tumpukan[ujung].Kiri = i;

Tumpukan[ujung].Kanan = R;

}

R = j;

}

}

}

Metode Quick Sort Rekursif

        Algoritma quick Rekursif dapat dituliskan sebagai berikut :

1. x = Data[(L + R) / 2]

2. i = L

3. j = R

4. Selama ( i <= j) kerjakan baris 5 sampai dengan 12

5. Selama (Data[i] < x) kerjakan i = i + 1

6. Selama (Data[j] > x) kerjakan j = j – 1

7. Jika (i <= j) maka kerjakan baris 8 sampai 10; jika tidak kerjakan baris 11

8. Tukar Data[i] dengan Data[j]

9. i = i + 1

10. j = j –1

11. Jika (L < j) kerjakan lagi baris 1 dengan R = j

12. Jika (i < R) kerjakan lagi baris 1 dengan L = i

Dibawah ini merupakan prosedur yang menggunakan metode quick dengan rekursi:

void QuickSortRekursif(int L, int R)

{

int i, j, x;

x = data[(L+R)/2];

i = L;

j = R;

while (i <= j)

{

while(Data[i] < x)

i++;

while(Data[j] > x)

j--;

if(i <= j)

{

Tukar(&Data[i], &Data[j]);

i++;

j--;

}

}

if(L < j)

QuickSortRekursif(L, j);

if(i < R)

QuickSortRekursif(i, R);

}

Merge Sort (Metode Penggabungan)

           Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut :

          Mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data pertama (T1) adalah sebagai berikut :

3 11 12 23 31

Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :

9 15 17 20 35

           Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya

sehingga didapat hasil sebagai berikut :

3 9 11 12 15 17 20 23 31 35

Algoritma penggabungan dapat dituliskan sebagai berikut :

 i = 0

 j = 0

 J3 = 0

4. Kerjakan baris 5 sampai dengan 7 selama (i < J1) atau (j < J2)

 J3 = J3 + 1

 Jika (T1[i] < T2[j]) maka T3[J3] = T1[i], i = i + 1

 Jika (T1[i] >= T2[j]) maka T3[J3] = T2[j], j = j + 1

 Jika (i > J1) maka kerjakan baris 9, jika tidak kerjakan baris 15

 i = j

 Selama (i < J2) kerjakan baris 11 sampai dengan 13

 J3 = J3 + 1

 T3[J3] = T2[i]

 i = i + 1

 Selesai

 j = i

 Selama (j < J1) kerjakan baris 17 sampai dengan 19

 J3 = J3 + 1

 T3[J3] = T1[j]

 j = j + 1

Di bawah ini merupakan prosedur penggabungan dua kumpulan data yang sudah dalam keadaan urut:

void MergeSort(int T1[],int T2[],int J1,int J2, int T3[],int *J3)

{

int i=0, j=0;

int t=0;

while ((i<J1)||(j<J2))

{

if(T1[i]<T2[j])

{

T3[t] = T1[i];

i++;

}

else

{

T3[t] = T2[j];

j++;

}t++;

}

if(i>J1)

for(i=j; i<J2; i++)

{

T3[t] = T2[i];

t++;

}

if(j>J2)

for(j=i; j<J1; j++)

{

T3[t] = T1[j];

t++;

}

*J3 = t;

}

Shell Sort (Metode Shell)

          Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan. Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :

          Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2).

          Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).

Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :

 Jarak = N

 Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9

 Jarak = Jarak / 2. Sudah = false

 Kerjakan baris 4 sampai dengan 8 selama Sudah = false

 Sudah = true

 j = 0

 Selama (j < N – Jarak) kerjakan baris 8 dan 9

 Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],

   Data[j + Jarak].

   Sudah = true

 j = j + 1

Di bawah ini merupakan prosedur yang menggunakan metode Shell:

void ShellSort(int N)

{

int Jarak, i, j;

bool Sudah;

Jarak = N;

while(Lompat > 1)

{

Jarak = Jarak / 2;

Sudah = false;

while(!Sudah)

{

Sudah = true;

for(j=0; j<N-Jarak; j++)

{

i = j + Jarak;

if(Data[j] > Data[i])

{

Tukar(&Data[j], &Data[i]);

Sudah = false;

} } } } }

 Mana yang terbaik?

Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi, bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara

lain:

1. Banyak data yang diurutkan.

2. Kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki.

3. Tempat penyimpanan data.

Referensi :
http://lecturer.ukdw.ac.id/anton/download/TIstrukdat3.ppt
http://www.mdp.ac.id/materi/2012-2013-2/sp244/111070/SP244-111070-950-18.pdf
http://ianeceper.blogspot.com