2003 edhy sutanta laporan penelitian 30 mei 2003 hal i-vii dan 1

v

KATA PENGANTAR Puji syukur kami panjatkan ke hadirat Tuhan Yang Maha Kuasa, karena

atas rahmat dan ijin-Nya laporan penelitian ini dapat terselesaikan.

Pada kesempatan ini Penulis menyampaikan ucapkan terimakasih dan

penghargaan yang sebesar-besarnya kepada berbagai pihak yang telah

membantu kelancaran dan terlaksananya penelitian ini, yaitu :

1. Rektor Institut Sains & Teknologi AKPRIND Yogyakarta

2. Dekan Fakultas Teknologi Industri IST AKPRIND Yogyakarta

3. Kepala Lembaga Penelitian IST AKPRIND Yogyakarta

4. Bapak Ir. Amir Hamzah, M.T., atas masukan dan sarannya

5. Ibu Dra. Hj. Naniek Widyastuti, M.T., atas masukan dan sarannya

6. Rekan-rekan di Jurusan Teknik Informatika dan Laboratorium Komputer IST

AKPRIND Yogyakarta

7. Semua pihak yang telah mendukung penelitian ini

Penulis menyadari bahwa hasil penelitian ini masih mengandung

kedangkalan dan kekurangan, oleh karena itu umpan balik dan saran dari para

Pemerhati dan Pembaca akan membantu demi kesempurnaan pada masa

mendatang.

Akhirnya, Penulis berharap agar penelitian ini dapat bermanfaat.

Yogyakarta, 30 Mei 2003

Penulis

vi

DAFTAR ISI

Halaman:

HALAMAN JUDUL i HALAMAN PENGESAHAN ii SURAT KETERANGAN KARYA ILMIAH iii SURAT KETERANGAN KARYA ILMIAH iv KATA PENGANTAR v DAFTAR ISI vi ABSTRAK vii BAB I. PENDAHULUAN 1 1.1. Latar Belakang Permasalahan 1 1.2. Rumusan Permasalahan 2 1.3. Tujuan Penelitian 2 1.4. Manfaat Penelitian 3 BAB II TINJAUAN PUSTAKA 4 2.1. Metode Seleksi Langsung (Straight Selection) 5 2.2. Metode Gelembung (Buble Sort) 10 2.3. Contoh Penyisipan Langsung (Straight Insertion) 14 2.4. Metode Penyisipan Biner (Binary Insertion) 18 2.5. Metode Quick Sort (Partition Exchange Sort) 23 2.6. Metode Shell Short (Diminishing Increment) 27 2.7. Metode Merge Sort (Two-way Marge Sort) 30 2.8. Metode Radix Sort 35 BAB IV METODOLOGI PENELITIAN 38 3.1. Metode Penelitian 38 3.2. Perancangan Program Aplikasi 38 3.3. Jadwal Waktu Penelitian 43 3.4. Beaya Penelitian 44 BAB IV PEMBAHASAN 46 4.1. Desain Program Aplikasi Versi Pertama 46 4.2. Analisis Algoritma Metode Penyisipan Biner Versi Pertama 51 4.3. Desain Program Aplikasi Versi Kedua 57 BAB IV KESIMPULAN 59 DAFTAR PUSTAKA

vii

ABSTRAK

Pengurutan data atau sorting merupakan jenis operasi penting dalam pengolahan data yang banyak diterapkan dalam permasalahan sehari-hari. Saat ini telah dikenal beberapa metode pengurutan data, yaitu seleksi langsung (straight selection), gelembung (buble-sort atau excenge sort), penyisipan langsung (straight insertion), penyisipan biner (binary insertion), Shell sort (diminishing increment sort), quick sort (partition excenge sort), Radix sort serta merge sort (two_way merge sort). Metode penyisipan biner dikembangkan dengan menggabungkan metode penyisipan langsung dan metode pencarian biner. Dalam metode ini, metode pencarian biner digunakan untuk menentukan lokasi penyisipan data yang akan diurutkan.

Penelitian ini bertujuan untuk mengkaji kemungkinan adanya kelemahan dalam metode penyisipan biner dan memberikan perbaikan sehingga diperoleh jaminan bahwa hasil perbaikan tersebut akan memberikan hasil data urut. Penelitian ini dilakukan dengan studi literatur dan pengujian contoh-contoh kasus pengurutan data menggunakan simulasi program aplikasi komputer dengan Turbo Pascal. Program aplikasi dibuat dalam dua versi, yaitu versi pertama untuk prosedur asli dan versi kedua untuk hasil perbaikan. Untuk masing-masing versi, program aplikasi terdiri atas empat modul, yaitu input data sumber, proses pengurutan data ascending, pengurutan data descending, dan menampilkan informasi pengecekan hasil pengurutan

Berdasarkan hasil pengujian beberapa kasus pengurutan data dengan metode penyisipan biner, ternyata masih dijumpai adanya kemungkinan hasil yang tidak urut. Kesalahan hasil operasi pengurutan data tersebut terjadi pada saat penggeseran batas interval baru (baik batas atas maupun batas bawah).

Perbaikan dapat dilakukan pada algoritma penyisipan biner dalam dua hal. Pertama, jika perhitungan titik tengah interval yang baru sama dengan titik interval yang lama, maka jika nilai yang disisipkan kurang dari nilai data pada posisi tengah, maka batas atas interval yang baru adalah sama dengan TENGAH-1. Sebaliknya jika nilai yang disisipkan lebih dari nilai data pada posisi tengah, maka batas atas interval yang baru adalah sama dengan TENGAH+1. Kedua, jika perhitungan titik tengah interval yang baru tidak sama dengan titik interval yang lama, maka jika nilai yang disisipkan kurang dari nilai data pada posisi tengah, maka batas atas interval yang baru adalah sama dengan TENGAH yang lama. Sebaliknya jika nilai yang disisipkan lebih dari nilai data pada posisi tengah, maka batas atas interval yang baru adalah sama dengan TENGAH yang lama. Kata kunci: pengurutan data, algoritma, penyisipan, penyisipan biner

1

BAB I PENDAHULUAN

1.1. LATAR BELAKANG PERMASALAHAN

Pengurutan data atau sorting merupakan salah satu jenis operasi penting

dalam pengolahan data. Hampir setiap saat dalam kehidupan sehari-hari selalu

dijumpai permasalahan-permasalahan yang harus diselesaikan dengan

melibatkan operasi pengurutan data. Begitu pentingnya operasi tersebut,

sehingga sampai saat ini telah banyak dikembangkan metode-metode

pengurutan data. Pada dasarnya terdapat dua macam data urut, yaitu urut naik

(ascending) dan urut turun (descending). Contoh sekumpulan data dalam kondisi

ascending dan descending, adalah sebagai berikut :

Ascending : 40 47 51 52 69 70 72 84 90

Descending : 90 84 72 70 69 52 51 47 40

Saat ini telah dikenal beberapa metode pengurutan data, antara lain

seleksi langsung (straight selection), gelembung (buble-sort atau excenge sort),

penyisipan langsung (straight insertion), penyisipan biner (binary insertion),

Shell sort (diminishing increment sort), quick sort (partition excenge sort), Radix

sort serta merge sort (two_way merge sort).

Metode penyisipan biner merupakan metode yang dikembangkan

dengan menggabungkan dua metode lain, yaitu metode penyisipan langsung

dan metode pencarian biner. Dalam metode ini, metode pencarian biner

digunakan untuk menentukan lokasi penyisipan data yang akan diurutkan.

2

Permasalahan ternyata masih dapat terjadi ketika penentuan lokasi penyisipan

dilakukan dengan cara yang sama persis dengan metode biner sebagaimana

dalam metode pencarian biner. Berdasarkan hasil pengujian pada beberapa

kasus pengurutan data dengan metode penyisipan biner untuk data sumber

yang berbeda, ternyata masih dijumpai adanya kemungkinan hasil yang tidak

urut. Permasalahan demikian memerlukan pengkajian dan kemudian mencari

solusinya.

1.2. RUMUSAN PERMASALAHAN

Berdasarkan latar belakang permasalahan di atas, maka permasalahan

yang akan dibahas dalam penelitian ini adalah menemukan kelemahan metode

penyisipan biner dan bagaimana melakukan perbaikan terhadap algoritma

prosedur dalam metode tersebut. Penelitian ini dibatasi pada:

1. Penerapan metode penyisipan biner dengan data sumber berupa

sekumpulan data numerik

2. Mengkaji kemungkinan adanya kelemahan dalam metode penyisipan biner

3. Modifikasi untuk perbaikan metode penyisipan biner

1.3. TUJUAN PENELITIAN

Penelitian ini bertujuan untuk mengkaji kemungkinan adanya kelemahan

dalam metode penyisipan biner dan memberikan perbaikan terhadap metode

tersebut sehingga diperoleh jaminan bahwa penggunaan metode yang sudah

diperbaiki tersebut akan memberikan hasil berupa data urut.

3

1.4. MANFAAT PENELITIAN

Hasil penelitian ini diharapkan memberikan masukan bagi pemrogram

dalam menerapkan metode penyisipan biner agar terhindar dari kesalahan hasil

operasi.

4

BAB II TINJAUAN PUSTAKA

Pengurutan data (sorting) merupakan salah satu jenis operasi penting

dalam pengolahan data. Banyak permasalahan dalam kehidupan sehari-hari

yang harus diselesaikan dengan melibatkan operasi pengurutan data. Begitu

pentingnya operasi tersebut, sehingga telah dikembangkan metode-metode

pengurutan data dan mungkin akan muncul lagi metode yang baru. Beberapa

metode pengurutan data yang telah dikenal dan sering digunakan adalah seleksi

langsung (straight selection), gelembung (buble-sort atau exchange sort),

penyisipan langsung (straight insertion), penyisipan biner (binary insertion),

Shellsort (diminishing increment sort), quick sort (partition exchange sort), Radix

sort serta merge sort (two_way merge sort).

Pada dasarnya terdapat dua macam kondisi data urut, yaitu urut naik

(ascending) dan urut turun (descending). Data urut ascending jika data urutan

lebih awal mempunyai harga lebih kecil dari pada data urutan berikutnya.

Sebaliknya, data urut descending jika data pada urutan lebih awal mempunyai

harga lebih besar dari data urutan berikutnya.

Masing-masing metode tentu saja mempunyai keunggulan dan

kelemahan yang dapat saling dibandingkan. Umumnya dalam cacah data yang

sedikit, penggunaan metode seleksi langsung atau penyisipan langsung akan

lebih efisien dan menguntungkan. Namun dalam cacah data yang besar kedua

metode tersebut tidak efisien lagi untuk diterapkan. Efisiensi metode yang

digunakan dalam sebuah aplikasi adalah ditentukan oleh kecepatan dalam

mengurutkan data-data yang dalam kenyataannya sangat ditentukan oleh

banyaknya langkah yang harus dilakukan untuk membandingkan harga setiap

5

data dan menentukan lokasi urutan data. Semakin sedikit waktu yang diperlukan

untuk memperoleh data urut berarti metode tersebut relatif lebih baik.

2.1. Metode Seleksi Langsung (Straight Selection)

Prosedur pengurutan data ascending dengan metode seleksi langsung

adalah dimulai dengan mencari data terkecil dari seluruh data dan kemudian

