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

       
       SORTING bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah.

Pada umumnya terdapat dua jenis pengurutan :

- Ascending (Naik).

- Descending (Turun).

Contoh :

Data                             : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);

Data Acak                    : 22 10 15 3 8 2

Terurut Ascending       : 2 3 8 10 15 22

Terurut Descending     : 22 15 10 8 3 2

Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.

Beberapa metode yang sudah umum digunakan diantaranya adalah :

1. Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

Insertion sort

         Teknik sorting ini dibuat dengan cara menyisipkan atau memasukkan satu-persatu, bila kita akan mengurutkan data, kemudian ingin menyisipkan suatu data maka data tersebut akan otomatis masuk dimana dia berada. Pengurutan dilakukan dengan cara membandingkan data ke – i dengan data berikutnya, (dimana i dimulai dari data di index ke 1 sampai dengan data terakhir). Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya, dan saat ada elemen yang disispkan, maka elemen-elemen lainnya akan bergeser kebelakang.

Contoh procedure insertion sort ascending :

Procedure asc_insert;

Var

i, j, temp : byte;

begin

     for i := 2 to max do

          begin

               temp := data [i] ;

                    j :=i-1;

                    while (data [j] > temp ) and (j>0) do

          begin

               data [j+1] := data [j];

               dec (j) ;

          end;

     data [j+1] := temp ;

   end;

end;

Tree sort

         Metode sorting dengan cara membangun pohon biner dengan menampilkan 3 hasil output: PreOrder, InOrder, dan PostOrder. Konsep dasar dari tree sort adalah sebagaimana sebuah pohon, ada akar, batang, ranting, daun, dan sebagainya. Dalam tree sort ada istilah akar atau root dan daun atau leaf.

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.

            }

2. Pengurutan berdasarkan perbandingan (compirasion-based sorting)

Bubble sort

          Teknik ini dilakukan dengan pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data. Membandingkan elemen yang sekarang dengan elemen yang berikutnya, jika elemen sekarang>elemen berikutnya, maka tukar.

Contoh procedure tukar data:

Procedure asc_buble (var data :array; jmldata:integer);

Var

i,j : integer;

begin

     for i := 2 to jmldata do

          for j :=jmldata downto i do

               if data [j] <  data [j-1] then

               tukardata (data[j], data [j-1] ) ;

end;

Exchange sort

          Teknik sorting ini dibuat dengan cara pola membawa nilai terbesar menjadi nilai index terakhir array. Jadi sistem ini melakukan pengecekan nilai 1 dengan 2, lalu 2 dengan 3 sampai dengan data terakhir, bila nilai index yang lebih kecil lebih besar maka akan dilakukan pertukaran. Proses ini dilakukan hingga jumlah data dikurangi 1 atau sampai program tidak melakukan pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat. Exchange sort itu sangat mirip dengan buble sort. Bahkan banyak yang mengatakan bahwa exchange sort sama dengan buble sort.

Contoh procedure exchange sort :

Procedure asc_buble (var data :array; jmldata:integer);

Var

i,j : integer;

begin

     for i := 2 to jmldata do

          for j :=jmldata downto i do

          if data [j] <  data [j-1] then

               tukardata (data[j], data [j-1] ) ;

end;

perbedaannya terdapat dalam hal bagaimana membandingkan antar elemen-elemennya:

3. Pengurutan berdasarkan prioritas (priority queue sorting method)

Selection sort

          Teknik sorting ini dibuat dengan cara melakukan pengecekan satu-persatu, bila kita akan mengurutkan secara ascending maka kita lakukan pengecekan nilai tempat yang pertama (index pertama pada array) kita bandingkan semua nilai yang ada kita cari nilai minimalnya, lalu simpan index/ letak nilai minimum itu ditemukan, setelah pengecekan selesai tukar index awal pengecekan dengan nilai minimum yang telah simpan tadi. Proses ini dilakukan terus-menerus sampai pada pengecekan index terakhir minimal dengan index terakhir, beda dengan streith selection sort adalah dengan teknik ini melakukan pertukaran nilai lebih sedikit, hanya jumlah data-1 pertukaran. Jadi waktu untuk melakukan proses sorting lebih cepat. Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen yang lebih kecil, maka dicatat posisinya. Namun jika ditemukan elemen terkecil, maka dicatat posisinya dan kemudian di TUKAR dengan elemen sekarang.

Contoh procedure selection sort secara ascending :

Procedure asc_selection;

Var

Min,pos : byte;

Begin

     For i:= 1 to max-1 do

          Begin

               Pos :=i ;

               For j := i+1 to max do

               If data [j] < data [pos] then pos :=j;

                    If i <> pos then tukardata (data[i] , data[pos] );

               End;

End;

Heap sort (menggunakan tree)

          Teknik sorting ini dibuat dengan versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar tapi menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi unsur (atau terkecil) terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu, dan ini juga merupakan kompleksitas kasus terburuk.

          HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n. Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue.

          Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut. Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.

Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut. Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja. Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil.

Heap Sort memasukkan data masukan ke dalam struktur data heap. Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut.

Algoritma untuk heap sort :

function heapSort(a, count) is

input: sebuah larik tidak terurut a dengan panjang length

(pertama letakkan a dalam max-heap) heapify(a, count)

end := count -1

while end > 0 do

remove ( )

reheapify ( )

end := end – 1

4. Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

