SORTING (PENGURUTAN)

SORTING (PENGURUTAN) Pengantar Sorting secara umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting merupakan satu dari banyak pekerjaan komputer yang dilakukan, yang diteliti secara luas, dan memiliki banyak algoritma yang berbeda yang dibangun. Sorting (mengurutkan) data memiliki dampak yang sangat penting dalam pencarian. Data yang tidak terurut harus dicari secara normal menggunakan suatu pembacaan sekuensial (sequential scan) dari semua data. Data yang telah terurut membiarkan dirinya untuk dicari menggunakan teknik pencarian yang sederhana. Secara umum ada 2 jenis sorting, yaitu secara Ascending (terurut naik) dan Descending (terurut turun). Dalam hal pengurutan data yang bertipe string atau char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (collating sequence) seperti yang dinyatakan dalam tabel ASCII. Tujuan pengurutan data adalah untuk mempermudah pencarian data. Pengurutan data menjadi sesuatu yang penting dalam ilmu komputer karena waktu yang diperlukan untuk melakukan proses pengurutan perlu dipertimbangkan. Data yang akan diurutkan tentu sangat bervariasi baik dalam hal banyak data maupun jenis datanya. Sayangnya, tidak ada satu algoritma yang 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 : banyak data yang akan diurutkan, kapasitas pengingat apakah mampu menyimpan semua data yang dimiliki, dan tempat penyimpanan data. Keuntungan yang diperoleh dari data yang sudah terurut adalah data mudah dicari, dibetulkan, disisipi atau dihapus. Dalam keadaan terurut data dapat dengan

mudah

dicek

bila

hilang.

Pengurutan

juga

digunakan

dalam

mengkompilasi program komputer jika tabel-tabel simbol harus dibentuk, dan

Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 1

juga memegang peran penting untuk mempercepat proses pencarian data yang harus dilakukan berulang kali. Ada dua kategori besar yang dihubungkan dengan sorting, yaitu Internal Sorting ( Pengurutan Internal ) dan External Sorting ( Pengurutan Eksternal ). Dalam Internal Sorting jumlah data yang akan diurutkan cukup kecil sehingga seluruh proses dapat dibawa keluar ke Random Access Memory dari komputer. Sedangkan pada External Sorting terlalu banyak data untuk diijinkan dalam Internal Sorting. Data disimpan dalam suatu peralatan Secondary Storage.

Sort the Data

Internal Sorting

External Sorting

Gambar 1.1 Pengurutan data

1. Pengurutan Internal (Internal Sorting) Algoritma Internal Sorting seringkali mengklasifikasikan berdasarkan jumlah dari pekerjaan yang diminta untuk mengurutkan urutan elemen. Banyaknya pekerjaan mengarah pada dua operasi dasar dari sorting : membandingkan dua elemen dan memindahkan suatu elemen dari satu tempat ke tempat lainnya. Teknik internal sorting yang utama dibagi ke dalam 3 kategori dengan tanggung jawab ke pekerjaan yang dibutuhkan untuk mengurutkan suatu urutan dari n elemen-simple sort, advanced sort dan radix sort. Kategori tersebut tergambar sebagai berikut :


Internal Sorting

Simple Sort Technique O(n2)

Advanced Sort Technique O(n log2n)

Radix Sort O(k x n)

Gambar 1.2 Pengurutan internal

1.1. TEKNIK

PENGURUTAN

SEDERHANA

(SIMPLE

SORT

TECHNIQUES) 1.1.1 Selection Sort ( Metode Seleksi ) Operasi dasar dalam suatu selection sort adalah seleksi dari elemen yang terkecil (atau yang terbesar) dari urutan suatu elemen. Gambar 2.1 berikut akan menggambarkan proses untuk suatu urutan dari lima integer.

Gambar 2.1 Ilustrasi Selection sort Pada gambar diatas, integer yang diketahui dapat diurutkan diawal masing-masing langkah adalah yang dibold.

Gambar 2.1 (a) memperlihatkan lima integer yang merupakan input untuk Selection Sort. Integer terkecil, 45, dipilih dan ditukar dengan integer pertama, 390. Hal ini akan menghasilkan list pertama yang telah


diurutkan seperti yang terlihat pada gambar 2.1 (b). integer yang diurutkan di tampilkan dengan bold. Berikutnya, integer terkecil kedua dalam list tadi dipilih dan ditukarkan dengan integer kedua dalam list, maka akan menghasilkan list yang terurut kedua seperti tampak dalam gambar 2.1 (c). Transisi dari gambar 2.1 (c) ke gambar 2.1 (d) dilakukan dengan memilih integer terkecil diantara ketiga integer terakhir dalam list. Kemudian elemen tersebut ditukarkan dengan integer ketiga dalam urutan. Hasilnya seperti yang terlihat dalam gambar 2.1 (d), list terurut ketiga. Langkah terakhir adalah memilih integer terkecil diantara integer keempat dan kelima dan menukarkan integer tersebut dengan integer keempat. Setelah hal tersebut dilakukan maka akan tampak hasilnya seperti pada gambar 2.1 (e), seluruh list telah diurutkan.

Algoritma Procedure selectsort(var r:list; n: integer); Var j, k, small: integer; Begin If n > 1 Then begin For k := 1 to n – 1 do Begin Small := k; For j := k + 1 to n do If r[j] < r[small] Then small := j; Swap(r[k], r[small]) End End End;

Logika dari prosedur SelectSort adalah kekhususan dari algoritma pengurutan sederhana, yang terdiri atas loop luar (outer loop) dan loop dalam (inner loop). Dalam prosedur SelectSort masing-masing diimplementasikan menggunakan Pascal untuk membangunnya. Inner loop dieksekusi mengikuti nomor waktu :


(n–1)+(n–2)+…+1=

1 n(n-1) = O(n2) 2

Outer loop dieksekusi sebanyak n-1 kali. Masing-masing eksekusi dari inner loop memerlukan satu perbandingan dan satu nomor yang tidak diketahui. Masing-masing eksekusi dari outer loop memerlukan satu perubahan. Total usha yang dilakukan : Perubahan = n – 1 Perbandingan = ½ n( n - 1 )

Yang perlu diperhatikan bahwa usaha yang diperlukan, seperti yang diukur oleh perbandingan dan perubahan, adalah pengurutan independen dari data yang diurutkan. Pada sisi negatif, SelectSort memerlukan O(n2) perbandingan tidak perduli bagaimana inisial data diurutkan. Sisi positifnya, ia tidak pernah memerlukan lebih dari O(n) perpindahan. Inilah yang membuat SelectSort sebagai metode yang baik untuk elemen yang besar (yang mahal untuk perpindahan) dengan pilihan pengurutan yang pendek (mudah untuk dibandingkan).

1.1.2 Exchange Sort ( Bubble Sort ) Operasi dasar dalam Exchange Sort adalah menukarkan sepasang elemen yang berdekatan. Metode ini mudah dipahami dan diprogram, tetapi tidak efisien. Secara keseluruhan proses pengurutan terdiri dari satu nomor yang melintasi data. Masing-masing lintasan dimulai pada suatu akhir dari array dan bekerja ke akhir yang lainnya. Masing-masing pasangan elemen yang keluar dari urutan ditukarkan. Gambar 2.2 berikut akan menggambarkan proses dari pengurutan secara ascending (dari kecil ke besar ).