ditempatkan pada posisi urutan pertama. Langkah kedua adalah mencari data

terkecil kedua dari seluruh data kecuali data pertama, dan kemudian ditempatkan

pada posisi urutan kedua. Langkah ketiga adalah mencari data terkecil ketiga

dari seluruh data kecuali data pertama dan kedua, dan kemudian ditempatkan

pada posisi urutan ketiga. Langkah seperti ini akan dilakukan secara terus

menerus hingga semua data selesai diproses dan telah menempati posisi yang

tepat dan akhirnya akan menghasilkan sekumpulan data yang urut.

Proses yang terjadi pada langkah pertama dilakukan dengan cara

mengambil data pertama dan kemudian dibandingkan dengan data kedua. Bila

data pertama lebih besar dari data kedua, maka tukarkan data pertama dengan

data kedua. Jika data kedua lebih besar dari data pertama, maka proses

dilanjutkan untuk membandingkan data pertama dengan data ketiga. Jika data

pertama lebih besar, maka tukarkan data pertama dengan data ketiga. Teruskan

proses tersebut hingga data pertama selesai dibandingkan dengan seluruh data

yang ada, sehingga akhirnya akan diperoleh data terkecil. Hasilnya kemudian

ditempatkan pada urutan pertama. Pada langkah selanjutnya data pertama tidak

perlu dibandingkan lagi.

Pada langkah kedua, data kedua dibandingkan dengan data ketiga. Bila

data kedua lebih besar dari data ketiga, maka tukarkan data kedua dengan data

6

ketiga. Jika data ketiga lebih besar, maka proses dilanjutkan untuk

membandingkan data kedua dengan data keempat. Jika data kedua lebih besar,

maka tukarkan data kedua dengan data keempat. Teruskan proses tersebut

hingga data kedua selesai dibandingkan dengan seluruh data yang ada,

sehingga akhirnya akan diperoleh data terkecil. Hasilnya kemudian ditempatkan

pada urutan kedua, dan pada langkah selanjutnya data kedua tidak perlu

dibandingkan lagi. Langkah-langkah selanjutnya dilakukan dengan cara

mengulangi proses tersebut untuk menemukan data terkecil ketiga, keempat,

kelima, dan seterusnya hingga semua data akan menempati lokasi yang tepat.

Jika diinginkan data urut descending, maka proses perbandingannya

tinggal dibalik. Pada langkah pertama data pertama dibandingkan dengan data

kedua, bila data pertama lebih kecil dari data kedua, maka tukarkan data

pertama dengan data kedua. Jika data kedua lebih kecil dari harga data pertama,

maka proses dilanjutkan untuk membandingkan data pertama dengan data

ketiga. Jika data pertama lebih kecil, maka tukarkan data pertama dengan data

ketiga. Teruskan proses tersebut hingga data pertama selesai dibandingkan

dengan seluruh data yang ada, sehingga akhirnya akan diperoleh data terbesar.

Hasilnya kemudian ditempatkan pada urutan pertama, dan pada langkah

selanjutnya data pertama tidak perlu dibandingkan lagi.

Pada langkah kedua, data kedua dibandingkan dengan data ketiga. Bila

data kedua lebih kecil dari pada data ketiga, maka tukarkan data kedua dengan

data ketiga. Jika data ketiga lebih kecil dari data kedua, maka proses dilanjutkan

untuk membandingkan data kedua dengan data keempat. Jika data kedua lebih

kecil, maka tukarkan data kedua dengan data keempat. Teruskan proses

tersebut hingga data kedua selesai dibandingkan dengan seluruh data, sehingga

7

akhirnya akan diperoleh data terbesar. Hasilnya kemudian ditempatkan pada

urutan kedua, dan pada langkah selanjutnya data kedua tidak perlu diproses lagi.

Proses pada langkah-langkah selanjutnya adalah mengulangi proses

tersebut untuk menemukan data terbesar ketiga, keempat, kelima, dan

seterusnya hingga semua data akan menempati lokasi yang tepat dan pada

akhirnya akan diperoleh data dalam kondisi urut descending.

Berikut adalah contoh penggunaan metode seleksi langsung untuk

mengurutkan data-data secara ascending dan descending. Data-data yang akan

diurutkan adalah sebagai berikut:

12 29 17 56 11 23

Langkah-langkah yang dilakukan dalam proses pengurutan secara

ascending adalah ditunjukkan oleh Tabel 2.1. Sedangkan Tabel 2.2 menunjukan

proses pengurutan data secara descending. Dalam kedua tabel tersebut, data

yang bergaris bawah merupakan data terkecil yang harus ditemukan dan

diproses pada langkah berikutnya.

Tabel 2.1: Contoh pengurutan data ascending dengan metode seleksi langsung Iterasi ke Data yang

diproses Hasil proses

0

1

2

3

4

5

-

11

17

23

29

59

12 29 17 56 11 23 11 12 29 17 56 23 11 12 17 29 56 23 11 12 17 23 29 59 11 12 17 23 29 59 11 12 17 23 29 59

8

Tabel 2.2: Contoh pengurutan data descending dengan metode seleksi langsung Iterasi ke Data yang


0

1

2

3

4

5

-

56

29

23

17

12

12 29 17 56 11 23 56 11 12 29 17 23 56 29 11 12 17 23 56 29 23 11 12 17 56 29 23 17 11 12 56 29 23 17 12 11

Dalam metode seleksi langsung harus diperhatikan seluruh elemen

data sumber untuk kemudian menentukan sebuah elemen data yang akan

ditempatkan pada tujuan (multiple source one destination). Solusi dalam bentuk

algoritma untuk mengurutkan data secara ascending dengan metode seleksi

langsung dapat dituliskan sebagai berikut:

Masukan vektor K yang memuat N buah data yang akan diurutkan.

Data-data yang akan diurutkan dibaca sebagai X.

1. Mulai

2. Proses berulang langkah-3 s/d langkah-5

FOR I = 1 TO N-1

3. Tentukan harga awal

LOKASI = I

4. Proses berulang untuk membandingkan harga data-data

FOR J = I +1 TO N