Quick sort

          Teknik sorting ini dibuat dengan cara yang menggunakan partisi. Pada teknik ini, data dibagi menjadi dua bagian, yaitu data disebelah kiri partisi selalu lebih kecil dari data disebelah kanan. Namun data pada kedua patisi belum terurut, sehingga untuk mengurutkannya, proses pengurutan dilakukan pada kedua partisi secara terpisah. Selanjutnya, data di sebelah kiri dan kanan dipartisi lagi. Merupakan proses penyusunan elemen yang membandingkan suatu elemen (pivot) denan elemen yang lain, dan menyusunnya sedemikian rupa sehingga elemen –elemen lain yang lebih kecil dari pivot terletak disebelah kiri pivot. Dan elemen yang lebih besar dari pivot terletak disebelah kanan pivot.Dengan demikian akan terbentuk dua sublist, yang terletak disebelah kanan dan kiri pivot.Lalu pada sublist kiri dan kanan itu kita anggap sebuah list baru, dan kita kerjakan proses yang sama seperti yang sebelumnya.Demikian seterusnya sampai tidak terdapat sublist lagi.

Contoh procedure quick sort secara ascending :

Procedure asc_quick (l , r :integer) ;

Var

i, j : integer;

begin

     if l < r then

     begin

          i := l ;    j := r+1;

          repeat

               repeat inc (i) until data [i] >= data [l] ;

               repeat dec (j) until data [j] <= data [l] ;

          if i<j then tukardata (data [i], data [j]) ;

          until i>j ;

               tukardata (data [l], data [j] );

          asc_quick (l, j-1);

          asc_quick (j+1, r);

     end;

end;

Merge sort

          Teknik sorting ini dibuat dengan cara mengambil keuntungan dari kemudahan penggabungan daftar sudah disortir ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu: 1 dengan 2, kemudian 3 dengan 4) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dari dua ke daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir.

          Algoritma pengurutan data mergesort dilakukan dengan menggunakan cara divideandconquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

          Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode mergesort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

          Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Mergesort.

- Divide          : Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

- Conquer       : Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif

- Kombinasi   : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan

          Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

          Contoh penerapan atas sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

- Pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}

- Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}

- Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)

- Langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya

- {1, 2} ↔{3, 4, 9} dan {5}

- {1, 2, 3} ↔ {4, 9} dan {5}

- {1, 2, 3, 4}↔{9} dan {5}

- {1, 2, 3, 4, 5}↔{9} dan {null}

- {1, 2, 3, 4, 5, 9}↔{null}dan {null}

Contoh program sedehana merge sort :

Public class mergeSort{

Public static void main(String args [ ] ){

int i;

int array [ ] = {7,5,1,3,6,4,9,8};

System.out.println("\n\n Kelompok 3\n\n");

System.out.println(" Pengurutan dengan MergeSort\n\n");

System.out.println("Data Sebelum Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print( array[i]+"  ");

System.out.println( );

Merge Sort_srt(array,0, array.length - 1);

System.out.print("Data Setelah Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print(array[i]+"  ");

System.out.println();

    }

Public static void mergeSort_srt(int array[ ],int lo, int n){

 int low = lo;

int high = n;

if (low > = high)

    {return; }

int middle = (low + high) / 2;

mergeSort_srt(array, low, middle);

mergeSort_srt(array, middle + 1, high);

int end_low = middle;

int start_high = middle + 1;

while ((lo <= end_low) && (start_high <= high))

    {

if (array[low] < array[start_high]) {

low++; }

else {

int Temp = array[start_high];

            for (int k = start_high- 1; k > =low; k--)

                {array[k+1] = array[k]; }

array[low] = Temp;

low++;

end_low++;

start_high++;  }

        }

    }

5. Pengurutan berkurang menurun (diminishing increment sort method)

Shell sort (pengembangan insertion)

          Merupakan proses pengurutan data yang sebelumnya acak menjadi data yang terurut dengan cara menentukan jarak antar elemen yang akan dibandingkan. Teknik sorting ini dibuat dengan cara meningkatkan atas bubble sort dan insertion sort dengan menggerakkan keluar dari elemen-elemen memesan lebih dari satu posisi pada suatu waktu. Salah satu implementasi dapat digambarkan sebagai mengatur urutan data dalam array dua dimensi dan kemudian menyortir kolom baru array menggunakan insertion 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. Kemudian 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.

Berikut ini merupakan Procedure ShellSort pada Pascal :

Procedure Shell(Var Temp : Data; JmlData : Integer);

Var I,J, Jarak : Integer;

Begin

     Jarak := JmlData Div 2;

     While Jarak > 0 Do

          Begin

               For I:=1 To JmlData-Jarak Do

                    Begin

                         J := I + Jarak;

                         If Temp[I] > Temp[J] Then

                              SWAP(Temp[I], Temp[Lok]);

                    End;

               Jarak := Jarak Div 2;

          End;

End;

Nama    : Tri Atmojo Sulaiman
NIM      : A710140024
Prodi     : Pend TIK

Referensi :

http://puguhjayadi.blogspot.com/2013/05/tree-sort-c.html

https://itprogrammingandlinux.wordpress.com/2011/05/22/buble-insertion-selection-shell-maxmin-quick-merge-sort/

http://arraydalamprogram.blogspot.com/2010/03/heap-sort.html

http://populeritas.blogspot.com/2013/01/metode-pengurutan-merge-sort.html