Gambar 2.2 Ilustrasi Exchange Sort

Pada gambar diatas, lintasan pertama dibuat diatas data yang diberikan pertama seperti pada gambar 2.2 (a), 390 dibandingkan dengan 205; kemudian ditukarkan karena 205 lebih kecil. Hasilnya ditunjukkan dalam gambar 2.2 (b). kemudian 390 dibandingkan dengan 182, dan ditukarkan, karena 182 lebih kecil. Hasilnya seperti pada gambar 2.2 (c). Kemudian 390 dibandingkan dengan 45, dan ditukarkan, seperti pada gambar 2.2 (d). dan terakhir 390 dibandingkan dengan 235, dan ditukar. Hasil akhirnya seperti pada gambar 2.2 (e). Lintasan pertama memindahkan elemen terbesar ke posisi ke-n, membentuk list terurut pertama. lintasan kedua hanya memikirkan n-1 elemen. Lintasan kedua memindahkan elemen terbesar kedua ke posisi n – 1. Oleh karena itu lintasan ketiga hanya perlu memperhatikan n – 2 elemen. Secara umum setelah i melintas elemen terbesar ke i akan berada pada posisi terakhir, maka lintasan i + 1 hanya perlu memperhatikan i – 1 elemen. Dalam metode ini elemen yang kecil berpindh secara pelan, atau menggelembung, kearah atas. Oleh karena itu teknik pengurutan ini sering disebut dengan buble sort. Jika tidak ada perubahan yang terjadi selama satu lintasan yang melintasi data maka data diurutkan dan proses berhenti. Pengecekan dilakukan untuk melihat jika ada suatu perubahan yang terjadi pada lintasan dengan menggunakan variable boolean sorted. Pada awal setiap lintasan sorted diset


ke true. Jika terjadi suatu perubahan, kemudian sorted diset ke false (pada kenyatannya, sorted diset ke false setiap suatu perubahan terjadi., tidak hanya pertama kali).

Algoritma Procedure exchangesort(var r: list; n: integer); Var j, k, small: integer; Sorted: boolean; Begin K := n; sorted := false; While (k > 1) and (not sorted) do Begin Sorted := true; For j := 1 to k – 1 do If r[j] > r[j+1] Then begin Swap(r[j],r[j + 1]); Sorted := false End; K := k – 1 End; End;

Dalam prosedur exchangesort loop keluar diimplementasikan dengan satement while dalam Pascal, dan loop ke dalam dengan statement for dalam Pascal. Loop kedalam dieksekusi mengikuti nomor waktu : (n – 1) + (n – 2) + … + (n – ksorted) =

1 (2n - ksorted – 1) (ksorted) 2

dimana ksorted adalah nomor dari eksekusi dari loop keluar sebelum disana ada lintasan selama disana tidak ada perubahan. Loop kedalam memiliki satu perbandingan dan beberapa kali perubahan. Performa terbaik yang terjadi ketika ksorted adalah 1. Hal ini berarti tidak ada perubahan yang terjadi karena data asli telah diurutkan. Nomor perbandingan digunakan oleh prosedur exchange sort untuk menentukan :

1 (2n – 2)(1) = n – 1 = O(n2) 2 Performa terburuk yang terjadi ketika ksorted adalah n – 1. loop dalam kemudian dieksekusi mengikuti nomor waktu :


1 n(n – 1) = O(n2) 2 Ketika

menterjemahkan

eksekusi

loop

kedalam

pertukaran

dan

perbandingan, maka akan diperoleh : 

worst case (kejadian terburuk) pertukaran = ½ n(n-1) perbandingan = ½ n(n-1)



sorted data (data terurut) pertukaran = 0 perbandingan = n - 1 Suatu ExchangeSort memiliki dua kekurangan. Pertama, inner loop

mengandung suatu pertukaran yang memerlukan tiga perubahan. Dalam SelectSort tidak ada perpindahan dalam inner loop. Kedua, ketika suatu elemen dipindahkan, ia selalu dipindahkan ke posisi terdekat. Dalam SelectSort suatu elemen mungkin berpindah ke jarang yang jauh dan selalu berpindah ke

posisi yang diurutkan. Jadi ExchangeSort

algoritma

pengurutan terlambat.

1.1.3 Insertion Sort ( Metode Penyisipan Langsung ) Operasi dasar dalam insertion sort adalah penyisipan suatu elemen tunggal kedalam urutan elemen yang telah diurutkan sehingga hasil dari urutan masih tetap terurut. Gambar 2.3 mengilutrasikan proses yang terjadi pada 5 elemen, dengan setiap elemennya merupakan bilangann integer. Data yang digunakan untuk input merupakan array 5 bilangan integer (gambar 2.3(a)). Ketika elemen ke lima, 235, diperhatikan, … Dalam transisi dari gambar 2.3(a) ke gambar 2.3(b) terjadi penysisipan 45 ke dalam daftar elemen yang telah diurutkan. Sealama 45 kurang dari 235, penyisipan 45 merupakan puncak dari daftar. Sebagaimana ditampilkan dalam gambar 2.3(b), segmen yang terurutkan mempunyai panjang dua. Transisi dari gambar 2.3(b) ke gambar 2.3(c) diselesaikan dengan memasikkan 182 ke dalam daftar elemen yang telah diurutkan. Selama 182 Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 8

terletak diantara 35 dan 235, 182 disisipkan diantara 45 dan 235 dengan memindahkan 45 ke atas yang menciptakan suatu ruangan. Daftar subset yang terurut tersebut sekarang mempunyai panjang tiga. Gambar 2.3(d) diperoleh dengan menyisipkan 205 ke dalam daftar elemen yang telah diurutkan, dilakukan dengan memindahkan 45 dan 182 naik untuk menjadikan ruangan. Terakhir, gambar 2.3(e) diperoleh dengan memasukkan 390 ke dalam daftar elemen (dengan panjang empat) yang telah terurut. Gambar 2.3mengilustrasikan prosedur yang terdapat pada algoritma insertion sort. Algoritma melakukan penyisipan dengan melakukan dibawah elemen untuk disisipkan. Setiap elemen yang kecil dibandingankan dengan elemen yang akan disispkan posisinya dinaikkan satu tingkat. Selama elemen yang ditemukan lebih besar dibandingkan dengan elemen yang akan disisipkan, pencarian akan dihentikan dan penyisipan terjadi didepan elemen yang besar.

Gambar 2.3 Ilustrasi Insertion Sort Algoritma Procedure insertsort(var r; list; n: integer); Var j, k, save: integer; Begin For k := n – 1 downto 1 do Begin j := k + 1;save := r[k]; r[n + 1] := save; while save > r[j] do


begin r[j – 1] := r [j]; j := j + 1; end; r[j – 1] := save end; end;

Perulangan sebelah luar dari prosedur insertsort selalu dieksekusi sebanyak n-1 kali. Banyakanya ekseskusi yang terjadi pada perulangan sebelah dalam tergantung pada nilai k dan urutan data. Dalam kasus data yang telah diurutkan, perulangan sisi dalam tidak pernah dieksekusi. Dalam kasus terburuk akan dieksekusi sebanyak : 1+2+…+n–1=

1 n(n – 1) = O(n2) 2