IF (X[LOKASI] > X[J]

Jika ya, tentukan LOKASI = J

Jika tidak, lanjutkan ke langkah-6

5. Tentukan posisi data X[I] dengan X[LOKASI]

BANTU = X[I]

X[I] = X[LOKASI]

9

X[LOKASI] = BANTU

6. Cetak hasil

7. Selesai

Solusi dalam bentuk algoritma untuk mengurutkan data secara urut

turun dengan metode seleksi langsung dapat dituliskan sebagai berikut:

Masukkan vektor K yang memuat N buah data yang akan diurutkan.


1. Mulai


FOR I = 1 TO N-1


LOKASI = I


FOR J = I +1 TO N

IF (X[LOKASI] < X[J]

Jika ya, tentukan LOKASI = J

Jika tidak, lanjutkan ke langkah-6

5. Tentukan posisi data X[I] dengan X[LOKASI]

BANTU = X[I]

X[I] = X[LOKASI]

X[LOKASI] = BANTU

6. Cetak hasil

7. Selesai

Dalam algoritma prosedur pengurutan data dengan metode seleksi

langsung tersebut digunakan beberapa variabel, yaitu I, N, J, X, LOKASI, dan

BANTU. Variabel I dan J digunakan sebagai pencacah. Variabel N menunjukkan

cacah data yang akan diurutkan. Variabel X digunakan untuk menyimpan harga-

harga data yang akan diurutkan. Sedangkan variabel LOKASI dan BANTU

digunakan sebagai variabel bantuan untuk proses pertukaran lokasi data-data.

10

Dalam metode seleksi langsung, banyaknya proses perbandingan antar

data yang harus dilakukan untuk menemukan harga terkecil atau data terbesar

pada setiap langkah adalah sebanyak N-1. Untuk mengurutkan seluruh data

dalam vektor asal/sumber, maka total proses perbandingan yang harus dilakukan

dapat dihitung dengan formula sebagai berikut:

22)1()( 21

1

NNNNINK

N

I

−=

−=

−=∑

−

=

Keterangan:

K : cacah total proses perbandingan

N : cacah data

I : langkah pengurutan

Dalam cacah data yang besar, penggunaan metode ini akan tidak

efisien, karena memerlukan langkah perbandingan yang sangat banyak sehingga

akan memerlukan waktu yang relatif lama.

2.2. Metode Gelembung (Buble Sort)

Metode gelembung (bublesort) disebut juga metode exchange sort. Jika

dibandingkan dengan metode seleksi langsung, metode gelembung memiliki

perbedaan dalam menemukan data terkecil dan cara pertukaran datanya.

Langkah pertama pengurutan data secara ascending dengan metode

gelembung adalah membandingkan data pertama dengan data kedua, jika data

pertama lebih besar maka tukarkan posisinya dengan data kedua. Kemudian

data kedua dibandingkan dengan data ketiga, tukarkan jika data kedua lebih

besar dari data ketiga. Selanjutnya, data ketiga dibandingkan dengan data

keempat, tukarkan jika data ketiga lebih besar dari data keempat. Proses seperti

ini akan diulang terus menerus hingga semua data selesai dibandingkan. Hasil

11

pada langkah pertama adalah menempatkan data terbesar pada urutan. Data

terbesar yang telah menempati posisi terakhir tersebut tidak perlu dibandingkan

lagi pada langkah selanjutnya.

Pada langkah kedua, data pertama dibandingkan dengan data kedua.

Jika harga data pertama lebih besar maka tukarkan dengan data kedua.

Kemudian data kedua dibandingkan dengan data ketiga, tukarkan posisinya jika

data kedua lebih besar dari data ketiga. Selanjutnya, data ketiga dibandingkan

dengan data keempat, tukarkan jika data ketiga lebih besar dari data keempat.

Proses tersebut diulang secara terus menerus hingga semua data selesai

dibandingkan. Hasil pada langkah kedua adalah menempatkan data terbesar

pada urutan terakhir. Sehingga data terbesar yang diperoleh tersebut akan

menempati urutan kedua dari belakang dari keseluruhan data hasil pengurutan.

Data kedua tersebut tidak perlu dibandingkan lagi pada langkah selanjutnya.

Jika K menyatakan cacah proses perbandingan yang harus dilakukan

untuk mengurutkan semua data, maka cacah perbandingan dalam metode

gelembung dapat dihitung dengan formula sebagai berikut:

2

2 NNK −=

Keterangan:

K : cacah proses perbandingan

N : cacah data

Sebagai contoh, terdapat enam elemen data yang akan diurutkan

ascending dengan metode gelembung, yaitu sebagai berikut:

87 74 71 54 88 60

Proses pengurutan ascending dengan metode gelembung dapat ditelusuri

pada Tabel 2.3. Dalam tabel tersebut, data yang bergaris bawah merupakan

12

data terbesar yang harus ditemukan dan diurutkan pada langkah berikutnya.

Data tersebut akan menempati posisi terakhir sebelum elemen-elemen data yang

telah diurutkan pada langkah sebelumnya.

Tabel 2.3: Contoh pengurutan data ascending dengan metode gelembung Iterasi ke Data yang


0

1

2

3

4

5

-

88

87

74

71

60

87 74 71 54 88 60 74 71 54 87 60 88 71 54 74 60 87 88 54 71 74 60 87 88 54 60 71 74 87 88 54 60 71 74 87 88

Solusi dalam bentuk algoritma untuk mengurutkan data secara

ascending dengan metode gelembung dapat dituliskan sebagai berikut:



1. Mulai

2. Proses berulang langkah-3

FOR I = 1 TO N-1


FOR J = 1 TO N-I


IF X[J] > X[J+1]

Jika ya, lakukan penggeseran

BANTU = X[J]

X[J] = X[J+1]

X[J+1] = BANTU

13

5. Cetak hasil

6. Selesai

Jika data dalam contoh di atas akan diurutkan secara descending,

maka langkah proses pengurutan di atas tinggal dibalik, yaitu pada saat

membandingkan harga data, sehingga data terkecil akan dicari dari keseluruhan

data sumber dan ditempatkan pada posisi terakhir.

Secara ringkas, langkah pengurutan secara descending dengan metode

gelembung dapat ditelusuri pada Tabel 2.4. Dalam tabel tersebut, data yang

bergaris bawah merupakan data terkecil yang harus ditemukan dan diurutkan

pada langkah berikutnya dan akan menempati posisi paling akhir sebelum

elemen-elemen data yang telah diurutkan pada langkah sebelumnya.

Tabel 2.4: Contoh pengurutan data descending dengan metode gelembung Iterasi ke Data yang


0

1

2

3

4

5

-

54

60

71

74

87

87 74 71 54 88 60 74 71 71 88 60 54 87 74 71 88 60 54 87 74 88 71 60 54 87 88 74 71 60 54 88 87 74 71 60 54

Solusi dalam bentuk algoritma untuk mengurutkan data secara

descending dengan metode gelembung dapat dituliskan sebagi berikut ini:



1. Mulai

14


FOR I = 1 TO N-1


FOR J = 1 TO N-I


IF X[J] < X[J+1]


BANTU = X[J]

X[J] = X[J+1]

X[J+1] = BANTU

5. Cetak hasil

6. Selesai

2.3. Metode Penyisipan Langsung (Straight Insertion)

Secara umum proses pengurutan data dengan metode penyisipan

langsung (straight insertion) merupakan kebalikan dari proses yang dilakukan

dalam metode seleksi langsung. Dalam metode penyisipan langsung, hanya

diperhatikan satu elemen data dari sumber dan semua elemen data dari larik

tujuan (one source multiple destination).

Pengurutan data dengan metode penyisipan langsung dimulai dengan

membandingkan data kedua dengan data pertama. Jika data kedua lebih besar,

maka data kedua ditukarkan posisinya dengan data pertama. Pada langkah

berikutnya data ketiga dibandingkan dengan data kedua. Jika data ketiga lebih

besar, maka data ketiga ditukarkan posisinya dengan data kedua. Kemudian

data tersebut dibandingkan dengan data pertama, tukarkan posisinya jika data

ketiga lebih besar. Berikutnya data keempat dibandingkan dengan semua data

urut yang telah diproses, yaitu ketiga, kedua, dan pertama. Proses perbandingan

15

data yang sedang diproses terhadap data urut akan dihentikan jika data tersebut

telah menempati posisi semestinya sehingga akan tetap diperoleh data urut.

Sebagai contoh, diketahui larik data yang memuat delapan data dalam

tidak urut, yaitu sebagai berikut:

10 5 7 9 2 1 8 6

Langkah pengurutan dan hasil pada setiap langkah pengurutan dengan

metode penyisipan langsung dapat ditelusuri pada Tabel 2.5. Dalam tabel

tersebut, data yang bergaris bawah merupakan data urutan berikutnya yang

harus dibandingkan dan disisipkan dalam larik yang telah diurutkan pada langkah

sebelumnya. Setiap data baru yang diproses akan selalu disisipkan secara

langsung dan menempati posisi baru yang tepat, sehingga pada setiap akhir

langkah tertentu semua data yang telah diproses akan selalu berada dalam

kondisi urut.

Tabel 2.5: Contoh pengurutan ascending dengan metode penyisipan langsung Iterasi ke Data yang

diproses Hasil Proses

0

1

2

3

4

5

6

7

-

5

7

9

2

1

8

6

10 5 7 9 2 1 8 6 5 10 7 9 2 1 8 6 5 7 10 9 2 1 8 6 5 7 9 10 2 1 8 6 2 5 7 9 10 1 8 6 1 2 5 7 9 10 8 6 1 2 5 7 8 9 10 6 1 2 7 6 7 8 9 10

16

Algoritma prosedur pengurutan data ascending dengan metode penyisipan

langsung dapat dituliskan sebagai berikut:



1. Mulai


FOR I = 1 TO N

3. Tentukan elemen yang akan disisipkan

T = X[I]

X[0] = T

J = I - 1

4. Proses berulang untuk menyisipkan harga data-data

WHILE T<X[J]


X[J+1] = X[J]

J = J -1

X[J+1] = T

5. Cetak hasil

6. Selesai

Jika data dalam contoh di atas akan diurutkan secara descending,

maka prosesnya tinggal dibalik saja. Prosedur pengurutan data descending

dengan metode penyisipan langsung, adalah dimulai dengan membandingkan

data kedua dengan data pertama. Jika data kedua lebih besar, maka data kedua

ditukarkan posisinya dengan data pertama. Proses pada langkah berikutnya data

ketiga dibandingkan dengan data kedua. Jika data ketiga lebih kecil, maka data

ketiga ditukarkan posisinya dengan data kedua. Kemudian data tersebut

dibandingkan dengan data pertama, tukarkan posisi kedua data jika data ketiga

lebih kecil.

17

Berikutnya data keempat dibandingkan dengan data-data urut yang

telah diproses, yaitu ketiga, kedua, dan pertama. Proses perbandingan data baru

yang sedang diproses dengan data-data lain yang telah urut akan dihentikan jika

data tersebut telah menempati posisi yang semestinya sehingga data-data yang

telah diproses tetap berada dalam kondisi urut.

Langkah dan hasil pengurutan data pada setiap langkah dapat ditelusuri

sebagaimana ditunjukkan oleh Tabel 2.6. Dalam tabel tersebut, data yang

bergaris bawah merupakan data urutan berikutnya yang harus dibandingkan dan

disisipkan dalam larik yang telah diurutkan pada langkah sebelumnya.

Tabel 2.6: Contoh pengurutan descending dengan metode penyisipan langsung Iterasi ke Data yang

diproses Hasil Proses

0

1

2

3

4

5

6

7

-

5

7

9

2

1

8

6

10 5 7 9 2 1 8 6 10 5 7 9 2 1 8 6 10 7 5 9 2 1 8 6 10 9 7 5 2 1 8 6 10 9 7 5 2 1 8 6 10 9 7 5 2 1 8 6 10 9 8 7 5 2 1 6 10 9 8 7 6 5 2 1

Algoritma prosedur pengurutan data descending dengan metode

penyisipan langsung dapat dituliskan sebagai berikut ini:

Masukkan vektor K sebanyak N buah data yang akan diurutkan.


1. Mulai

18


FOR I = 1 TO N

3. Tentukan elemen yang akan disisipkan

T = X[I]

X[0] = T

J = I-1

4. Proses berulang untuk menyisipkan harga data-data

While T>X[J]


X[J+1] = X[J]

J = J -1

X[J+1] = T

5. Cetak hasil

6. Selesai

2.4. Metode Penyisipan Biner (Binary Insertion)

Metode penyisipan biner (binary insertion) merupakan usaha perbaikan

dari metode penyisipan langsung (straight inserton). Dalam cacah data yang

banyak, proses pengurutan data dengan metode penyisipan biner akan lebih

efisien jika dibandingkan dengan metode penyisipan langsung. Secara garis

besar, proses pengurutan data dengan metode ini terdiri dari dua bagian utama,

yaitu proses penentuan elemen-elemen data yang akan diproses dan proses

penyisipan elemen data untuk mengurutkan data-data. Proses penentuan

elemen data yang akan diproses adalah sama dengan cara-cara dalam metode

penyisipan langsung. Berbeda dengan metode penyisipan langsung dimana

penentuan lokasi dan penyisipan dilakukan secara langsung, maka dalam

metode penyisipan biner penentuan lokasi dan penyisipan dilakukan dengan

metode biner. Oleh karena itu, metode ini kemudian disebut sebagai metode

penyisipan biner.

19

Langkah pengurutan data menggunakan metode penyisipan biner dapat

dijelaskan sebagai berikut ini. Mula-mula data pertama dalam larik sumbr

dianggap telah menempati posisi yang tepat pada larik hasil. Kemudian setiap

data yang mendapat giliran diproses akan disisipkan ke dalam larik hasil, yaitu

dimulai data kedua, ketiga, hingga data terakhir. Proses penyisipannya dilakukan

dengan tiga tahap, yaitu penentuan lokasi untuk penyisipan, kemudian

penggeseran data-data dalam larik hasil yang mempunyai harga lebih besar dari

data yang akan disisipkan, dan terakhir adalah penyisipan data.

Untuk menentukan lokasi penyisipan dengan cara biner dilakukan

dengan cara sebagai berikut ini. Mula-mula ditetapkan harga-harga batas bawah

dan batas atas interval untuk larik hasil. Harga awal batas bawah untuk setiap

iterasi adalah 1. Sedangkan harga awal batas atas pada setiap iterasi adalah

sama dengan cacah data pada larik hasil. Sebagai contoh, jika saat ini sedang

berlangsung proses penyisipan data ke-10 dari larik sumber, maka harga awal

batas bawahnya adalah 1 dan batas atasnya adalah 9. Selanjutnya dari dua

harga awal tersebut dapat ditentukan titik tengah intervalnya, yaitu dengan

menjumlahkan harga batas interval bawah dengan batas interval atas dan

kemudian dibagi 2. Titik ini akan membagi larik hasil menjadi dua bagian yang

sama.

Jika data-data akan diurutkan secara urut naik, maka data-data pada

bagian pertama yaitu bagian yang berda di sebelah kiri akan memuat data-data

urut yang lebih kecil dari harga data pada titik tengah interval. Sedangkan data-

data pada bagian kedua yaitu bagian yang berada di sebelah kanan akan

memuat data-data yang lebih besar dari harga data pada titik tengah interval.

Setiap data yang akan disisipkan mula-mula dibandingkan dengan data pda

20

posisi titik tengah interval. Jika semua data dalam larik sumber tidak ada yang

sama, maka langkah ini akan mengakibatkan dua kemungkinan kondisi, yaitu

data yang akan disisipkan akan lebih kecil atau lebih besar dari harga data pada

posisi titik tengah interval. Jika lebih kecil maka, penyisipan harus dilakukan pada

bagian pertama yaitu interval sebelah kiri. Selanjutnya tidak perlu dibandingkan

dengan data-data pada bagian kedua di sebalah kanan. Namun jika data yang

akan disisipkan lebih besar, maka penyisipan harus dilakukan pada bagian

kedua dan tidak perlu lagi dibandingka dengan bagian pertama. Dengan cara

demikian, maka dapat dikurangi langkah proses membandingkan antara data

yang akan disisipkan dengan data-data dalam larik hasil. Faktor inilah yang

mampu meningkatkan efisiensi proses pengurutan data dengan metode

penyisipan biner sehingga dalam cacah data yang cukup banyak akan lebih baik

jika dibandingkan dengan metode penyisipan langsung.

Untuk melanjutkan ke langkah berikutnya, perlu diperhatikan bahwa jika

data yang disisipkan akan menempati pada bagian pertama, maka batas atas

interval akan digeser menjadi titik tengah dikurangi satu. Sebaliknya jika data

yang disisipkan akan menempati bagian kedua, maka batas bawah interval

dinaikan menjadi titik tengah ditambah satu. Prosedur demikian adalah mengikuti

cara-cara dalam metode biner yang merupakan salah satu dasar bagi

dikembangkannya metode penyisipan biner.

Pada langkah selanjutnya, interval dimana data akan disisipkan dibagi

kembali menjadi dua bagian yang sama dengan menetapkan titik tangah pada

interval baru yang lebih sempit tersebut. Kemudian proses perbandingan dan

penentuan interval-interval baru dilakukan kembali. Demikian seterusnya proses

dilaksanakan hingga ditemukan posisi yang tepat bagi data yang akan disisipkan,

21

yaitu jika harga titik tengah interval telah sama dengan harga batas bawah dan

batas atas interval. Selanjutnya jika posisi penyisipan telah ditemukan, maka

proses dilanjutkan untuk menggeser data-data mulai dari posisi dimana data

akan disisipkan hingga data terakhir pada larik hasil. Setelah selesai baru

kemudian dilakukan penyisipan, yaitu dengan cara menempatkan data yang

disisipkan pada posisi yang telah ditemukan. Dengan demikian sebuah data telah

selesai diproses dan data-data dalam larik hasil tetap berada dalam kondisi urut.

Untuk menyisipkan elemen-elemen data lain yang belum terproses, adalah

dilakukan dengan cara yang sama dengan cara-cara tersebut di atas. Pada

akhirnya jika semua data telah selesai diproses, akan diperoleh sebuah vektor

yang urut secara naik.

Untuk memproses yang dilakukan dalam metode penyisipan biner,

berikut ini akan diberikan sebuah contoh penerapannya. Diketahui sebuah vektor

K yang mempunyai delapan elemen data, yaitu sebagai berikut:

10 5 7 9 2 1

Dengan menggunakan metode penyisipan biner, vektor tersebut akan diurutkan

secara ascending. Secara ringkas, langkah dan hasil proses pengurutan pada

setiap iterasi adalah ditunjukkan oleh Tabel 2.7. Data yang mempunyai tanda

garis bawah menunjukkan bahwa data tersebut akan disisipkan pada iterasi

berikutnya. Seperti terlihat dalam tabel tersebut untuk mendapatkan vektor yang

urut naik diperlukan 7 iterasi penyisipan data. Sebagai contoh, hasil proses pada

iterasi pertama akan menyisipkan data 5 dalam posisi pertama. Iterasi kedua

akan menempatkan data 7 pada urutan kedua. Selanjutnya hasill iterasi ketiga

akan menempatkan data 9 pada urutan ketiga. Demikian seterusnya proses

22

tersebut akan diulangi hingga akhirnya semua data dalam vektor K menjadi urut

secara naik.

Algoritma prosedur pengurutan data secara ascending dengan metode

penyisipan biner sebagaimana telah dijelaskan di atas, dapat dituliskan ke dalam

solusi bentuk algoritma prosedur seperti di bawah ini.



1. Mulai


FOR I = 2 TO N

3. Tentukan elemen yang akan disisipkan dan harga awal batas-batas interval

SISIP = X[I], BAWAH = 1, ATAS = I-1

4. Proses berulang langkah-5 s/d langkah-6 untuk mencari lokasi penyisipan

data

WHILE BAWAH <= ATAS

5. Tentukan titik tengah interval

TENGAH = (BAWAH+ATAS) DIV 2

6. Mencari lokasi penyisipan

IF SISIP < X[TENGAH]

Jika ya, tentukan batas interval atas baru: ATAS=TENGAH-1

Jika tidak, tentukan batas interval bawah baru: BAWAH=TENGAH+1


FOR J = I -1 DOWNTO BAWAH

8. Menggeser data-data

X[J+1] = X[J]

9. Sisipkan data

X[BAWAH] = T

10. Selesai

23

Tabel 2.7: Contoh pengurutan ascending dengan metode penyisipan biner Iterasi Ke: Hasil Proses

0

1

2

3

4

5

10 5 7 9 2 1 5 10 7 9 2 1 5 7 10 9 2 1 5 7 9 10 2 1 2 5 7 9 10 1 1 2 5 7 9 10

2.5. Metode Quick Sort (Partition Exchange Sort)

Metode Quick Sort (Partition Exchange Sort) pertama kali diperkenalkan

oleh C.A.R. Hoare. Proses pengurutan data menggunakan metode ini secara

garis besar adalah sebagai berikut ini. Apabila diketahui sebuah vektor K dengan

N buah elemen data yang akan diurutkan secara urut naik. Pertama-tama dipilih

salah satu elemen data sembarang pada vektor K tersebut, biasanya adalah

elemen pada urutan pertama dan diberi nama X. Selanjutnya semua elemen

pada vektor K disusun dengan menempatkan elemen data X pada posisi tertentu

yaitu J sedemikian rupa sehingga elemen data pada urutan ke-1 sampai ke J-1

mempunyai harga lebih besar dari X. Sehingga, dengan demikian akan terdapat

dua subvektor, yaitu subvektor bagian pertama yang memuat elemen-elemen

data yang memilki harga kurang dari X dan subvektor bagian kedua yang

memuat elemen-elemen data yang memilki harga lebih dari X.

Prosedur di atas akan diulang pada subvektor pertama dan subvektor

kedua, sehingga akan diperoleh empat bagian subvektor baru. Proses yang

sama akan terus dilakukan secara berulang hingga semua subvektor pada

24

akhirnya hanya tinggal mempunyai satu elemen data. Dalam kondisi demikian,

maka semua data dalam vektor K telah menjadi urut naik.

Secara lebih terinci, prosedur pengurutan data dengan menggunakan

metode quick sort dapat terdiri serangkaian langkah yang dapat dituliskan dalam

solusi bentuk algoritma sebagai berikut ini.



1. Mulai

2. Cek pencacah data

IF AWAL < AKHIR

Jika ya, kerjakan langkah-3 s/d langkah-10

Jika tidak, kerjakan langkah-11


I = AWAL +1

J = AKHIR

4. Menentukan posisi data X dengan gerakan dari kiri ke kanan

WHILE X[I] < X[AWAL]

I = I+1

5. Menentukan posisi data X dengan gerakan dari kanan ke kiri

WHILE X[J] > X[AWAL]

J = J-1


while i<j

7. Tukarkan nilai X[I] dengan X[J]

BANTU = X[J]

X[J] =X[I]

X[I] = BANTU

8. Bergerak dari kiri ke kanan

WHILE X[I] < X[AWAL]

I = I+1

9. Bergerak dari kanan ke kiri

25

WHILE X[J] > X[AWAL]

J = J -1

10. Tukarkan X[AWAL] dengan X[J]

BANTU = X[J]

X[J] = X[AWAL]

X[AWAL] = BANTU

11. Cetak hasil

12. Selesai

Sebagai ilustrasi pengurutan data secara urut naik dengan metode

quick sort, berikut ini akan diberikan contoh penerapannya. Diketahui suatu

vektor K yang mempunyai delapan elemen data, yaitu sebagai berikut:

87 74 71 100 75 25 56 90

Proses pengurutan data dalam vektor K di atas dimulai dengan

menempatkan data urutan pertama yaitu 87 pada posisi tertentu yaitu J,

sehingga titik J akan membagi vektor K menjadi dua subvektor baru yaitu

subvektor di sebelah kiri yang hanya memuat data-data yang lebih kecil atau

sama dengan 87. Subvektor kedua yaitu subvektor di sebelah kanan hanya

memuat data-data yang mempunyai harga lebih besar dari 87. Dengan demikian,

data 87 akan ditempatkan pada urutan ke-2. Hasil dari proses pada langkah

pertama tersebut di atas selengkapnya adalah sebagai berikut:

74 71 75 25 56 87 100 90

Langkah berikutnya, elemen pertama pada subvektor kiri yaitu 74

dibandingkan dengan elemen data pada urutan kedua, ketiga, keempat, serta

kelima pada subvektor kiri. Dengan demikian 74 akan menempati urutan ke-4

dan akan membagi subvektor kiri menjadi dua subvektor baru, dimana subvektor

pertama akan berada di sebelah kiri yang hanya akan memuat data-data yang

26

lebih kecil atau sama dengan 74 dan subvektor kedua akan berada disebelah

kanan yang hanya akan memuat data-data yang lebih besar dari 74.

Pada saat yang bersamaan data-data pada subvektor kanan juga

dikenakan perlakuan yang sama. Data pertama pada subvektor kanan yaitu 100

akan dibandingkan dengan semua data dalam subvektor kanan, sehingga akan

membentuk dua subvektor baru. Berhubung cacah elemen pada subvektor

kanan hanya memiliki dua elemen data, maka subvektor baru yang terbentuk

akan menempatkan elemen 90 pada urutan lebih awal dan elemen 100 pada

urutan berikutnya. Akhir proses pada langkah ini akan memberikan hasil sebagai

berikut:

71 25 56 74 75 87 90 100

Langkah selanjutnya, elemen pertama pada subvektor kiri yaitu 71 akan

dibandingkan dengan elemen data 25 dan 56 pada subvektor bagian kiri.

Akhirnya subvektor kiri akan terbagi menjadi dua subvektor baru, dimana data 71

akan menempati urutan ke-3. Sedangkan masing - masing subvektor kanan

tinggal memiliki sebuah elemen data, sehingga tidak perlu diproses kembali.

Akhir proses pada langkah ini akan memberikan hasil sebagai berikut:

25 56 71 74 75 87 90 100

Dengan mengulang proses yang sama seperti diatas, maka pada

akhirnya akan diperoleh suatu vektor baru dalam kondisi urut secara naik, yaitu

sebagai berikut ini:

25 56 71 74 75 87 90 100

27

2.2.Metode Shell Short (Diminishing Increment)

Metode Shellsort (diminishing increment) pertama kali dikenalkan pada

tahun 1959 oleh Donald L.Shell. Proses pengurutan data dengan metode ini

secara ringkas dapat dijelaskan sebagai berikut ini. Untuk mengurutkan sebuah

vektor yang memuat N elemen data secara ascending, mula-mula data pertama

dibandingkan dengan data pada jarak tertentu dari data pertama tersebut, misal

N/6 atau N-5, N-4, N-3, N-2, atau N-1. Jika data pertama lebih besar, maka posisi

data saling ditukarkan. Berikutnya, data kedua dibandingkan dengan data pada

jarak yang sama sebagaimana dilakukan pada data pertama. Lakukan

pertukaran data jika diperlukan. Demikian seterusnya proses perbandingan dan

pertukaran data dilakukan pada seluruh data (data ke-N).

Pada langkah kedua, proses perbandingan dan pertukaran data seperti

di atas diulang kembali dengan jarak yang lebih kecil. Demikian juga untuk

langkah ketiga, keempat, kelima, hingga terakhir, proses perbandingan dan

pertukaran, (jika diperlukan) akan terus dilakukan dengan jarak yang semakin

diperkecil. Proses akan dihentikan hingga jarak perbandingan antar data sama

dengan satu. Dalam kondisi demikian ini, maka semua data dalam vektor N telah

menjadi urut naik.

Dalam metode Shellsort tidak ada ketentuan tentang seberapa jauh

jarak yang harus ditetapkan untuk perbandingan antar data pertama kali yang

kemudian akan dipersempit pada langkah-langkah selanjutnya. Semakin jauh

jarak perbandingan yang digunakan pertama kali akan mengakibatkan semakin

banyak proses perbandingan dan pertukaran antar data yang harus dilakukan.

Hal ini berarti proses pengurutan data akan menjadi tidak efisien. Jika

diharapkan efisiensi yang tinggi tentu akan digunakan jarak yang relatif kecil

28

sejak langkah pertama. Tetapi, cara yang seperti ini sungguh tidak dapat

menjamin keakuratan pada hasil operasi. Dengan menetapkan jarak

perbandingan sama dengan separuh dari cacah data keseluruhan (=N/2) untuk

langkah pertama, kemudian N/2-1, N/2-2, N/2-3, dan seterusnya pada langkah-

langkah berikutnya, pada umumnya akan memberikan efisiensi yang cukup baik.

Metode ini akan paling aman digunakan jika jarak yang digunakan pada langkah

pertama adalah N-1, kemudian N-2 pada langkah kedua, N-3 pada langkah

ketiga, dan seterusnya hingga proses berakhir. Namun, cara ini sama sekali tidak

efisien.

Berikut contoh pengurutan data ascending dengan metode Shellsort,

untuk sebuah vektor K yang memiliki delapan elemen data dalam kondisi acak

yaitu sebagai berikut:

90 15 95 30 35 100 12 25

Tabel 2.8. Contoh pengurutan data iascending dengan metode Shellsort Iterasi ke Jarak Hasil proses

0

1

2

3

4

5

6

7

-

7

6

5

4

3

2

1

90 15 95 30 35 100 12 25 25 15 95 30 35 100 12 90 12 15 95 30 35 100 25 90 12 15 90 30 35 100 25 95 12 15 25 30 35 100 90 95 12 15 25 30 35 95 90 100 12 15 25 30 35 95 90 100 12 15 25 30 35 95 90 100

Jika jarak untuk melakukan perbandingan pada langkah pertama adalah

N-1 atau sama dengan 7, maka jarak perbandingan pada langkah kedua adalah

29

6, jarak pada langkah ketiga adalah 5, dan pada langkah-langkah berikutnya

akan terus dikurangi satu hingga akhirnya sama dengan satu. Secara terinci,

proses pengurutan data dengan metode Shellsort untuk vektor K adalah seperti

ditunjukan dalam Tabel 2.8. Tanda garis bawah adalah menunjukan posisi awal

data yang akan saling dibandingkan pada langkah selanjutnya.

Algoritma prosedur pengurutan data secara urut naik dengan metode

Shellsort dapat dituliskan seperti di bawah ini.



1. Mulai

2. Tentukan harga awal jarak perbandingan data.

JARAK = N/2


while jarak >= 1

4. Proses berulang langkah-5 s/d langkah-6 untuk mengurutkan data

FOR I = 1 TO N-JARAK

5. Tentukan

J = I + JARAK

6. Bandingkan antar data

IF X[I] > X[J]

Jika ya, tukarkan posisi kedua data

BANTU = X[I]

X[I] = X[J]

X[J] = BANTU

7. Tentukan jarak baru untuk langkah berikutnya

JARAK = JARAK-1

8. Cetak hasil

9. Selesai

30

2.7. Metode Merge Sort (Two-way Marge Sort)

Metode merge sort juga disebut two way merge sort. Langkah-langkah

pengurutan dengan merge sort secara garis besar dapat dijelaskan sebagai

berikut ini. Andaikan terdapat sebuah vektor K dengan cacah elemen data

sebanyak N dalam kondisi tidak urut. Untuk mengurutkan semua data dalam K,

mula-mula setiap elemen dalam vektor K dianggap sebagai sebuah vektor yang

masing-masing mempunyai sebuah elemen data. Dengan demikian akan

terdapat N vektor dengan cacah elemen masing-masing adalah 1 buah.

Selanjutnya setiap pasang vektor yang berurutan digabungkan menjadi sebuah

vektor baru. Jika diinginkan hasil secara urut naik, maka pada saat

menggabungkan kedua vektor tersebut sekaligus dilakukan perbandingan dan

pertukaran posisi antar elemen data sedemikian rupa sehingga data yang lebih

kecil akan ditempatkan pada posisi yang mendahului data lain yang lebih besar.

Pada akhir langkah pertama ini, akan diperoleh vektor baru sebanyak N/2 yang

masing-masing dalam kondisi urut naik. Cacah elemen pada masing-masing

vektor adalah 2 buah, kecuali jika N bernilai ganjil maka akan terdapat N/2+1

vektor baru dimana salah satu vektor hanya memiliki sebuah elemen data saja.

Langkah selanjutnya, setiap pasang vektor yang berurutan digabungkan

sekaligus saling ditukarkan posisi antar data sehingga akan terbentuk vektor-

vektor baru. Proses penggabungan dan pertukaran posisi data tersebut akan

dilakukan terus-menerus hingga akhirnya diperoleh vektor baru yang memuat

semua elemen data dalam vektor sumber dalam kondisi urut.

Berikut contoh proses pengurutan ascending dengan metode merge sort

untuk sebuah vektor K dengan delapan elemen data sebagai berikut:

87 74 71 100 75 25 56 90

31

Ilustrasi proses pengurutan vektor K dengan metode merge sort secara

ringkas adalah ditunjukkan Gambar 2.10.

Gambar 2.10: Contoh ilustrasi pengurutan data dengan metode merge sort

Dalam contoh di atas, mula-mula vektor K akan dipecah menjadi vektor-

vektor baru yang masing-masing memiliki satu elemen data, sehingga akan

terdapat delapan vektor. Pada langkah pertama, setiap pasang vektor yang

berurutan akan digabungkan dan sekaligus dibandingkan untuk menempatkan

data yang lebih kecil pada lokasi yang lebih awal. Dalam contoh di atas 87 akan

digabungkan dengan 74, 71 dengan 100, 75 dengan 25, dan 56 dengan 90.

Dengan demikian langkah pertama akan menghasilkan empat vektor baru yang

masing-masing telah urut. Langkah ketiga akan menggabungkan kembali

sekaligus mengatur lokasi setiap data yang digabungkan tersebut sehingga

akhirnya akan menghasilkan dua vektor baru. Pada langkah terakhir, yaitu

langkah keempat, maka dua vektor hasil penggabungan pada langkah ketiga

akan digabungkan dan diatur kembali, sehingga akhirnya akan diperoleh vektor

baru yang urut secara naik, yaitu:

25 56 71 74 75 87 90 100

Dari ilustrasi di atas terlihat bahwa untuk mengurutkan vektor KK yang

memiliki delapan elemen data akan memerlukan 3 langkah penggabungan

Langkah-1: 87 74 71 100 75 25 56 90 N = 1 Langkah-2: 74 80 71 100 25 75 56 90 N = 2 Langkah-3: 71 74 80 100 25 56 75 90 N = 3 Langkah-4: 25 56 71 74 75 80 90 100 N = 4

32

dimana masing-masing langkah terdiri dari beberapa proses perbandingan dan

pertukaran lokasi elemen data.

Selanjutnya, untuk menuliskan solusi bentuk algoritma prosedur

pengurutan data secara urut naik dengan metode merge sort akan digunakan

beberapa variabel I, J, K, dan L, adalah sebagai pencacah pada proses

perulangan. Variabel N adalah menunjukkan cacah elemen vektor sumber KK.

Variabel ITERASI menyatakan banyaknya langkah yang harus dilakukan untuk

mengurutkan data. SUB ITERASI adalah variabel untuk menentukan banyaknya

sub iterasi pada setiap iterasi. Variabel UKURAN menunjukkan cacah elemen

vektor pada iterasi yang bersesuaian. Sedangkan R, S dan T adalah variabel-

variabel yang akan digunakan sebagai pencacah. Untuk memperoleh vektor

yang urut maka cacah iterasi yang harus dilakukan adalah sebanyak M dimana

sama dengan log2N. Algoritma prosedur pengurutan data dengan metode merge

sort dapat dituliskan sebagai berikut ini:


KK adalah vektor hasil dalam kondisi urut naik.

1. Mulai


FOR ITERASI = 1 TO M

3. Inisialisasikan untuk iterasi

UKURAN = 2..(ITERASI-1)

P = 1

Q = P + UKURAN

SUB ITERASI = N/(2x ITERASI)

4. Proses berulang langkah-5 s/d langkah-8 untuk setiap iterasi

FOR S = 1 TO SUB ITERASI

5. Inisialisasi prosedur simple merge

I = P

33

J = Q

T = P

6. Proses berulang untuk membandingkan antar data dan menemukan elemen

terkecil

WHILE ((I+1-P <= UKURAN) AND (J+1-Q <= UKURAN))

IF ITETRASI = “GANJIL”

Jika ya, IF K[I] <= K[J]

Jika ya, tentukan KK[T] = K[I]

I = I + 1

T = T + 1

Jika tidak, tentukan KK[T] = K[J]

J = J + 1

T = T + 1

Jika tidak, IF KK[I] <= KK[J]

Jika ya, tentukan K[T] = KK[I]

I = I + 1

T = T + 1

Jika tidak, tentukan K[T] = KK[J]

J = J + 1

T = T + 1

7. Copikan sisa elemen data yang tidak terproses dari vektor sumber ke vektor

hasil

IF I + 1 – P > UKURAN

Jika ya, IF ITERASI = “Ganjil”

Jika ya, lakukan proses berulang

FOR R = J TO Q + UKURAN-1

KK[T] = K[R]

T = T + 1

Jika tidak, lakukan proses berulang

FOR R = J TO Q + UKURAN – 1

K[T] = KK[R]

T = T + 1

Jika tidak, IF ITERASI = “Ganjil”


34

FOR R = I TO P + UKURAN – 1

KK[I] = K[R]

T = T +1

Jika tidak, lakukan proses berulang

FOR R = I TO P + UKURAN – 1

K[T] = KK[R]

T = T + 1

8. Perbaharui indikasi vektor

P = Q + UKURAN

Q = P + UKURAN

9. Copikan ulang jika diperlukan

IF M = “Ganjil”


FOR I = 1 TO N

K[I] = KK[I]

10. Cetak hasil

11. Selesai

Proses dalam algoritma di atas dapat dijelaskan sebagai berikut ini.

Langkah ke-1 adalah titik mulai proses dimana data yang akan diurutkan

diasumsikan telah dibaca sebelumnya. Langkah ke-2 memeriksa cacah iterasi

yang diperlukan dalam pengurutan data. Langkah ke-3 memeriksa cacah

masing-masing vektor baru (=UKURAN) yang digunakan dalam sub iterasi untuk

melakukan proses penggabungan. Langkah ini juga menghitung cacah prosedur

penggabungan (=SUB ITERASI) yang diperlukan dalam satu kali iterasi. Selain

itu, inisialisasi variabel K dan L dilakukan untuk menyimpan jejak vektor yang

digabungkan pada setiap sub iterasi ditetapkan dalam langkah ini. Langkah ke-4

adalah memeriksa cacah sub iterasi yang diperlukan pada setiap iterasi. Langkah

ke-5 adalah menginisialisasikan variabel-variabel I, J, dan T yang akan

35

digunakan sebagai indeks vektor yang akan digabungkan. Langkah ke-6 hingga

langkah ke-8 merupakan prosedur untuk melakukan penggabungan. Dalam

langkah ini, jika variabel ITERASI mempunyai nilai ganjil maka outputnya akan

disimpan dalam vektor C. Namun jika bernilai genap, maka outputnya akan

disimpan dalam vektor KK yaitu vektor hasil. Langkah ke-9 adalah menentukan

daerah vektor yang telah terurut / tersortir. Jika cacah ITERASI yang diperlukan

dalam menyortir vektor adalah ganjil, maka outputnya akan meliputi semua

elemen data yang telah terproses. Dalam kasus ini, maka elemen-elemen data

dalam vektor C akan dicopikan ke dalam vektor KK.

Metode ini cukup efisien untuk diterapkan. Untuk cacah iterasi

sebanyak M = Log2N, maka total perbandingan yang harus dilakukan adalah

sebanyak NxLog2N kali. Kelemahan metode ini adalah daerah output akan

memerlukan tempat yang sama ukuranya dengan vektor sumber. Algoritma

prosedur merge sort sebagaimana dituliskan di atas hanya diutamakan pada

vektor dengan cacah elemen N=2M. Tentunya algoritma prosedur tersebut dapat

dimodifikasi agar dapat mengatasi semua kasus pengurutan data secara umum.

2.8. Metode Radix Sort

Metode pengurutan dengan Radix Sort hanya ditujukan untuk

pengurutan data yang bertipe numerik saja. Dalam metode Radix Sort proses

pengurutan didasarkan pada harga sesungguhnya dari suatu digit pada bilangan-

bilangan yang hendak diurutkan. Dalam basis sistem bilangan desimal, maka

digit-digit suatu bilangan dapat dikelompokkan menjadi 10 kelompok, yaitu

kelompok “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, dan “9”. Dengan demikian harga

suatu bilangan dapat diidentifikasi ke dalam kelompok-kelompok digit tersebut.

36

Sebagai contoh pada bilangan 5426 angka 6 menempati pada digit “satuan”,

angka 2 menempati pada digit “puluhan”, angka 4 menempati pada digit

“ratusan”, dan angka 5 menempati pada digit “ribuan”. Untuk mengurutkan data-

data bertipe numerik, maka dapat dilakukan dengan cara membandingkan setiap

digit yang bersesuaian terhadap bilangan yang lain.

Pengurutan data dengan metode Radix Sort dilakukan dengan cara

membandingkan setiap digit bilangan yang akan diurutkan mulai dari digit paling

kiri yaitu digit yang mempunyai harga paling besar. Jika harganya sama maka

kemudian perlu dibandingkan kembali digit pada posisi di sebelah kanannya

hingga digit yang terakhir yaitu digit yang ditulis paling kanan. Pada saat dijumpai

adanya perbedaan nilai pada digit yang sama, maka dapat ditentukan bahwa

suatu bilangan adalah lebih besar atau lebih kecil berdasarkn harganya. Sebagai

contoh, data 6425 adalah lebih besar dari 5425, karena harga pada digit pertama

(dari kiri), yaitu 6 lebih besar dari 5.

Dalam contoh yang lain, 7254 adalah lebih kecil dari 7264. Jika

dibandingkan, digit 7 pada kedua bilangan tersebut mempunyai harga yang

sama, sehingga harus dibandingkan harga pada digit sebelah kanannya. Digit

kedua pada 7254, nilainya sama dengan digit kedua pada 7264, yaitu sama-

sama memiliki angka 2. Ini berarti harus dibandingkan kembali digit sebelah

kanannya. Ketika dibandingkan kembali, yaitu 5 pada 7254 dan digit 6 pada

angka 7264, maka digit 6 lebih besar daripada 5. Sehingga dapat disimpulkan

bahwa 7254 lebih kecil daripada 7264.

Dalam metode Radix sort, setiap data yang akan diurutkan perlu

dipisahkan ke dalam sejumlah digit sesuai kelompok-kelompoknya.

Pengelompokan dimulai pada digit paling kiri yaitu digit terbesar dan kemudian

37

diikuti oleh digit berikutnya yang lebih kecil hingga pada digit satuan yang

menempati posisi paling kanan. Untuk keperluan pengelompokan tersebut, jika

diperlukan dapat ditambahkan digit 0 untuk menyamakan panjang digit semua

data yang akan diurutkan.

38

BAB III METODOLOGI PENELITIAN

3.1. Metode Penelitian

Penelitian ini dilakukan dengan studi literatur dan 4pengujian contoh-

contoh kasus pengurutan data menggunakan simulasi program aplikasi

komputer. Langkah-langkah yang dilakukan dalam penelitian ini adalah:

1. Memahami prosedur pengurutan data dengan metode penyisipan biner

dari berbagai literatur dan referensi

2. Mengembangkan program aplikasi komputer sesuai dengan prosedur

dalam metode penyisipan biner

3. Menguji program aplikasi untuk beberapa kasus pengurutan data yang

berbeda

4. Menganalisis kemungkinan terjadinya kesalahan hasil operasi

pengurutan data

5. Mengembangkan alternatif solusi untuk perbaikan prosedur dalam

metode penyisipan biner

6. Menguji program aplikasi hasil perbaikan untuk beberapa kasus

pengurutan data yang berbeda

7. Menyusun dokumentasi laporan penelitian

3.2. Perancangan Program Aplikasi

Untuk mempermudah analisis dalam penelitian ini, maka perlu

dikembangkan alat bantu berupa program aplikasi komputer yang dikembangkan

dengan bahasa pemrograman Turbo Pascal. Program aplikasi dibuat dalam dua

versi, yaitu versi pertama untuk prosedur asli dan versi kedua untuk hasil

39

perbaikan. Untuk masing-masing versi, program aplikasi terdiri atas empat

bagian/modul, yaitu:

1. Bagian/modul untuk input data sumber

2. Bagian/modul untuk proses pengurutan data secara ascending

3. Bagian/modul untuk proses pengurutan data secara descending

4. Bagian/modul untuk menampilkan informasi pengecekan hasil pengurutan

Struktur program aplikasi komputer yang dikembangkan adalah ditunjukkan oleh

Gambar 3.1.

Gambar 3.1: Rancangan struktur program aplikasi

Tampilan dialog layar utama program aplikasi yang dikembangkan

dirancang sebagaimana ditunjukkan oleh Gambar 3.2.

Gambar 3.2: Rancangan dialog layar tampilan utama

PENGURUTAN DATA DENGAN METODE PENYISIPAN BINER

INPUT DATA

PROSES PENGURUTAN DESCENDING

PROSES PENGURUTAN ASCENDING

CEK HASIL PENGURUTAN


1. INPUT DATA 2. PENGURUTAN SECARA ASCENDING 3. PENGURUTAN SECARA DESCENDING 4. CEK HASIL PENGURUTAN 5. SELESAI MASUKAN PILIHAN ANDA [1..5] :

40

Fungsi masing-masing bagian/modul program aplikasi yang dirancang

adalah sebagai berikut:

1. INPUT DATA

Bagian/modul ini berfungsi sebagai tempat pemasukan data sumber yang

akan diurutkan. Bagian/modul ini merupakan tampilan dialog layar yang


Gambar 3.3: Rancangan dialog layar input data

2. PROSES PENGURUTAN ASCENDING

Bagian/modul ini berfungsi sebagai tempat pemrosesan pengurutan data

secara ascending. Bagian/modul ini merupakan tampilan dialog layar yang


Gambar 3.4: Rancangan dialog layar proses ascending

INPUT DATA

MASUKAN CACAH DATA SUMBER: 999 MASUKAN NILAI DATA KE-1 : 999 MASUKAN NILAI DATA KE-2 : 999 . . : . . : MASUKAN NILAI DATA KE-N : 999 TEKAN ENTER UNTUK KEMBALI KE MENU UTAMA

PENGURUTAN ASCENDING

CACAH DATA SUMBER : 999 DATA SUMBER : 999 999 999 999 999 999 999 999 999 999 HASIL PENGURUTAN : 999 999 999 999 999 999 999 999 999 999 TEKAN ENTER UNTUK KEMBALI KE MENU UTAMA

41

3. PROSES PENGURUTAN DESCENDING


secara descending. Bagian/modul ini merupakan tampilan dialog layar yang


Gambar 3.5: Rancangan dialog layar proses descending

4. CEK HASIL PENGURUTAN

Bagian/modul ini berfungsi sebagai tempat menampilkan informasi

pengecekan hasil pengurutan data. Bagian ini mempunyai dua kemungkinan,

yaitu hasil proses pengurutan ascending atau descending sesuai pilihan.

Bagian/modul ini merupakan tampilan dialog layar yang dirancang

sebagaimana ditunjukkan oleh Gambar 3.6, Gambar 3.7, Gambar 3.8 dan

Gambar 3.9.

Gambar 3.6: Rancangan dialog layar hasil pengecekan proses ascending

PENGURUTAN DESCENDING


CEK HASIL PENGURUTAN ASCENDING

HASIL PENGURUTAN SUDAH BENAR …! TEKAN ENTER UNTUK KEMBALI KE MENU UTAMA

42

Gambar 3.7: Rancangan dialog layar hasil pengecekan proses ascending

Gambar 3.8: Rancangan dialog layar hasil pengecekan proses descending

Gambar 3.9: Rancangan dialog layar hasil pengecekan proses descending

Program aplikasi dirancang hanya untuk mengolah input berupa bilangn

bulat dengan cacah data maksimal 100 buah. Hal ini dilakukan dengan alasan

program aplikasi hanya dimaksudkan sebagai alat bantu untuk menganalisis

validitas algoritma prosedur, bukan untukpengolahan data yang kompleks.

Statemen utama yang digunakan dalam program aplikasi antara lain adalah:


HASIL PENGURUTAN TIDAK BENAR …! KESALAHAN PADA NILAI : 999 URUTAN : 999 TEKAN ENTER UNTUK KEMBALI KE MENU UTAMA

CEK HASIL PENGURUTAN DESCENDING




43

1. Statemen input : berfungsi untuk memasukkan data sumber, yaitu

menggunakan statemen READ dan READLN

2. Statemen output : berfungsi untuk menampilkan data hasil proses

pengurutan data, yaitu menggunakan statemen WRITE dan WRITELN.

3. Statamen GOTOXY : berfungsi untuk untuk pengaturan tampilan input

dan output dalam dialog tampilan layar

4. Statemen FOR TO DO: berfungsi sebagai satemen kendali proses

perulangan selama pemasukan, pemrosesan mapun penampilan hasil

5. Statemen IF THEN : berfungsi sebagai statemen kendali pada saat

pembandingan nilai-nilai data

6. Statemen WHILE DO : berfungsi sebagai statemen kendali pada saat

penentuan lokasi penyisipan secara biner

Berdasarkan informasi yang diperoleh dari pengecekan hasil proses

pengurutan untuk beberapa data sumber yang berbeda, selanjutnya dapat

dianalisis permasalahan yang masih mungkin muncul dalam metode penyisipan

biner. Hasil analisis tersebut, selanjutnya dapat digunakan sebagai dasar untuk

melakukan perbaikan metode penyisipan biner. Program aplikasi versi pertama,

selanjutya dimodifikasi menjadi versi kedua berdasarkan hasil analisis yang

diperoleh tersebut.

3.3. Jadwal Waktu Penelitian

Penelitian ini dilaksanakan dalam jangka waktu 4 (empat) bulan, dengan

rincian kegiatan sebagaimana ditunjukkan oleh Tabel 3.1.

44

Tabel 3.1: Kegiatan dan alokasi waktu penelitian Tahap Kegiatan Waktu

Persiapan awal Mengumpulkan materi 4 Minggu

Pelaksanaan Menganalisis teori

Menguji data

Menyusun program

3 Minggu

3 Minggu

2 Minggu

Penyelesaian Menyusun laporan 4 Minggu

3.4. Beaya Penelitian

Rincian kebutuhan beaya penelitian ini ditunjukkan oleh Tabel 3.2.

Tabel 3.2: Kegiatan dan alokasi waktu penelitian No Komponen beaya Jumlah (Rupiah)

1. Tenaga Peneliti 300.000 2. Pustaka dan fotocopy bahan pustaka 600.000 3. Alat tulis, kertas, cartridge 500.000 4. Pengetikan 200.000 5. Akses internet 200.000 6. Fotocopy dan penjilidan laporan 200.000

TOTAL : 2.000.000

46

BAB IV PEMBAHASAN

4.1. Desain Program Aplikasi Versi Pertama

Untuk mempermudah analisis dalam penelitian ini, maka perlu

dikembangkan alat bantu berupa program aplikasi komputer yang dikembangkan

dengan bahasa pemrograman Turbo Pascal. Program aplikasi dibuat dalam dua

versi, yaitu versi pertama untuk prosedur asli dan versi kedua untuk hasil

perbaikan. Untuk masing-masing versi, program aplikasi terdiri atas empat

bagian/modul, yaitu:

1. Bagian/modul untuk input data sumber

2. Bagian/modul untuk proses pengurutan data secara ascending

3. Bagian/modul untuk proses pengurutan data secara descending

4. Bagian/modul untuk menampilkan informasi pengecekan hasil pengurutan

Program aplikasi dikembangkan berdasarkan algortima prosedur yang

telah tersedia dan banyak digunakan hingga saat ini. Struktur program aplikasi

komputer yang dikembangkan adalah ditunjukkan oleh Gambar 4.1.

Gambar 4.1: Struktur program aplikasi


INPUT DATA

PROSES PENGURUTAN DESCENDING

PROSES PENGURUTAN ASCENDING

CEK HASIL PENGURUTAN

47

Tampilan dialog layar utama program aplikasi yang dikembangkan

adalah ditunjukkan oleh Gambar 4.2.

Gambar 4.2: Tampilan dialog layar utama

Fungsi masing-masing bagian/modul program aplikasi yang dirancang

adalah sebagai berikut:

1. INPUT DATA

Bagian/modul ini berfungsi sebagai tempat pemasukan data sumber yang

akan diurutkan. Bagian/modul ini merupakan tampilan dialog layar untuk input

data sebagaimana ditunjukkan oleh Gambar 4.3.

Gambar 4.3: Dialog layar input data


1. INPUT DATA 2. PENGURUTAN SECARA ASCENDING 3. PENGURUTAN SECARA DESCENDING 4. CEK HASIL PENGURUTAN 5. SELESAI MASUKAN PILIHAN ANDA [1..5] :

INPUT DATA

MASUKAN CACAH DATA SUMBER: 999 MASUKAN NILAI DATA KE-1 : 999 MASUKAN NILAI DATA KE-2 : 999 . . : . . : MASUKAN NILAI DATA KE-N : 999 TEKAN ENTER UNTUK KEMBALI KE MENU UTAMA

48

2. PROSES PENGURUTAN ASCENDING


secara ascending. Bagian/modul ini merupakan tampilan dialog pengurutan

data secara ascending sebagaimana ditunjukkan oleh Gambar 4.4.

Gambar 4.4: Tampilan dialog layar pengurutan ascending

3. PROSES PENGURUTAN DESCENDING


secara descending. Bagian/modul ini merupakan tampilan dialog layar untuk

pengurutan data descending sebagaimana ditunjukkan oleh Gambar 4.5.

Gambar 4.5: Tampilan dialog layar pengurutan descending

PENGURUTAN ASCENDING


PENGURUTAN DESCENDING


49

4. CEK HASIL PENGURUTAN

Bagian/modul ini berfungsi sebagai tempat menampilkan informasi

pengecekan hasil pengurutan data. Bagian ini mempunyai dua kemungkinan,

yaitu hasil proses pengurutan ascending atau descending sesuai pilihan.

Bagian/modul ini merupakan tampilan dialog layar sebagaimana ditunjukkan

oleh Gambar 4.6, Gambar 4.7, Gambar 4.8 dan Gambar 4.9.

Gambar 4.6: Tampilan dialog layar hasil pengecekan pengurutan ascending

Gambar 4.7: Tampilan dialog layar hasil pengecekan pengurutan ascending

Gambar 4.8: Tampilan dialog layar hasil pengecekan descending







50

Gambar 4.9: Tampilan dialog layar hasil pengecekan descending

Program aplikasi dirancang hanya untuk mengolah input berupa bilangn

bulat dengan cacah data maksimal 100 buah. Hal ini dilakukan dengan alasan

program aplikasi hanya dimaksudkan sebagai alat bantu untuk menganalisis

validitas algoritma prosedur, bukan untukpengolahan data yang kompleks.

Statemen utama yang digunakan dalam program aplikasi antara lain adalah:

1. Statemen input : berfungsi untuk memasukkan data sumber, yaitu

menggunakan statemen READ dan READLN

2. Statemen output : berfungsi untuk menampilkan data hasil proses

pengurutan data, yaitu menggunakan statemen WRITE dan WRITELN

3. Statamen GOTOXY : berfungsi untuk untuk pengaturan tampilan input

dan output dalam dialog tampilan layar

4. Statemen FOR TO DO: berfungsi sebagai satemen kendali proses

perulangan selama pemasukan, pemrosesan mapun penampilan hasil

5. Statemen IF THEN : berfungsi sebagai statemen kendali pada saat

pembandingan nilai-nilai data

6. Statemen WHILE DO : berfungsi sebagai statemen kendali pada saat

penentuan lokasi penyisipan secara biner



51

Berdasarkan informasi yang diperoleh dari pengecekan hasil proses

pengurutan untuk beberapa data sumber yang berbeda, selanjutnya dapat

dianalisis permasalahan yang masih mungkin muncul dalam metode penyisipan

biner. Hasil analisis tersebut, selanjutnya dapat digunakan sebagai dasar untuk

melakukan perbaikan metode penyisipan biner. Program aplikasi versi pertama,

selanjutya dimodifikasi menjadi versi kedua berdasarkan hasil analisis yang

diperoleh tersebut.

4.2. Analisis Algoritma Metode Penyisipan Biner Versi Pertama

Penentuan lokasi penyisipan dalam contoh pengurutan data ascending

dengan metode penyisipan biner pada Tabel 2.7 adalah dihitung sebagaimana

ditunjukkan oleh Tabel 4.1. Data sumber yang digunakan adalah:

10 5 7 9 2 1

sedangkan hasil pengurutannya adalah:

1 2 5 7 9 10

Hasil proses pengurutan data tersebut telah memberikan hasil yang benar, yaitu

urut secara ascending.

Tabel 4.1: Contoh penentuan lokasi penyisipan ascending dengan metode biner

Iterasi ke I Data yg disisipkan

Kiri Kanan Tengah Lokasi penyisipan

1 2

3

4

5

2 3

4

5

6

5 7 7 9 9 2 2 1 1 1

1 1 2 1 3 1 1 1 1 1

1 2 2 3 3 4 1 5 2 1

1 1 2 2 3 2 1 3 1 1

1 - 2 - 3 - 1 - - 1

52

Berikut ini akan diberikan contoh kedua proses pengurutan data secara

ascending dengan metode penyisispan biner. Data sumber yang akan diurutkan

adalah sama dengan contoh sebelumnya dan ditambahkan data 8 dan 6 di

urutan selanjutnya, yaitu:

10 5 7 9 2 1 8 6

Hasil proses pengurutan pada setiap tahapan adalah ditunjukkan oleh Tabel 4.2.

Sedangkan penentuan lokasi penyisipan ascending dengan metode biner

ditunjukkan oleh Tabel 4.3.

Dalam contoh kedua ini, ternyata hasil proses pengurutan data pada

langkah ke-6 telah memberikan hasil yang salah, yaitu menempatkan data 8

justru pada urutan ke-4. Data 8 seharusnya ditempatkan pada urutan ke-5. Hasil

proses pengurutan pada langkah ke-6 adalah:

1 2 5 8 7 9 10 6

Tabel 4.2: Contoh kesalahan pengurutan dalam metode penyisipan biner

Iterasi Ke: Hasil Proses 0

1

2

3

4

5

6

7

10 5 7 9 2 1 8 6 5 10 7 9 2 1 8 6 5 7 10 9 2 1 8 6 5 7 9 10 2 1 8 6 2 5 7 9 10 1 8 6 1 2 5 7 9 10 8 6 1 2 5 8 7 9 10 6 1 2 6 5 8 7 9 10

53

Tabel 4.3: Contoh kesalahan penentuan lokasi penyisipan dengan metode biner



1 2

3

4

5

6

7

2 3

4

5

6

7

8

5 7 7 9 9 2 2 1 1 1 8 8 8 4 4 4

1 1 2 1 3 1 1 1 1 1 1 4 4 1 1 3

1 2 2 3 3 4 1 5 2 1 6 6 4 7 3 3

1 1 2 2 3 2 1 3 1 1 3 5 4 4 2 3

1 - 2 - 3 - 1 - - 1 - - 4 - - 3

Selanjutnya, ternyata kesalahan juga terjadi kembali pada langkah

selanjutnya, yaitu langkah ke-7. Proses pada langkah ke-7 menempatkan data 6

justru pada urutan ke-3. Data 6 seharusnya ditempatkan pada urutan ke-4. Hasil

proses pengurutan pada langkah ke-6 adalah:

1 2 6 5 8 7 9 10

Hasil yang diinginkan semestinya adalah data urut ascending, yaitu:

1 2 5 6 7 8 9 10

Berdasarkan contoh tersebut, dapat disimpulkan bahwa algoritma

prosedur penyisipan biner versi pertama masih mempunyai kelemahan, yaitu

kemungkinan masih terjadi kesalahan pada hasil proses pengurutan.

Sedangkan algoritma prosedur tersebut selama ini telah banyak digunakan

dalam berbagai proses pengurutan data, tanpa disadari bahwa ternyata memiliki

kelemahan dan sangat fatal.

54

Berdasarkan hasil analisis algoritma prosedur pengurutan data dengan

metode penyisipan biner yang ada dalam Bab II maupun dalam program aplikasi,

ternyata kesalahan adalah terjadi pada saat penentuan lokasi penyisipan yang

dilakukan secara biner (langkah ke-6). Potongan prosedur penentuan lokasi

penyisipan secara biner adalah sebagai berikut:


Jika ya, tentukan batas interval atas baru: ATAS = TENGAH-1

Jika tidak, tentukan batas interval bawah baru: BAWAH=TENGAH+1

Dalam prosedur tersebut, jika data yang akan disisipkan (=SISIP) kurang

dari nilai data pada posisi titik tengah (=X[TENGAH]), maka batas atas interval

penyisipan akan digeser pada posisi TENGAH-1. Prosedur ini ternyata

mengakibatkan kesalahan, yaitu apabila data pada posisi TENGAH-1 kurang dari

nilai data yang disisipkan (=SISIP), maka data tersebut akan digeser menempati

urutan selanjutnya (pada posisi TENGAH). Hal ini berarti nilai data pada urutan

TENGAH-1 tersebut justru tidak akan pernah ikut dibandingkan dengan data

yang akan disisipkan (=SISIP) tersebut.

Sebaliknya, jika data yang akan disisipkan (=SISIP) lebih dari nilai data

pada posisi titik tengah (=X[TENGAH]), maka batas bawah interval penyisipan

akan digeser pada posisi TENGAH+1. Prosedur ini juga akan mengakibatkan

kesalahan, yaitu apabila data pada posisi TENGAH+1 kurang dari nilai data yang

disisipkan (=SISIP), maka data tersebut akan dilewati begitu saja. Hal ini berarti

nilai data pada urutan TENGAH+1 tersebut justru tidak akan pernah ikut

dibandingkan dengan data yang akan disisipkan (=SISIP) tersebut.

Alternatif solusi perbaikan yang dapat dilakukan untuk menghindari

terlewatkannya suatu nilai data tertentu dalam larik data sumber adalah

55

mengubah prosedur penggeseran batas bawah dan batas atas interval (pada

langkah ke-6). Ketika nilai yang akan disisipkan ternyata kurang dari nilai data

pada posisi tengah interval, maka batas atas interval selanjutnya digeser ke

posisi TENGAH (bukan TENGAH-1). Dengan cara demikian, maka akan

terhindar dari kesalahan/terlewatinya proses perbandingan antar data,

khususnya data pada posisi TENGAH-1 yang bisa jadi mempunyai nilai lebih dari

nilai yang akan disipkan (=SISIP).

Pada sisi yag lain, ketika nilai yang akan disisipkan ternyata lebih dari

nilai data pada posisi tengah interval, maka batas bawah interval selanjutnya

digeser ke posisi TENGAH (bukan TENGAH+1). Dengan cara demikian, maka

akan terhindar dari kesalahan/terlewatinya proses perbandingan antar data,

khususnya data pada posisi TENGAH+1 yang bisa jadi mempunyai nilai kurang

dari nilai yang akan disipkan (=SISIP).

Selain itu, perbaikan juga perlu dilakukan untuk menghindari proses

perulangan yang hanya berputar-putar saja dan tidak pernah berhenti, yaitu

ketika batas bawah atau batas atas telah digeser ke posisi tengah interval

ternyata hasil perhitungan TENGAH yang baru tetap sama dengan nilai TENGAH

yang lama (=TENGAH_LAMA). Dalam kondisi seperti ini, jika nilai data yang

akan disisipkan kurang dari nilai data pada posisi TENGAH, maka batas atas

akan digeser menjadi TENGAH_LAMA+1. Sebaliknya, jika nilai data yang akan

disisipkan lebih dari nilai data pada posisi TENGAH, maka batas atas akan

digeser menjadi TENGAH_LAMA-1.

Dalam kondisi dimana hasil perhitungan TENGAH yang baru tidak

sama dengan nilai tengah yang lama, maka penentuan lokasi penyisipan tidak

mengalami perubahan.

56

Dengan demikian, maka secara keseluruhan algoritma prosedur

pengurutan data secara ascending dengan metode penyisipan biner dapat

diperbaiki menjadi sebagai berikut:



1. Mulai


FOR I = 2 TO N

3. Tentukan elemen yang akan disisipkan dan harga awal batas-batas interval

SISIP = X[I], BAWAH = 1, ATAS = I-1

4. Proses berulang langkah-5 s/d langkah-7 untuk mencari lokasi penyisipan

data

WHILE BAWAH <= ATAS

5. Tentukan titik tengah interval

TENGAH_LAMA= TENGAH

TENGAH = (BAWAH+ATAS) DIV 2

6. Cek nilai TENGAH

IF TENGAH=TENGAH_LAMA


Jika ya, tentukan batas interval atas baru: ATAS=TENGAH_LAMA-1

Jika tidak, tentukan batas interval bawah baru: BAWAH=TENGAH_LAMA+1 7. Mencari lokasi penyisipan

IF TENGAH<>TENGAH_LAMA


Jika ya, tentukan batas interval atas baru: ATAS=TENGAH_LAMA

Jika tidak, tentukan batas interval bawah baru: BAWAH=TENGAH_LAMA 8. Proses berulang langkah-9

FOR J = I -1 DOWNTO BAWAH

9. Menggeser data-data

X[J+1] = X[J]

10. Sisipkan data

57

X[BAWAH] = T

11. Selesai

4.3. Implementasi Program Aplikasi Versi Kedua

Program aplikasi versi kedua dikembangkan berdasarkan algoritma

prosedur baru yang sudah diperbaiki sebagaimana telah dituliskan di atas.

Dengan menggunakan program aplikasi versi kedua ini, maka kesalahan

yang terjadi dalam contoh proses pengurutan data sebelumnya dapat dihindari.

Hasil proses pengurutan pada setiap tahapan adalah ditunjukkan oleh Tabel 4.4.

Sedangkan penentuan lokasi penyisipan ascending dengan metode biner

ditunjukkan oleh Tabel 4.5.

Tabel 4.4: Contoh pengurutan dengan metode penyisipan biner (hasil perbaikan)

Iterasi Ke: Hasil Proses 0

1

2

3

4

5

6

7

10 5 7 9 2 1 8 6 5 10 7 9 2 1 8 6 5 7 10 9 2 1 8 6 5 7 9 10 2 1 8 6 2 5 7 9 10 1 8 6 1 2 5 7 9 10 8 6 1 2 5 7 8 9 10 6 1 2 5 6 7 8 9 10

58

Tabel 4.5: Contoh penentuan lokasi penyisipan dengan metode biner (hasil

perbaikan)



1 2

3

4

5

6

7

2 3

4

5

6

7

8

5 7

9

2

1

8

4

1 1 2 1 2 3 1 1 1 1 1 1 3 4 4 5 1 1 2

1 2 2 3 3 3 4 2 5 3 2 6 6 6 5 5 7 4 4

1 1 2 2 2 3 2 1 3 2 1 3 4 5 4 5 4 2 3

1 - 2 - - 3 - 1 - - 1 - - - - 5 - - 3

Dalam contoh kedua ini, hasil proses pengurutan data telah

memberikan hasil yang benar. Hasil proses pengurutan pada langkah ke-6

adalah:

1 2 5 7 8 9 10 6

Sedangkan hasil akhir proses pengurutannya adalah:

1 2 5 6 7 8 9 10

Sebagai catatan tambahan, sebenarnya kesalahan hasil pengurutan data

dengan metode penyisipan biner tersebut bisa juga terjadi pada saat pengurutan

descending. Tentusaja perbaikannya dapat dilakukan juga dengan analogi yang

sama dengan perbaikan dalam algpritma prosedur sebagaimana telah dijelaskan

di atas

59

BAB V KESIMPULAN

Penelitian ini bertujuan untuk mengkaji kemungkinan adanya kelemahan

dalam metode penyisipan biner dan memberikan perbaikan terhadap metode

tersebut sehingga diperoleh jaminan bahwa penggunaan metode yang sudah

diperbaiki tersebut akan memberikan hasil berupa data urut naik / turun.

Berdasarkan hasil analisis algoritma yang dilakukan dan hasil output

yang dihasilkan program aplikasi pengurutan data dengan metode penyisipan

biner yang dikembangkan dalam, maka penelitian ini dapat diberikan

kesimpulan sebagai berikut:

1. Penggunaan metode penyisipan biner yang selama ini digunakan masih

memiliki kelemahan yaitu terjadinya kesalahan hasil operasi pengurutan

data

2. Kesalahan tersebut terjadi pada saat penggeseran batas interval baru (baik

batas atas maupun batas bawah) yang ditentukan sebagai upaya

meningkatkan efisiensi prose pengurutan data

3. Perbaikan dapat dilakukan berkaitan dengan proses penggeseran batas

interval, yaitu:

a. Jika perhitungan titik tengah interval yang baru sama dengan titik

interval yang lama, maka :

• Jika nilai yang disisipkan kurang dari nilai data pada posisi tengah,

maka batas atas interval yang baru adalah sama dengan TENGAH-1

• Jika nilai yang disisipkan lebih dari nilai data pada posisi tengah,

maka batas atas interval yang baru adalah sama dengan

TENGAH+1

60

b. Jika perhitungan titik tengah interval yang baru tidak sama dengan titik

interval yang lama, maka :

• Jika nilai yang disisipkan kurang dari nilai data pada posisi tengah,

maka batas atas interval yang baru adalah sama dengan TENGAH

yang lama

• Jika nilai yang disisipkan lebih dari nilai data pada posisi tengah,

maka batas atas interval yang baru adalah sama dengan TENGAH

yang lama

Hasil penelitian ini diharapkan memberikan masukan bagi parav

pemrogram aplikasi dalam menerapkan metode penyisipan biner agar terhindar

dari kesalahan hasil operasi.

61

DAFTAR PUSTAKA

Alfred V., Aho; Hopcraft, John; Ullman, Jefffrey D., The Design and Analysis of Computer Algorithms, NHSS Addison Wesley Publising Co. Behforooz, Ali; Holoien, Martin O., 1986, Problem Solving and Structured Programming with PASCAL, Brooks/Cole Publishing Co., A Division of Wadworth Inc., California Brand, Kolman W., 1986, Problem Solving with PASCAL, Kent Publishing Co., A Division of Wadworth Inc., USA Goodman, SE.; Hedetniemi, S.T., 1985, Introduction to the Design and Analysis of Algorithms, Mc.Graw_Hill Int’l Book Co. Lipshutz, Martin M.; Lipschutz, Seymour, 1982, Theory and Problems of Data Processing, Schaum’s Outline Series, McGraw_Hill Int’l Book Co. Lipschutz, Seymour; Lipson, Marc L., 1992, 2000 Solved Problems in Discrette Mathematics, Mc.Graw_Hill Int’l Book Co., USA Lisanti, Barbara; Mann, Lydia; Zlotnick Freed, 1987, Algorithms, Programming, Pascal, Wardworth Publishing Co., California Trembly, Jean P.,; Bunt, Richard B., 1981, An Introduction to Computer Science an Algorithmic Approach, Int’l Student edition, McGraw_Hill Int’l Book Co., Singapore Trembly ; Sorenson, An Introduction to the Design and Analysis of Algorithms, McGraw_Hill Int’l Book Co. Wirth, Niklaus, 1991, Algorithms + Data Structures = Programs, Prentice Hall Int’l Inc., Englewood Clifs, New Jersey

2003 edhy sutanta laporan penelitian 30 mei 2003 hal i-vii dan 1

Documents