METODE SORTING

Posted by : Unknown Minggu, 05 April 2015

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;

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;

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;

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