Dengan memberikan semua inisial pengurutan data yang mungkin terjadi, rata-rata perulangan dalam yang terjadi dieksekusi setengah dari kasus terburuk. Hal tersebut terjadi karena perulangan sisi dalam pada prosedur insertsort memeriksa daftar yang telah terurut dicari elemen pertama yang lebih besar dari satu yang disipkan. Rata-rata perintah tersebut menguji setengah dari daftar yang ada. Insertsort perulangan sisi dalam membutuhkan usaha yang lebih besar dibandingkan dengan selectsort perulangan sisi dalam – satu perpindahan melawan tidak ada perpindahan sama sekali. Tapi membutuhkan usaha yang lebih kecil dibandingkan dengan exchangesort. Untuk elemen yang pendek, pemindahan dalam perulangan sisi dalam lebih dari diseimbangkan dengan seringkali hanya mengeksekusi setengah perulangan sisi dalam, dan insertosrt memberikan kinerja yang lebih baik. Karena overhead yang rendaj dan kinerja yang cukup tinggi untuk dtaa terurut,

insertsort

akan

dikombinasikan

dengan

quicksort

untuk

menghasilkan algoritma pengurutan internal serbaguna yang terbaik untuk saat ini.


Sejauh ini, pengurutan data yang disimpan dalam doubly linked list tidak dibahas, bab selanjutnya membahas tentang implementasi insertion sort pada linked list. 1.1.4 Insertion Sort – diimplementasikan untuk Linked List Bab ini menggunakan algoritma insertion sort pada bagian sebelumnya. Perbedaannya terletak pada penggunaan linked list lebih dari sekedar suatu array. Dengan linked list nomor dari elemen yang dipindahkan adalah nol. Gambar 2.4 menampilkan tampilan logikal dari struktur doubly linked yang digunakan dalam bab ini. Daftar diakses oleh dua pointer, head dan tail, yang mengidentifikasikan akhir dari darftar. Algoritma insertion sort menampilkan prosedur Pascal, sortlink, untuk insertion sort pada doubly linked list.

Gambar 2.4 Tampilan logikal struktur data doubly linked

Algoritma Procedure sortlink(head, tail; pointer); Var p, psave: pointer; Begin If head <> tail Then begin P := tail^.prior; While p <> nil do begin psave := p^.prior; locate(p, pinsert); if p^.next <> psearch then begin remove(p; insert(p, psearch)


end; p := psave end; end; end;

Banyaknya eksekusi pada perulangan sisi dalam dan sisi luar pada implementasi linked sama dengan implementasi array. Perbedaan utama antara implementasi linked dan array terdapat pada kompleksitas prosedur, mekanisme pengalamatan, banyaknya pemindahan elemen data, dan overhead. Versi linked list lebih besar dibandingkan dengan versi array, karena alasan itu tidka diragukan lagi lebih komplek. Panjang yang tidak dibutuhkan berarti sulit, meskipun demikian, setiap bagian dari implementasi linked melakukan task yang sederhana. Implementasi array menggunakan pemosisian dan kalkulasi (fungsi pemetaan array) untuk mengakses elemen. Fungsi pemetaan array dapat memperlambat kerja, karena alasan tersebut kinerja yang lebih baik diharapkan dari implementasi linked. Lebih penting lagi, bagaimaan versi list mengontrol perpidahan elemen. Implementasi array pada insertion sort mengandung suatu pemindahan dalam perulangan sisi dalam dan memindahkannya ke perulangan sisi luar. Pemindahan perulangan sisi dalam adalah salah satu metode yang buruk; suatu elemen dipindahkan ke elemen yang berdekatan. Pemindahan tersebut dihilangkan pada versi linked list. Pemindahan pada perulangan sisi luar dapat menempuh jarak yang lebih besar. Dalam versi linked list hal tesebut digantikan dengan manipulasi pointer. Selection sort dan exchange sort dapat dengan mudah dikonversi untuk mengimplementasikan doubly linked list. Implementasi linked pada selection sort akan menjadi sedikit berbeda dari array sebagai pembandingnya. Perbedaan utama adalah bahwa prosedur swap tidak harus memindahkan sembarang data tapi hanya harus memanipulasi pointer.


Implementasi linked pada selection sort akan lebih sederhana dibandingkan dengan implementasi linked pada insertion sort. Perulangan sisi dalam pada kedua metode tersebut memudahkan dalam pencarian. Insertion sort memiliki keunggulan kinerja karena secara rata-rata pencarian perulangan sisi dalam terjadi hanya setengah dari selection sort. Hal tersebut merupakan logic yang dibutuhkan untuk mengimplementasikan manfaat yang menjelaskan peningkatan kompleksitas. Kelebihan pengurutan linked dibandingkan dengan penurutan array adalah data tidak dipindahkan. Harga yang harus dibayarkan untuk itu adalah dibutuhkannya penyimpanan untuk pointer dan implementasi yang sedikit lebih komplek. Seorang pengguna yang membutuhkan untuk mengurutkan elemen data yang besar yang disimpan dalam suatu array memiliki tiga pilihan dasar: 1. Mengurutkan array dengan berkurangnya kinerja dengan memindahkan elemen yang besar. 2. Memindahkan data ke suatu linked list, mengurutkannya, dan jika dipelrukan memindahkannya kembali ke suatu array untuk pemrosesan lebih lanjut. Pendekatan yang sederhana tersebut dapat meningkatkan kinerja, tapi membutuhkan momory ekstra yang cukup untuk menyimpan linked list. 3. Membuat suatu array index. Yang akan terasa efektif jika hal tersebut adalah data, dan bukan item yang urut, yamng membuat elemen besar. Array Index array terurut, dan index tersebut menyediakan akses pada data asli dalam urutan (tabel 1) Harga yang harus dibayarkan pada peningkatan kinerja adalah dibutuhkannya memory extra. Manfaat tergantung pada beberapa faktor, yaitu: ketersediaan memory tambahan, ukuran elemen yang diurutkan, dan pentingnya kinerja pengurutan.


1.1.5 Kinerja Pengurutan Sederhana

Gambar 2.5.1 Waktu yang dibutuhkan untuk mengurutkan daftar integer, nilai integer diinisialisasi secara acak

Gambar 2.5.2. Waktu yang dibutuhkan untuk mengurutkan daftar integer, nilai integer diinisialisasi terurut Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 14

Gambar 2.5.3. Waktu yang dibutuhkan untuk mengurutkan daftar integer, nilai integer diinisialisasi terbalik

Algoritma

Inisialisasi Data Diurutkan Acak Dibalik

Selection

Pemindahan Pembandingan

O(n) O(n2)

O(n) O(n2)

O(n) O(n2)

Exchange


0 O(n)

O(n2)

O(n2) O(n2)

Insertion – array


O(n) O(n)

O(n2) O(n2)

O(n2) O(n2)

Insertion – Linked


0 O(n)

0 O(n2)

0 O(n2)

List

Tabel 1 hanya menjelaskan tentang hasil pengurutan integer.


Gambar 2.5.4 Waktu yang dibutuhkan untuk mwngurutkan array 100 elemen, diinisialisasi secara acak, sebagai fungsi ukuran elemen. Kunci ataupun item yang diurutkan merupakan integer dengan data array integer

1.2. TEKNIK PENGURUTAN TINGKAT LANJUT ( ADVANCED SORT TECHNIQUE ) 1.2.1 QuickSort ( Partition Exchange Sort ) Quick Sort terdiri dari serangkaian langkah, dimana masing-masing mengambil elemen untuk diurutkan sebagai input. Output dari masingmasing langkah adalah terurutnya kembali elemen sehingga tidak ada elemen yang berada pada posisi untuk diurutkan dan disana ada dua sublist yang tersisa untuk diurutkan. Jika elemen yang akan diurutkan adalah r[1], r[2], …, r[n] kemudian satu langkah dari proses quicksort akan mengurutkan kembali elemen seperti yang tampak pada gambar berikut :


r[1], r[2], …, r[j - 1] (a)

r[j]

r[j + 1]. r[j + 2]…, r[n]

(b)

(c)

Gambar 3.1.1 hasil dari pengaplikasian satu langkah proses quicksort kedalam list elemen r[1], r[2], …, r[n]. (a) rangkaian yang akan diurutkan. Setiap elemen lebih kecil dari r[j]. (b) elemen dalam posisinya yang akan diurutkan. (c) rangkaian yang akan diurutkan. Masing-masing elemen lebih besar dari r[j].

Gambar 3.1.2 Serangkaian integer

Gambar 3.1.3 satu integer yang telah diurutkan Pada gambar 3.1.3 diatas, integer dalam gambar 3.1.2 diurutkan kembali sehingga 53 dalam posisinya yang terurut. Integer yang diurutkan ditunjukkan dengan bold. Jadi dengan kata lain, setiap langkah dari partisi quicksort memberikan urutan kedalam tiga disjoint sublist. Satu dari sublist adalah elemen tunggal yang berada dalam posisi terurutnya (gambar 3.1.1 b). Dua sublist yang lain berbagi properti umum. Masing-masing mengandung elemen yang semuanya lebih besar dari (gambar 3.1.1 c) atau lebih kecil dari (3.1.1 a) elemen yang sudah berada dalam posisi terurutnya. Hal tersebut mengujinkan setiap dua sublist untuk diurutkan tanpa referensi ke beberapa elemen dalam sublist yang lain. Setiap langkah dalam quicksort manggantikan masalah pengurutan satu list yang panjang menjadi dua list pengurutan yang pendek. Masalah pengurutan dikatakan dipartisi. Berdasarkan gambar list dari integer seperti yang ditunjukkan oleh gambar 3.1.2, setiap integer didianggap sebagai elemen. Satu jalan untuk mengurutkaninteger sehingga 53 berada dalam posisi terurut seperti ditunjukkan pada gambar 3.1.3. Integer yang telah berada dalam posisi terurut akan ditunjukkan melalui huruf tebal. Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 17

Disana ada beberapa pengurutan lain yang sesuai. Pada dasarnya beberapa pengurutan dimana integer lebih kecil dari 53 (51 dan 52) berada di sebelah kiri 53 dan integer yang lebih besar dari 53 (54, 55, …, 59 )berada di sebelah kanan 53. Berikut akan disedkripsikan algoritma yang selanjutnya akan digunakan untuk mengurutkan elemen. Aplikasi yang dilang dalam proses quicksort ke sublist yang tidak terurut yang secara sukses digenerate pada akhirnya akan menghasilkan suatu list yang terurut. Semua proses akan dideskripsikan dalam algoritma rekursi. Asumsikan bahwa elemen yang akan diurutkan disimpan dalam suatu array global yang dinamakan r. Index elemen pertama dan terakhir dalam rangkaian diurutkan kiri dan kanan berturut-turut.

Algoritma Algoritma QuickSort memiliki 3 versi yaitu : a. Versi 1 Procedure qs1(left, right: integer); Begin If left < right Then begin Rearrange the elements in the sequence r[left],…, r[right] In order to produce a new sequence That is partitioned as follows: r[left],…, r[j – 1] are all smaller than r[j] r[j] is in its sorted position r [j + 1],…, r[right] are all larger than r[j] qs1(left, j – 1); qs1(j + 1, right) end; end;

Andaikan prosedur qs1 dalam algoritma diatas diaplikasikan dalam list dari integer pada gambar 3.1.4 . Input untuk qs1 adalah kiri = 1 dan kanan = 9. langkah pertama meletakkan 73 kedalam posisi terurut seperti ditunjukkan pada gambar 3.1.5.


Gambar 3.1.4 rangkaian integer

Gambar 3.1.5 integer dalam gambar 3.1.4 disusun sehingga 73 berada dalam posisi terurut. Dua statemen terakhir dalam qs1 adalah pemanggilan rekursi kepada qs1. dalam contoh ini pasangan pertama yang dipanggil akan menjadi qs1(1,2) dan qs1(4,9). Yang pertama segera dieksekusi dan yang kedua dipush kedalam stack untuk dieksekusi kemudian. Dalam urutan ilustrasi proses, akan dibangun suatu binary tree. Setiap node dalam tree merepresentasikansatu panggilan ke qs1; root dari subtree kiri adalah rekursi panggilan pertama dan subtree kanan adalah panggilan rekursi kedua, seperti yang terlihat pada gambar 3.1.5 berikut:

Gambar 3.1.5. Inisialisasi panggilan dan dua panggilan rekursif pertama untuk urutan pada gambar 3.1.4 Prosedur call qs1 (1,2) menyebabkan 72 diletakkan dalam posisi terurut diantara 71 dan 72. hsilnya ditunjukkan dalam gambar 3.1.6. Syarat pemanggilan qs1 semua proses dari contoh ditunjukkan dalam gambar 3.1.7.

Gambar 3.1.6 rangkaian setelah qs1(1,2)


Gambar 3.1.7 pemanggilan inisial dan semua pemanggilan rekursif untuk qs1 dibutuhkan untuk mengurutkan urutan dalam gambar 3.1.4 Dua pemanggilan rekursi berikutnya, qs1(1,1) dan qs1(3,2), index kiri lebih besar dari atau sama dengan index kanan. Hal ini berarti bahwa sublist yang diurutkan kosong. Kemudian qs1(4,9) sekarang di pop kedalam stack dan proses dilanjutkan. Gambar 3.1.8 menunjukkan urutan dari integer setelah qs1(4,9) dan gambar 3.1.9 menunjukkanorutan setelah qs1(7,8). List telah diurutkan.

Gambar 3.1.8 rangkaian setelah qs1(4,9)

Gambar 3.1.9 rangkaian setelah qs1(7,8). Rekursi memanggil qs1(7,7) dan qs1(9,8) melengkapi pengurutan. b Versi 2, yang merupakan perbaikan dari versi 1 Procedure qs2(left, right: integer); Var j, k: integer; Begin If left < right Then begin j := leftk k := right + 1; repeat {1} repeat j := j + 1 until r[j] >= r[left]; {2} repeat k := k – 1 until r[k] <= r[left]; {3} if j < k then swap(r[j],r[k]) until j > k; swap(r[left],r[k]);


qs2(left, k-1); qs2(k + 1, right); end; end;

Algoritma diatas memfokuskan pada statement repeat-until, yang mengandung statement {1}, {2}, dan {3}, yang merupakan penempatan statement inner loop dari algoritma dan jantung dari proses penyusunan kembali. Inner loop dalam algoritma diatas digambarkan dengan rangkaian integer dalam gambar berikut :

Pertama kali statement {1} dieksekusi untuk membaca ke kanan sepanjang rangkaian integer, dimulai dengan elemen yang memiliki index left + 1. pembacaan dilanjutkan sampai suatu elemen yang lebih besar dari r[left] ditemukan. Dalam contoh pembacaan dimulai dari 15 dan berakhir pada 60 seperti yang ditunjukkan oleh gambar berikut :

Dengan cara yang sama, statement {2} dibaca ke kanan, dimulai dengan elemen yang paling kanan dalam rangkaian. Pembacaan akan berakhir ketika suatu elemen lebih kecil dari r[left] ditemukan, seperti yang tampak pada gambar berikut :

Jika dua pembacaan tidak cocok, yaitu j < k, kemudian statement {3} menukarkan dua elemen dimana pembacaan dihentikan. Dalam contoh, 60 dan 20 ditukar, seperti tampak dalam gambar berikut :

Sekarang, setelah

j < k, statement {1}, {2}, dan {3} diulang.

Statement {1} mulai membaca elemen disebelah kanan dari elemen dikirinya. Sekali lagi pembacaan dihentikan, ketika suatu nilai yang lebih besar dari r[left] ditemukan. Dengan cara yang sama statement {2} membaca ke kiri. Hasilnya ditunjukkan dalam gambar berikut :


Karena j < k, 75 dan 35 ditukar leh statement {3}. Statement {1} dan {2} dieksekusi lagi. Pembacaannya diilustrasikan dalam gambar berikut :

Periksa bahwa dalam pembacaan menyilang. Setelah statement {1} dan {2} dieksekusi, dimiliki j > k. Oleh karena itu r[j] dan r[k] tidak ditukar, dan menurunkannya melalui loop repeat – untul. Kemudian r[left], 40, ditukar dengan r[k], yaitu 35. hasil dari penyusunan ditunjukkan oleh gambar berikut :

Pasangan dari recursive call adalah qs2(1,6) dan qs2 (8,14). Secara umum ketika statement {3} dieksekusi, suatu nilai yang besar (lebih besar dari r[left] ) ditukar dengan suatu elemen kecil.( lebih kecil dari r[left] ). Efeknya adalah memindahkan elemen kecil ke depan rangkaian dan elemen besar ke bagian belakang rangkaian. Perhatikan juga bahwa kemungkinan elemen untuk berpindah dalam jarak yang panjang sebagai hasil daripertukaran tunggal. Hal ini merupakan penjelasan heuristik kinerja yang bagus dari quicksort. Dengan koleksi semua elemen yang lebih kecil dari r[left] di depan rangkaian dan semua elemen yang lebih besar dari r[left] di bagian belakang dari rangkaian, hanya menyisakan tempat untuk r[left] ditengah satu langkah yang komplit dariproses quicksort.

c. Versi 3, yang merupakan perbaikan dari versi 2 procedure qs3(left, right: integer); var j, k, temp: integer; ch: char; begin if left < right then begin swap(r[(left + right) div 2], r[left + 1]); if r[left + 1] > r[right]


then swap(r[left + 1], r[right]); if r[left] > r[right] then swap(r[left],r[right]); if r[left + 1] > r[left] then swap(r[left + 1], r[left]); j := left + 1; k := right; repeat {1} repeat j := j + 1 until r[j] >= r[left]; {2} repeat k := k – 1 until r[k] <= r[left]; {3} if j < k then swap(r[j],r[k]) until j > k; swap(r[left],r[k]); if(k – left) > 10 then qs3(left,k – 1); if(right – k) > 10 then qs3(k + 1, right) end; end;

Algoritma diatas merupakan perbaikan dari algoritma sebelumnya. Dalam algoritma tersebut terdapat tiga perbaikan dari algoritma sebelumya. Efek dari kinerjanya ditunjukkan dalam gambar berikut :

Gambar 3.2.0 waktu pengurutan suatu array dari inisial integer dalam urutan acak


Salah satu aspek penting dalam quicksort adalah cara membagi daftar ke dalam format binary tree (gambar 6.18). Masalah yang ada adalah proses pembagian tersebut dapat menimbulkan overhead yang tinggi dibandingkan dengan teknik yang sederhana seperti insertion sort. Analisa yang logis yaitu terdapat suatu sublist dibawah dimana prosedur simple sort harus digunakan untuk dalam quicksort. Sublist kecil dengan panjang 10 atau kurang dapat diabaikan sempai selesai ketika satu peneyelesaian insertion sort digunakan unutk menyelesaikan pengurutn. Peningkatan kinerj a12 % (untuk daftar yang besar) sampai dengan 20% (untuk daftar yang kecil) akan didapatkan (Lihat Sedgewick 1978).

1.2.2 TreeSort Treesort 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’.

1.2.3 HeapSort Seperti treesort, heapsort adalah dua langkah proses. Pertama, data ditaruh kedalam heap(tumpukan), dan, kedua, data diekstrak dari heap dalam 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 :


Gambar 3.3.1 Ringkasan proses heapsort Langkah kedua adalah menukarkan r[1] dengan r[n - 1] dan kemudian memeriksa kebawah r[1] dalam rangkaian r[1],…, r[n -2], buat suatu heap dengan n – 2 elemen. Sekarang r[n -1] dan r[n] membentuk suatu list terurut dari deret kedua dan r[1] adalah elemen terbesar ketiga. Langkah ke i menukarkan r[1] dengan r[n – (i – 1)] dan memeriksa kebawah r[1] dalam rangkaian r[1],…, r[n -1] membentuk suatu heap dengan n – 1 elemen. Rangkaian r[n – (i – 1)], …, r[n] adalah terurut, dan r[1] adalah elemen terbesar. Kunci dari semua proses ini adalah prosedur untuk memasukkan satu elemen kedalam puncak dari heap (tumpukan) sehingga heap yang baru dibentuk memiliki semua elemen lama ditambah satu yang dimasukkan. Prosedur yang menyelesaikannya adalah sift-down. Dengan menggunakan sift-down sebagai alat dasar, algoritma berikut mengimplementasikan prosedur heapsort.

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)


end; k := n; while k > 1 do begin swap(r[1],r[k]); k := k – 1; siftdown(1,k) end end;

Langkah pertama dari prosedur heapsort adalah mengkonstruksi suatu heap/tumpukan (lihat gambar 3.3.2). Hal itu memerlukan siftdown untuk membagi elemen-elemen. Nomor maksimum yang dibandingkan (atau dipindahkan) yang diperlukan siftdown adalah log2n. konstruksi dari inisial heap akan memerlukan paling banyak (n/2)log2n perbandingan atau perpindahan. Pengurutan

data

setelah

suatu

heap

dibentuk

memerlukan

pengaplikasian siftdown untuk n – 1 elemen. Loncatan keatas untuk memindahkan dan membandingkan adalah (n – 1) log2n. Kombinasi hasil dari konstruksi heap daan pengurutan selanjutnya menjamin bahwa paling banyak (3/2)nlog2n perpindahan atau perbandingan yang akan diperlukan. Hal ini seharusnya menjadi loncatan yang sangat konservatif dalam upaya yang diperlukan karena siftdown sering diaplikasikan untuk suatu heap yang lebih kecil dari n elemen.

Gambar 3.3.2 Ilustrasi dari heapsort Dalam setiap langkah, elemen terkecil diambil ari bagian teratas heap dan dipindahkan ke list terurut. Suatu heap dibentuk dari elemen sisa yang Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 27

menggunakan prosedur siftdown. Proses kemudian diulangi. (a) data yang akan diurutkan. (b) konstruksi dari suatu heap.

1.2.4 MergeSort Dua sublist, masing-masing telah diurutkan, dapat digabung bersama untuk membentuk suatu kumpulan list yang juga sudah diurutkan. Prosedur yang sederhana dan efektif untuk melakukannya disebut mergesort, dimulai dengan membandingkan sepasang elemen – satu dari setiap sublist. Elemen terkecil dilampirkan kedalam suatu list terurut dan di-replace dengan elemen berikutnya dari sublist. Hai ini berlannjut sampai tidak ada lagi elemen dalam sublist. Sisa elemen dalam sublist lainnnya dilampirkan ke list terurut dan pengurutan talah selesai. Akan menjadi bagus ketika ada dua sublist terurut dimana tidak ada untuk memulainya. Jika tidak ada masalahnya adalah memutuskan bagaimana untuk memulainya. Disana ada beberapa kemungkinan. Pendekatan pertama adalah menganggap elemen individu sebagai sublist terurut dari deret pertama. Pasangan dari sublist digabungkan untuk membuat list terurut dari deret dua. Pasangan dari list tersebut kemudian digabung untuk menghasilkan list terurut dari deret empat. Proses ini berlangsung terus menerus sampai satu dari list terurut tersisa. Proses ini diilustrasikan oleh gambar 3.4.1 berikut dan diimplementasikan dalam kedua algoritma mergesort.

Gambar 3.4.1 Ilustrasi dari penggabungan dua list terurut (sorted list) Ingat bahwa mergesort memerlukan dua array-r, dimana secara asli dipegang oleh data yang aan diurutkan, dan t, suatu array dari tipe yang


sama. Penggabungannya adalah dalam pasangan pertama dari r ke t, kemudian dari t ke r. Jadi mergesort memerlukan ruang untuk 2 x n elemen.

Algoritma 1. Procedure merge(L, n: integer; var r, t: list); Var q, k, k1, k2, end1, end2: integer; Begin k1 := 1; k2 := L + 1; q := 1; repeat end1 := k1 – L; if end1 > = n then end1 := n + 1 else begin end2 := k2 + L; if end2 > n then end2 := n + 1; repeat if r[k1] <= r[k2] then begin t[q] := r[k1]; q := q + 1; k1 end else begin t[q] := r[k2]; q := q + 1; k2 end until (k1 = end1) end; if k1 < end1 then repeat t[q] := r[k1]; q := q + 1; k1 := k1 until k1 = end1; else repeat t[q] := r[k2]; q := q + 1; k2 := k2 until k2 = end2;

:= k1 + 1

:= k2 + 1 or (k2 = end2);

+ 1

+ 1

k1 := k2; k2 := k2 + L until (k1 >= n); end; procedure mergesort(n: integer); var k, l: integer; t : list; begin L := 1; If n >= 3 Then repeat Merge(L,n

Merge(L,n= (n div 2); If L < n Then begin Merge(L,n,r,t); For k := 1 to n do r[k] := t[k] end end;

Prosedur mergesort membuat suatu lintasi diatas semua aray setiap kali dipanggil. Hal ini menjadi kurang lebih log2n kali dalam mengurutkan suatu list dengan panjang n. prosedur merge memindahkan semua n elemen selama setiap lintasan. Jika ia memerlukan n log2n perpindahan tidak memperdulikan bagaimana data diurutkan secara inisial. Oleh karena itu akan menjadi kinerja yang lebih baik untuk suatu linked list daripada array. Perbandingan selama suatu lintasan tergantung ari susunan data. Jika panjang sublist pertama digabung, maka akan menjadi n/2 perbandingan. Jika panjang sublist lebih besar dari n/2 akan digabung, kemudian diperlukan perbandingan sebanya n – 1. Oleh karena itu prosedur mergesort memerlukan kira-kira n log2n perpindahan (atau manipulasi pointer) dan pada suatu tempat diantara n/2 log2n dan n log2n perbandingan. Ini merupakan kinerja yang konsisten karena upaya yang diperlukan untuk menggunakannya tidak banyak dipengaruhi oleh susunan inisial dari data. Ia juga cepat, karena seperti heapsort memerlukan O(n log2n) upaya, meskipun dalam kondisi terburuk. Gambar berikut merupakan ilustrasi dari mergesort.

Gambar 3.4.2 Ilustrasi dari prosedur mergesort


Gambar 3.4.3 Perbandingan waktu yang diambil untuk mengurutkan suatu array dari integer atau elemen untuk mergesort, heapsort, quicksort, dan insertionsort. (a) integer secara inisial dalam urutan random. (b) integer secara inisial dalam susunan terurut. (c) integer secara inisial dalam susunan terbalik.


Gambar 3.4.3 membandingkan waktu pengurutan untuk 4 algoritma : mergesort, heapsort, quicksort, dan insertionsort. Mergesort

kira-kira

memerlukan waktu yang sama untuk semua inisial pengurutan data. Insertsort adalah yang tercepat dalam pengurutan data karena hanya memerlukan n – 1 perbandingan dan tidak ada perpindahan. Quicksort adalah yang tercepat untuk data acak karena disana menggunakan inner loop yang sederhana, yang memiliki kemampuan untuk memindahkan elemen melalui jarak yang panjang, dan menggunakan insertsort untukmengakhiri sesudah data secara dekat diurutkan. Untuk data dalam susunan terbalik mergesort adalah yang terbaik, bukan karena kinerjanya yang bertambah baik tetap karena kinerjanya berubah sangat kecil, dimana kinerja algoritma yang lain memburuk. Insertsort memerlukan O(n2) upaya, dan quicksort memerlukan lebih banyak perpindahan dari cara yang normal. Kekurangan mergesort untuk array adalah memerlukan dua memory seperti algoritma yang lain. Quicksort memerlukan stack tetapi tingginya paling tinggi log2n.

1.3. RADIX SORT Semua teknik pengurutan yang telah dibahas di depan sejauh ini berdasarkan pada membandingkan dan memindahkan atau menghubungkan kembali elemen yang akan diurutkan. Radix Sort tidak membandingkan dan mengambil suatu link struktur data, tidak ada perpindahan. Operasi dasar dari suatu radix sort adalah mengambil suatu elemen dari satu linked list dan menambahkannya ke yang lainnya. Jika item terurut dalam setiap elemen memiliki paling banyak k karakter, kemudian setiap elemen dihubungkan kembali sebanyak k kali. Usaha yang dilakukan sebanyak k x n operasi penghubungan kembali. Jadi disini tidak ada algoritma yang didasarkan pada pembandingan sepasang elemen yang memerlukan sedikitnya O(nlog2n) perbandingan dari data random.


1.3.1 Contoh kasus Radix Sort Suatu rangkaian integer seperti yang ditunjukkan dalam gambar 4.1 akan diurutkan. Setiap integer dalam contoh mengandung 3 digit; maka k = 3. langkah pertama adalah menambahkan setiap integer kedalam satu dari beberapa list yang disebut character list, berdasarkan nilai digit integer signifikan terkecil (integer’s least significant digit). Disana harus menjadi satu character list untuk setiap nilai karakter yang mungkin. Disini nilai yang mungkin adalah : 0, 1, …, 9. hasilnya ditunjukkan dalam gambar 4.2 dimana [0], …, [9] mengidentifkasi character list.

Gambar 4.1 list dari integer yang akan diurutkan

Gambar 4.2 Setiap integer ditambahkan kedalam suatu list karakter berdasarkan nilai dari digit pertamanya Sekarang integer diurutkan berdasarkan nilai dari least significant digits. Ini merupakan hal yang mudah, meskipun tidak diperlukan, untuk menggabungkan character list untuk membuat list yang ditunjukkan oleh gambar 4.3. list ini harus merefleksikan susunan dari character list yang digunakan untuk membangunnya.


Gambar 4.3 List dalam gambar 4.1 digabungkan untuk membentuk list baru

Langkah kedua adalah mengambil elemen, seperti yang diurutkan dalam gambar 4.3, dan menambahkan setiap integer ke suatu character list berdasarkan nilai dari 10 digitnya. Hasilnya ditunjukkan oleh gambar 4.4 berikut. Penggabungan list tersebut melindungi susunan lainnya, hasil dari list ditunjukkan oleh gambar 4.5.S

Gambar 4.4 Setiap integer ditambahkan ke list karakter berdasarkan nilai dari 10 digitnya.

Gambar 4.5list dalam gambar4.4 digabungkan untuk membentuk list baru.

Langkah ketiga dalam radixsort dari list dalam gambar 4.1 adalah menempatkan setiap integer kedalam character list berdasarkan nilai dari most significant digit. Prosesnya ditunjukkan dalam gambar 4.6. pengurutan dilengkapi dengan penggabungan, dalam urutan, character list ditunjukkan oleh gambar 4.7.


Gambar 4.6 setiap integer ditambahkan dalam list karakter berdasarkan nilai dari 100 digitnya.

Gambar 4.7 List yang dibentuk dgn menggabungkan list dalam gambar 4.6

1.3.2 Proses Umum Radix Sort Dalam algoritma 6.11 diasumsikan bahwa item yang diurutkan pada setiap elemen mengandung karakter k dan tipe data untuk karakter tersebut memiliki struktur linear. Struktur linear menemungkinkan pengasosiasian setiap nilai karakter dengan suatu karakter berdasar nomer urut nilai tersebut. Tipe data karakter selalu berupa karakter atau 0..9. Radix sort merupakan suatu historik yang signifikan sejak dapat diterapkan pada pengurutan kartu mekanikal . Pengurutan kartu mekanikal menggunakan suatu tumpukan kartu dan setiap tempat kartu dalam suatu slot output ditentukan oleh suatu nilai dalam kolom yang dipilih oleh operator. Algoritma 6.11 dapat dimodifikasi untuk menjelaskan proses tersebut. Dan hasilnya disebut dengan pengurutan mekanikal yang ditunjukkan pada algoritma 6.12. Sejak semakin jarangnya pemindahan kartu secara fisik, Algoritma 6.11 apat ditingkatkan. Tidak diharuskan mengunpulkan daftar karakter kedalam daftar tunggal sebelum mendistribusikan elemen ke dalam daftar karakter. Salah satu kelebihan lainnya adalah dapat didistribusikan dari dari satu set daftar karakter ke Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 35

lainnya dan menjjaga overhead kombinasi . Peningkatan tersebut tidak tidak dapat diterapkan pada pengurut mekanikal, sejak suatu subjek (misanya robot) harus mengurutkan suatu tumpukan pendek, mengkombinasikan menjadi satu tumpukan besar, dan menumpuk hasinya ke dalam suatu penampung input. Radix sort menunjukkan suatu teknik terbaik , sejak yang dibutuhkan hanya O(n) manipulasi pointer untuk mengurutkan suatu linked list.

Algoritma procedure radixsort(firstcolumn, lastcolumn: integer); var j, k: integer; begin j : = lastcolumn; repeat Meninjau daftar elemen yang akan diurutkan. Menambhakan setiap elemen ke suatu daftar karakter berdasarkan nilai karakter jth nya. Mengatur suatu bentuk baru daftar yang akan diurutkan oleh konkatenating daftar karakter dari daftar pertama ke daftar terkahir. j := j – 1 until j < firstcolumn end; procedure

Gambar. Perbandingan dari radixsort, qs3, dan insertsort untuk suatu set integer acak Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 36

1.3.3 kekurangan Radix Sort Kekurangan pertama dari radix sort ada;ah daftar harus berupa linked list. Radix sort pada suatu array akan menyulitkan dalam dua hal. Yang pertama adalah bahwa yang dibutuhkan bukan pada pemindahan malahan pada manipulasi pointer. Hal tersebut menjadi masalah serius jika elemen yang digunakan adalah besar. Setiap daftar karakter harus mampu untuk mengakomodasikan keseluruhan daftar yang akan diurutkan. Dengan demikian , jika terdapat m kemungkinan nilai untuk setiap karakter, memory ekstra yang dibutuhkan untuk radix sort ukurannya akan menjadi m kali dari ukuran daftar aslinya. Kekurangan lainnya adalah dibutuhkan overhead untuk mengkonversi nilai karakter kedalam indeks untuk daftar karakter yang tepat.. Sebagai contoh, jika item yang diurutkan adalah integer dengan tiga digit, disebut k, kemudian pemotongan digit secara individual membutuhkan statemen Pascal sebagai berikut: D3:=k mod 10;

{Digit signifikan terkedil}

D2:=(k div 10) mod 10;

{Digit puluhan}

D1:=k div 100;

(Digit signifikan terbesar}

Pascal bukan merupakan bahasa yang tepat untuk mengimplementasikan radix sort karena biasanya akan mencegah programmer

dari pengaksesan

instruksi mesin untuk efisiensi pemotongan bit dan karakter. Akhirnya, diaktakan bahwa radix sort adalah O(n) penekanan suatu konstan – banyaknya karakter dalam daftar urutan. Radix sort akan tidak eefisien jika item yang diurutkan mengandung karakter atau digit yang banyak. Untuk k tetap dan n yang cukup besar, radix sort seharusnya lebih cepat dibandingkan dengan algoritma lainnya. Masalah yang terjadi adalah nilai n untuk dimana radix sort melebihi metode yang membutuhkan O(n log n) pembandingan atau pemindahan akan menajdi sangat besar, tergantung pada beberapa faktor antara lain bahasa, kompiler, komputer, dan programmer. Gambar 6.44 membandingkan waktu pengurutan untuk insertsort, radixsort, dan qs3 dengan asumsi dikerjakan

pada kasus yang sederhana –kumppulan


integer acak. Radixsort tidak direpresentasikan dengan baik pada gambar 6.42 sejak Pascal tidak mengijinkan representasinya.

2. Pengurutan Eksternal Mengingat memory yang dimiliki sangat terbatas, maka tidak memungkinkan semua data yang dimiliki dimasukkan seluruhnya dalam memory utama. Untuk itu diperlukan suatu cara pengurutan ( Sorting ) yang disebut dengan pengurutan eksternal ( External Sorting ), yakni pengurutan yang menggunakan bantuan media penyimpan luar. External Sorting sangat berbeda dengan Internal Sorting , meskipun persoalannya sama yaitu mengurutkan sekumpulan data secara terurut naik, karena efisiensi pemasukan media penyimpan luar cukup terbatas. Struktur data harus ditentukan sedemikian rupa sehingga kelambanan pemasukan media luar bisa ditolerir. Konsekuensinya adalah bahwa beberapa metoda sebelumnya (penyisipan, penukaran, dan seleksi) menjadi tidak berguna untuk pengurutan eksternal. Sebagai contoh, dipunyai berkas dengan 5000 rekaman R1 sampai R5000 yang akan diurutkan. Panjang masing-masing rekamannya adalah 100 byte. Jika hanya 1000 rekaman saja yang bisa dimasukkan dalam pengingat utama, apa yang bisa kita lakukan ? Salah satu pemecahannya adalah dengan memecah berkas tersebut menjadi 5 berkas yang masing-masing terdiri dari 1000 rekaman. Kemudian setelah kelima berkas tersebut diurutkan secara terpisah, dilakukan merging terhadap kelima berkas tersebut untuk memperoleh berkas yang terdiri dari 5000 rekaman.yang rekamannya sudah dalam keadaan urut berdasarkan kuncinya. Cara ini sama dengan metode MergeSort. Cara inilah yang banyak digunakan untuk dalam melakukan External Sorting. Dengan kata lain metode MergeSort memegang peranan sangat besar untuk melakukan pengurutan eksternal. Dalam metode MergeSort terdapat dua tahap yang berbeda. Tahap pertama adalah memecah berkas menjadi sejumlah sub berkas, yang disebut run. Kemudian dengan menggunakan metoda pengurutan yang baik, misalnya Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 38

QuickSort, dilakukan pengurutan terhadap masing-masing run yang ada kemudian merekamnya ke dalam media penyimpanan luar. Tahap kedua adalah melakukan merge terhadap setiap pasang run. Hasil akhir yang diperoleh adalah sebuah run yang merupakan keseluruhan berkas yang telah dalam keadaan urut berdasar suatu kunci. Sebagai contoh, proses External Sorting menggunakan metode MergeSort dengan bantuan pita magnetis sebagai media penyimpan luar. Disini digunakan berkas yang terdiri dari 5000 rekaman, dan komputer yang mampu melakukan pengurutan internal sebanyak 1000 rekaman. Dengan demikian akan dipunyai 5 buah run, yaitu R1…R1000, R1001…R2000, R2001…R3000, R3001…R4000, R40001…R5000. akan digunakan 4 buah pita kerja. Dalam tahap pertama, setelah setiap run diurutkan secara internal, hasilnya secara bergantian disimpan dalam pita 1 dan pita 2 sampai semua masukan diproses. Kemudian pita 1 dan pita 2 diputar ulang ke awal rekaman, dan kemudian dilakukan merge terhadap sepasang run yang masing-masing berasal dari pita 1 dan pita 2. Hasilnya secara bergantian disimpan dalam pita 3 dan pita 4. (Jika banyaknya run dalam pita 1 lebih satu dibandingkan dengan banyaknya run dalam pita 2, maka dalam pita 2 dianggap ada sebuah run dengan panjang 0.) dengan selesainya langkah ini, akan terlihat bahwa dalam pita 3 dan pita 4 panjang setiap run adalah dua kali panjang run dalam pita 1 atau pita 2. langkah selanjutnya adalah melakukan merge terhadap setiap pasang run dalam pita 3 dan pita 4 dan secara bergantian hasilnnya disimpan dalam pita 1 dan pita 2. inilah hasil pengurutan eksternal yang telah dilaksanakan. Dengan menggunakan cotoh berkas diatas, maka setelah setiap run (yang masing-masing) panjangnya 1000 rekaman) diurutkan secara internal, isi keempat pita magnetis yang digunakan adalah sebagai berikut : Pita 1

R1…R1000, R2001…R3000, R40001…R5000

Pita 2

R1001…R2000, R3001…R4000

Pita 3

(Kosong)

Pita 4

(Kosong)


Setelah dilakukan satu kali merging, isi pita 3 dan pita 4 berubah menjadi: Pita 3

R1…R2001, R4001…R5000

Pita 4

R2001…R4000

Sebelum dilakukan merging berikutnya, dalam pita 4 dianggap ada sebuah run yang panjangnya 0, sehingga pada pita 3 dan pita 4 masing-masing terdapat dua buah run. Setelah dilakukan prose merging yang hasilnya disimpan dalam pita 1 dan pita 2, maka isi pita 1 dan pita 2 akan berubah menjadi : Pita 1

R1…R40001

Pita 2

R4001…R5000

Kedua isi pita diatas kita mergecsekalilagi ke dalam pita 3 untuk mendapatkan sebuah run yang tidak lain adalah hasil dari proses pengurutan eksternal (External Sorting) menggunakan metode MergeSort. Dalam contoh diatas digunakan 4 buah pita denngan 2 pita kosong pada saat permulaan.nya. dengan alasan inilah maka metode tersebut sering disebut balanced 2-way mergesort. Jika digunakan 6 buah pita dengan 3 pita kosong pada saat permulaannya akan disebut balanced 3-way mergesort.

Kesimpulan Gambar 6.45 menunjukkan aturan pada elemen dalam urutan yang disimpan pada suatu array. Jika daftarnya berukuran kecil, digunakan insertion sort untuk elemen yang kecil dan selection sort untuk elemen yang besar. Kedua teknik tersebut adalah O(n2), tapi untuk daftar yang kecil akan mengurangi overhead. Selection sort membuat sedikit perpindahan sehingga lebih cepat untuj elemen yang besar. Insertion sort malakukan pembandingan yang sedikit, sehingga akan lebih cepat untuk elemen yang kecil.


Gambar 6.45 Graik sepintas pada pemilihan teknik penurutan untuk elemen yang disimpan dalam suatu array. Itema yang diurutkan diasumsikan kecil. Sejalan dengan peningkatan jumlah elemen, usaha O(n log n) pada quicksort dengan mendekati perputaran dalkam yang sederhana, menjadikannya pilihan yang lebih baik. Akhirnya, ketika elemen menjadi besar, quicksort akan menghabiskan banyak waktu pemindahan data dari satu tempat ke tempat lainnya. Lebih efektif jika ditentikan array baru dimana data digantikan dengan indeks array. Indeks dalam urutan array ini dapat ditempati dalam order terurut dengan

List Size

perpindahan sebanyak O(n). kali

Radix Sort

Mergesort

Insertion Sort

Sort Item Size

Gamar 6.46 Grafik sepintas pada pemilihan teknik pengurutan pada elemen yang disimpan dobly linked list. Quicksort dapat digunakan pada mergesort. Gambar 5.46 menampilkan teknik untuk pengurutan elemen yang diosimpan dalam doubly linked list. Sumbu horizontal pada gambar 6.45 dan 6.46 memiliki labe4l yang berbeda. Untuk array adalah elemen size, untuk linked list adalah sort item size. Pada linked list, ukuran elemen tidak terlalu menjadi perhatian karena elemen tidak pernah dipindahkan. Sort item size digunakan karena jikaecil, dan ukuran daftarnya besar, radix sort akan lebih efektif. Aturan tersebut menandakan hanya diterapkan pada kasus tertentu, meskipun gambar menunjukkan.


Terdapat banyak metode terbaik , tergantung pada apa yang akan diurutkan pada mesin apa dan untuk keperluan apa.


SORTING (PENGURUTAN)

Recommend Documents