DIKTAT PEMROGRAMAN PASCAL
SEMESTER 2
Algoritma Pengurutan Quick Sort
Quick sort merupakan divide and conquer algorithm. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) lalu menyimpan semua elemen yang lebih kecil di sebelah kirinya dan semua elemen yang lebih besar di sebelah kanannya. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut. Algoritma ini termasuk algoritma yang cukup baik dan cepat. Hal penting dalam algoritma ini adalah pemilihan nilai tengah yang baik sehingga tidak memperlambat proses sorting secara keseluruhan.
Ide dari algoritma ini adalah sebagai berikut:
a. Pilih satu elemen secara acak
b. Pindahka semua elemen yang lebih kecil ke sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan di salah satunya. Ini disebut operasi partisi
c. Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya.
Quick sort adalah pengembangan dari binary tree sort, yang lebih menghemat ruang. Cara perbandingannya mirip, hanya pengurutannya berbeda. dibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar Θ(log n), dibanding dengan merge sort sebesar Θ(n). Namun quick sort tidak mampu membandingkan linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada linked list merge sort memerlukan ruang yang lebih sedikit. Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optmal.
Kompleksitas algoritma Quick Sort adalah bergantung pada hasil partisi tersebut. Kondisi best case adalah jika dalam setiap partisi tidak dilakukan operasi pertukaran tempat dan pivot tepat berada di tengah subset (O(n)). Kondisi average case adalah jika partisi menghasilkan sub data set yang balance (O(n log n)). Kondisi worse case adalah jika partisi menghasilkan sub data set kosong dan yang lain besar (o(n2)). Walaupun demikian, algoritma ini cenderung untuk average case.
Procedure Quick (int data[ ], int awal, int akhir)
kiri = awal
kanan = akhir
While (kiri < kanan)
pivot = kiri
While (data[ pivot ] <= data[ kanan ]) dan (pivot < kanan)
kanan = kanan – 1
Endwhile
If (data[ pivot ] > data[ kanan ] then
tukar (data[ pivot ], data[ kanan ])
Endif
pivot = kanan
While (data[ kiri ] <= data[ pivot ]) dan (kiri < pivot)
kiri = kiri + 1
Endwhile
If (data[ kiri ] > data[ pivot ])
tukar (data[ kiri ], data[ pivot ])
Endif
Endwhile
If (kanan>awal) Quick(data,awal,(pivot-1))
If (kiri<akhir) Quick(data,(pivot+1),akhir)
End
PENCARIAN DATA
Pencarian adalah proses yang mendasar dalam pengolahan data. Begitu juga pencarian elemen di dalam senarai. Sebelum penyisipan elemen misalnya, harus dicari terlebih dahulu posisi penyisipan (untuk mendapatkan calon elemen predesesor dan suksesor dari elemen yang akan disisipkan). Variabel merupakan suatu nilai yang disimpan dalam memory yang dapat diakses dengan identifier. Variabel ini sesunggunhnya disimpan pada suatu alamat didalam memory. Dimana setiap alamat memory akan berbeda dengan yang lainnya (unik).
Variabel pointer sering dikatakan sebagai variabel yang menunjuk ke obyek lain. Pada kenyataan yang sebenarnya, variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang dikatakan ditunjuk oleh pointer). Sebagai contoh, px adalah variabel pointer dan x adalah variabel yang ditunjuk oleh px. Kalau x berada pada alamat memori (alamat awal) 1000, maka px akan berisi 1000.
Mendeklarasikan Variabel Pointer
Suatu variabel pointer dideklarasikan dengan bentuk sebagai berikut :
tipe *nama_variabel
dengan tipe dapat berupa sembarang tipe yang sudah dibahas pada bab-bab sebelumnya, maupun bab-bab berikutnya. Adapun nama_variabel adalah nama dari variabel pointer.
Sebagai contoh :
int *px; //contoh 1
char *pch1, *pch2; //contoh 2
Contoh pertama menyatakan bahwa px adalah variabel pointer yang menunjuk ke suatu data bertipe int, sedangkan contoh kedua masing pch1 dan pch2 adalah variabel pointer yang menunjuk ke data bertipe char.
Bentuk umum deklarasi pointer :
Type Pengenal = ^simpul ;
Simpul = tipe data ;
dengan pengenal : nama pengenal yang menyatakan tipe data pointer
simpul : nama simpul
tipe data : tipe data dari simpul
Tanda ^ di depan simpul harus ditulis apa adanya karena itu menunjukkan bahwa pengenal bertipe pointer. Tipe data dari simpul dapat berupa tipe data sebarang, misalnya char, integer, atau real.
Contoh :
Type Str30 = string[30] ;
Point = ^Data ;
Data = record
Nama_Peg : Str30 ;
Alamat : Str30 ;
Pekerjaan : Str30 ;
End ;
Var
P1, P2 : Point ;
A, B, C : Str30 ;
Mengatur Pointer agar Menunjuk ke Variabel Lain
Agar suatu pointer menunjuk ke variabel lain, mula-mula pointer harus diisi dengan alamat dari variabel yang akan ditunjuk. Untuk menyatakan alamat dari suatu variabel, operator & (operator alamat, bersifat unary) bisa dipergunakan, dengan menempatkannya di depan nama variabel. Sebagai contoh, bila x dideklarasikan sebagai variabel bertipe int, maka: &x . Berarti “alamat dari variabel x”. Adapun contoh pemberian alamat x ke suatu variabel pointer px (yang dideklarasikan sebagai pointer yang menunjuk ke data bertipe int) yaitu : px = &x;
Pernyataan di atas berarti bahwa px diberi nilai berupa alamat dari variabel x. Setelah pernyataan tersebut dieksekusi barulah dapat dikatakan bahwa px menunjuk ke variabel x.
Mengakses Isi Suatu Variabel Melalui Pointer
Jika suatu variabel sudah ditunjuk oleh pointer, variabel yang ditunjuk oleh pointer tersebut dapat diakses melalui variabel itu sendiri (pengaksesan langsung) ataupun melalui pointer (pengaksesan tak langsung). Pengaksesan tak langsung dilakukan dengan menggunakan operator indirection (tak langsung) berupa simbol * (bersifat unary).
Contoh penerapan operator * yaitu : *px
Yang menyatakan “isi atau nilai variabel/data yang ditunjuk oleh pointer px” . Sebagai contoh jika y bertipe int, maka sesudah dua pernyataan berikut:
px = &x;
y = *px;
y akan berisi nilai yang sama dengan nilai x. Kedua pernyataan di atas sebenarnya dapat digantikan dengan sebuah pernyataan berupa :
y = x;
Seandainya pada program di atas tidak terdapat pernyataan:
px = &x;
namun terdapat pernyataan
y = *px;
maka y tidaklah berisi nilai x, sebab px belum diatur agar menunjuk ke variabel x.
Hal seperti ini harap diperhatikan. Kalau program melibatkan pointer, dan pointer belum diinisialisasi, ada kemungkinan akan terjadi masalah yang dinamakan “bug” yang bisa mengakibatkan komputer tidak dapat dikendalikan (hang). Selain itu tipe variabel pointer dan tipe data yang ditunjuk harus sejenis. Bila tidak sejenis maka akan terjadi hasil yang tidak diinginkan.
Tipe Data Pointer
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam pengingat computer di mana data yang diwakili oleh tipe data tersebut disimpan.
Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah (Var) untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut.
Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable).
Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah.
Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasika sbb : Var matriks: array[1..100,1..100] of integer; maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data.
Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan.
Jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki,maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
Dengan kata lain, pada saat program dikompilasi, lokasi untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis.
Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan Pointer yang artinya menunjuk ke sesuatu. Dalam peubah dinamis, nilai dari data yang ditunjuk oleh suatu pointer biasanya disebut Simpul / node.
Pencarian Berdasarkan Nilai
Pencarian ini biasanya dilakukan untuk mengenali elemen senarai berdasarkan informasi yang dikandung di dalam elemen yang dicari. Keluaran proses pencarian bergantung pada kebutuhan, apakah hanya sekedar mengetahui sebuah elemen terdapat di dalam senarai, atau melakukan proses terhadap elemen yang ditemukan.
Bila tujuan kedua yang diinginkan, maka keluaran dari proses pencarian adalah alamat elemen yang dicari. Alamat ini nantinya diperlukan untuk pemrosesan elemen selanjutnya.
Pencarian adalah proses yang mendasar dalam pengolahan data. Begitu juga pencarian elemen di dalam senarai. Sebelum penyisipan elemen misalnya, harus dicari terlebih dahulu posisi penyisipan (untuk mendapatkan calon elemen predesesor dan suksesor dari elemen yang akan disisipkan). Variabel merupakan suatu nilai yang disimpan dalam memory yang dapat diakses dengan identifier. Variabel ini sesunggunhnya disimpan pada suatu alamat didalam memory. Dimana setiap alamat memory akan berbeda dengan yang lainnya (unik).
Variabel pointer sering dikatakan sebagai variabel yang menunjuk ke obyek lain. Pada kenyataan yang sebenarnya, variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang dikatakan ditunjuk oleh pointer). Sebagai contoh, px adalah variabel pointer dan x adalah variabel yang ditunjuk oleh px. Kalau x berada pada alamat memori (alamat awal) 1000, maka px akan berisi 1000.
Mendeklarasikan Variabel Pointer
Suatu variabel pointer dideklarasikan dengan bentuk sebagai berikut :
tipe *nama_variabel
dengan tipe dapat berupa sembarang tipe yang sudah dibahas pada bab-bab sebelumnya, maupun bab-bab berikutnya. Adapun nama_variabel adalah nama dari variabel pointer.
Sebagai contoh :
int *px; //contoh 1
char *pch1, *pch2; //contoh 2
Contoh pertama menyatakan bahwa px adalah variabel pointer yang menunjuk ke suatu data bertipe int, sedangkan contoh kedua masing pch1 dan pch2 adalah variabel pointer yang menunjuk ke data bertipe char.
Bentuk umum deklarasi pointer :
Type Pengenal = ^simpul ;
Simpul = tipe data ;
dengan pengenal : nama pengenal yang menyatakan tipe data pointer
simpul : nama simpul
tipe data : tipe data dari simpul
Tanda ^ di depan simpul harus ditulis apa adanya karena itu menunjukkan bahwa pengenal bertipe pointer. Tipe data dari simpul dapat berupa tipe data sebarang, misalnya char, integer, atau real.
Contoh :
Type Str30 = string[30] ;
Point = ^Data ;
Data = record
Nama_Peg : Str30 ;
Alamat : Str30 ;
Pekerjaan : Str30 ;
End ;
Var
P1, P2 : Point ;
A, B, C : Str30 ;
Mengatur Pointer agar Menunjuk ke Variabel Lain
Agar suatu pointer menunjuk ke variabel lain, mula-mula pointer harus diisi dengan alamat dari variabel yang akan ditunjuk. Untuk menyatakan alamat dari suatu variabel, operator & (operator alamat, bersifat unary) bisa dipergunakan, dengan menempatkannya di depan nama variabel. Sebagai contoh, bila x dideklarasikan sebagai variabel bertipe int, maka: &x . Berarti “alamat dari variabel x”. Adapun contoh pemberian alamat x ke suatu variabel pointer px (yang dideklarasikan sebagai pointer yang menunjuk ke data bertipe int) yaitu : px = &x;
Pernyataan di atas berarti bahwa px diberi nilai berupa alamat dari variabel x. Setelah pernyataan tersebut dieksekusi barulah dapat dikatakan bahwa px menunjuk ke variabel x.
Mengakses Isi Suatu Variabel Melalui Pointer
Jika suatu variabel sudah ditunjuk oleh pointer, variabel yang ditunjuk oleh pointer tersebut dapat diakses melalui variabel itu sendiri (pengaksesan langsung) ataupun melalui pointer (pengaksesan tak langsung). Pengaksesan tak langsung dilakukan dengan menggunakan operator indirection (tak langsung) berupa simbol * (bersifat unary).
Contoh penerapan operator * yaitu : *px
Yang menyatakan “isi atau nilai variabel/data yang ditunjuk oleh pointer px” . Sebagai contoh jika y bertipe int, maka sesudah dua pernyataan berikut:
px = &x;
y = *px;
y akan berisi nilai yang sama dengan nilai x. Kedua pernyataan di atas sebenarnya dapat digantikan dengan sebuah pernyataan berupa :
y = x;
Seandainya pada program di atas tidak terdapat pernyataan:
px = &x;
namun terdapat pernyataan
y = *px;
maka y tidaklah berisi nilai x, sebab px belum diatur agar menunjuk ke variabel x.
Hal seperti ini harap diperhatikan. Kalau program melibatkan pointer, dan pointer belum diinisialisasi, ada kemungkinan akan terjadi masalah yang dinamakan “bug” yang bisa mengakibatkan komputer tidak dapat dikendalikan (hang). Selain itu tipe variabel pointer dan tipe data yang ditunjuk harus sejenis. Bila tidak sejenis maka akan terjadi hasil yang tidak diinginkan.
Tipe Data Pointer
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam pengingat computer di mana data yang diwakili oleh tipe data tersebut disimpan.
Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah (Var) untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut.
Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable).
Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah.
Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasika sbb : Var matriks: array[1..100,1..100] of integer; maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data.
Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan.
Jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki,maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
Dengan kata lain, pada saat program dikompilasi, lokasi untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis.
Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan Pointer yang artinya menunjuk ke sesuatu. Dalam peubah dinamis, nilai dari data yang ditunjuk oleh suatu pointer biasanya disebut Simpul / node.
Pencarian Berdasarkan Nilai
Pencarian ini biasanya dilakukan untuk mengenali elemen senarai berdasarkan informasi yang dikandung di dalam elemen yang dicari. Keluaran proses pencarian bergantung pada kebutuhan, apakah hanya sekedar mengetahui sebuah elemen terdapat di dalam senarai, atau melakukan proses terhadap elemen yang ditemukan.
Bila tujuan kedua yang diinginkan, maka keluaran dari proses pencarian adalah alamat elemen yang dicari. Alamat ini nantinya diperlukan untuk pemrosesan elemen selanjutnya.
Quick Sort
Algoritma ini berdasarkan pada pola divide-and- conquer, adapun langkah-langkahnya:
1. Divide
Memilah rangkaian data mengjadi dua sub rangkaian A[p..q-1] dan A[q+1..r] dimana setiap elemen A[p..q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1..r] adalah lebih besar atau sam dengan elemen pa A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu begian dari procedure pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara reqursif
Insertsion Sort
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya.
Pengurtan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Marge Sort
Marge sort menggunakan pola divide and conquer, yang dirumuskan dalam 3 langkah:
1. Divide
Memilah elemen-elemen dari rangkaian data menjadi dua bagian
2. Conquer
Conquer setiap bagian dengan memanggil procedure marge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Function MargeSort(var La:list; Ca:integer):list;
Var Temp,Temp1,Temp2: List;
Begin
If La=nil then
MargeSort:=nil
Else
Begin
If Ca>1 then
Begin
Temp1:=MargeSort(La,Ca div 2);
Temp2:=MargeSort(La,(Ca+1) div 2);
MargeSort:=Marge(Temp1,Temp2)
End
Else
Begin
Temp:=La;
La:=La^.Kanan;
Temp^.Kanan:=nil;
MargeSort:=Temp
End
End;
Algoritma ini berdasarkan pada pola divide-and- conquer, adapun langkah-langkahnya:
1. Divide
Memilah rangkaian data mengjadi dua sub rangkaian A[p..q-1] dan A[q+1..r] dimana setiap elemen A[p..q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1..r] adalah lebih besar atau sam dengan elemen pa A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu begian dari procedure pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara reqursif
Insertsion Sort
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya.
Pengurtan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Marge Sort
Marge sort menggunakan pola divide and conquer, yang dirumuskan dalam 3 langkah:
1. Divide
Memilah elemen-elemen dari rangkaian data menjadi dua bagian
2. Conquer
Conquer setiap bagian dengan memanggil procedure marge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Function MargeSort(var La:list; Ca:integer):list;
Var Temp,Temp1,Temp2: List;
Begin
If La=nil then
MargeSort:=nil
Else
Begin
If Ca>1 then
Begin
Temp1:=MargeSort(La,Ca div 2);
Temp2:=MargeSort(La,(Ca+1) div 2);
MargeSort:=Marge(Temp1,Temp2)
End
Else
Begin
Temp:=La;
La:=La^.Kanan;
Temp^.Kanan:=nil;
MargeSort:=Temp
End
End;
SORTING ( POINTER )
Pengurutan dalam struktur data sangat penting terutama untuk data yang bertipe data numeric ataupun. Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25 Descending : 25 10 8 6 5 3 1
Bubble Sort
Bubble sort melakukan pengurutan dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.
procedure bubblesort (Pertama:PtrSimpul);
var
PtrData,PtrData2:Ptrsimpul;
a :integer;
begin
PtrData:=Pertama;
while PtrData <> NIL do
begin
PtrData2:=PtrData^.lnjt;
while PtrData2 <> NIL do
begin
if PtrData^.x > PtrData2^.x then
begin
a:=PtrData^.x;
PtrData^.x:=PtrData2^.x;
PtrData2^.x:=a;
end;
PtrData2:=PtrData2^.lnjt;
end;
PtrData:=PtrData^.lnjt;
end;
end;
Quick Sort
Algoritma ini berdasarkan pada pola divide-and- conquer, adapun langkah-langkahnya:
1. Divide
Memilah rangkaian data mengjadi dua sub rangkaian A[p..q-1] dan A[q+1..r] dimana setiap elemen A[p..q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1..r] adalah lebih besar atau sam dengan elemen pa A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu begian dari procedure pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara reqursif
Marge Sort
Marge sort menggunakan pola divide and conquer, yang dirumuskan dalam 3 langkah:
1. Divide
Memilah elemen-elemen dari rangkaian data menjadi dua bagian
2. Conquer
Conquer setiap bagian dengan memanggil procedure marge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Function MargeSort(var La:list; Ca:integer):list;
Var Temp,Temp1,Temp2: List;
Begin
If La=nil then
MargeSort:=nil
Else
Begin
If Ca>1 then
Begin
Temp1:=MargeSort(La,Ca div 2);
Temp2:=MargeSort(La,(Ca+1) div 2);
MargeSort:=Marge(Temp1,Temp2)
End
Else
Begin
Temp:=La;
La:=La^.Kanan;
Temp^.Kanan:=nil;
MargeSort:=Temp
End
End;
Pengurutan dalam struktur data sangat penting terutama untuk data yang bertipe data numeric ataupun. Pengurutan (Sorting) adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25 Descending : 25 10 8 6 5 3 1
Bubble Sort
Bubble sort melakukan pengurutan dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.
procedure bubblesort (Pertama:PtrSimpul);
var
PtrData,PtrData2:Ptrsimpul;
a :integer;
begin
PtrData:=Pertama;
while PtrData <> NIL do
begin
PtrData2:=PtrData^.lnjt;
while PtrData2 <> NIL do
begin
if PtrData^.x > PtrData2^.x then
begin
a:=PtrData^.x;
PtrData^.x:=PtrData2^.x;
PtrData2^.x:=a;
end;
PtrData2:=PtrData2^.lnjt;
end;
PtrData:=PtrData^.lnjt;
end;
end;
Quick Sort
Algoritma ini berdasarkan pada pola divide-and- conquer, adapun langkah-langkahnya:
1. Divide
Memilah rangkaian data mengjadi dua sub rangkaian A[p..q-1] dan A[q+1..r] dimana setiap elemen A[p..q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1..r] adalah lebih besar atau sam dengan elemen pa A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu begian dari procedure pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara reqursif
Marge Sort
Marge sort menggunakan pola divide and conquer, yang dirumuskan dalam 3 langkah:
1. Divide
Memilah elemen-elemen dari rangkaian data menjadi dua bagian
2. Conquer
Conquer setiap bagian dengan memanggil procedure marge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Function MargeSort(var La:list; Ca:integer):list;
Var Temp,Temp1,Temp2: List;
Begin
If La=nil then
MargeSort:=nil
Else
Begin
If Ca>1 then
Begin
Temp1:=MargeSort(La,Ca div 2);
Temp2:=MargeSort(La,(Ca+1) div 2);
MargeSort:=Marge(Temp1,Temp2)
End
Else
Begin
Temp:=La;
La:=La^.Kanan;
Temp^.Kanan:=nil;
MargeSort:=Temp
End
End;
SEARCHING ( POINTER )
Pencarian adalah proses yang mendasar dalam pengolahan data. Begitu juga pencarian elemen di dalam senarai. Sebelum penyisipan elemen misalnya, harus dicari terlebih dahulu posisi penyisipan (untuk mendapatkan calon elemen predesesor dan suksesor dari elemen yang akan disisipkan). Variabel merupakan suatu nilai yang disimpan dalam memory yang dapat diakses dengan identifier. Variabel ini sesunggunhnya disimpan pada suatu alamat didalam memory. Dimana setiap alamat memory akan berbeda dengan yang lainnya (unik).
Variabel pointer sering dikatakan sebagai variabel yang menunjuk ke obyek lain. Pada kenyataan yang sebenarnya, variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang dikatakan ditunjuk oleh pointer). Sebagai contoh, px adalah variabel pointer dan x adalah variabel yang ditunjuk oleh px. Kalau x berada pada alamat memori (alamat awal) 1000, maka px akan berisi 1000.
Mendeklarasikan Variabel Pointer
Suatu variabel pointer dideklarasikan dengan bentuk sebagai berikut :
tipe *nama_variabel
dengan tipe dapat berupa sembarang tipe yang sudah dibahas pada bab-bab sebelumnya, maupun bab-bab berikutnya. Adapun nama_variabel adalah nama dari variabel pointer.
Sebagai contoh :
int *px; //contoh 1
char *pch1, *pch2; //contoh 2
Contoh pertama menyatakan bahwa px adalah variabel pointer yang menunjuk ke suatu data bertipe int, sedangkan contoh kedua masing pch1 dan pch2 adalah variabel pointer yang menunjuk ke data bertipe char.
Bentuk umum deklarasi pointer :
Type Pengenal = ^simpul ;
Simpul = tipe data ;
dengan pengenal : nama pengenal yang menyatakan tipe data pointer
simpul : nama simpul
tipe data : tipe data dari simpul
Tanda ^ di depan simpul harus ditulis apa adanya karena itu menunjukkan bahwa pengenal bertipe pointer. Tipe data dari simpul dapat berupa tipe data sebarang, misalnya char, integer, atau real.
Contoh :
Type Str30 = string[30] ;
Point = ^Data ;
Data = record
Nama_Peg : Str30 ;
Alamat : Str30 ;
Pekerjaan : Str30 ;
End ;
Var
P1, P2 : Point ;
A, B, C : Str30 ;
Mengatur Pointer agar Menunjuk ke Variabel Lain
Agar suatu pointer menunjuk ke variabel lain, mula-mula pointer harus diisi dengan alamat dari variabel yang akan ditunjuk. Untuk menyatakan alamat dari suatu variabel, operator & (operator alamat, bersifat unary) bisa dipergunakan, dengan menempatkannya di depan nama variabel. Sebagai contoh, bila x dideklarasikan sebagai variabel bertipe int, maka: &x . Berarti “alamat dari variabel x”. Adapun contoh pemberian alamat x ke suatu variabel pointer px (yang dideklarasikan sebagai pointer yang menunjuk ke data bertipe int) yaitu : px = &x;
Pernyataan di atas berarti bahwa px diberi nilai berupa alamat dari variabel x. Setelah pernyataan tersebut dieksekusi barulah dapat dikatakan bahwa px menunjuk ke variabel x.
Mengakses Isi Suatu Variabel Melalui Pointer
Jika suatu variabel sudah ditunjuk oleh pointer, variabel yang ditunjuk oleh pointer tersebut dapat diakses melalui variabel itu sendiri (pengaksesan langsung) ataupun melalui pointer (pengaksesan tak langsung). Pengaksesan tak langsung dilakukan dengan menggunakan operator indirection (tak langsung) berupa simbol * (bersifat unary).
Contoh penerapan operator * yaitu : *px
Yang menyatakan “isi atau nilai variabel/data yang ditunjuk oleh pointer px” . Sebagai contoh jika y bertipe int, maka sesudah dua pernyataan berikut:
px = &x;
y = *px;
y akan berisi nilai yang sama dengan nilai x. Kedua pernyataan di atas sebenarnya dapat digantikan dengan sebuah pernyataan berupa :
y = x;
Seandainya pada program di atas tidak terdapat pernyataan:
px = &x;
namun terdapat pernyataan
y = *px;
maka y tidaklah berisi nilai x, sebab px belum diatur agar menunjuk ke variabel x.
Hal seperti ini harap diperhatikan. Kalau program melibatkan pointer, dan pointer belum diinisialisasi, ada kemungkinan akan terjadi masalah yang dinamakan “bug” yang bisa mengakibatkan komputer tidak dapat dikendalikan (hang). Selain itu tipe variabel pointer dan tipe data yang ditunjuk harus sejenis. Bila tidak sejenis maka akan terjadi hasil yang tidak diinginkan.
Tipe Data Pointer
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam pengingat computer di mana data yang diwakili oleh tipe data tersebut disimpan.
Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah (Var) untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut.
Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable).
Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah.
Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasika sbb : Var matriks: array[1..100,1..100] of integer; maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data.
Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan.
Jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki,maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
Dengan kata lain, pada saat program dikompilasi, lokasi untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis.
Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan Pointer yang artinya menunjuk ke sesuatu. Dalam peubah dinamis, nilai dari data yang ditunjuk oleh suatu pointer biasanya disebut Simpul / node.
Pencarian Berdasarkan Nilai
Pencarian ini biasanya dilakukan untuk mengenali elemen senarai berdasarkan informasi yang dikandung di dalam elemen yang dicari. Keluaran proses pencarian bergantung pada kebutuhan, apakah hanya sekedar mengetahui sebuah elemen terdapat di dalam senarai, atau melakukan proses terhadap elemen yang ditemukan.
Bila tujuan kedua yang diinginkan, maka keluaran dari proses pencarian adalah alamat elemen yang dicari. Alamat ini nantinya diperlukan untuk pemrosesan elemen selanjutnya.
Contoh :
Pemanggilan prosedur ListFind.
ListFind ( S, X, ketemu, P )
if ketemu then
Proses (P) { proses terhadap elemen P }
…
else
write ( X, ‘tidak ditemukan !’ )
endif
Pencarian Berdasarkan Alamat
Misalkan P adalah sebuah alamat elemen. Ingin diketahui apakah elemen yang alamatnya P terdapat di dalam senarai S. Pencarian ini mirip dengan pencarian berdasarkan nilai.
Contoh Kasus :
Mencari alamat predesesor.
Diberikan senarai S tidak kosong dan P adalah alamat sebuah elemen. Diminta menentukan alamat predesesor (Pred) dari elemen P. Jika P alamat elemen pertama, maka alamat predesesor dari P adalah Nil.
Mengakses Data Dalam Tipe Data Pointer
Pada saat program dikompilasi maka P1 dan P2 akan menempati lokasi tertentu dalam memory. Kedua peubah ini masing-masing belum menunjuk ke suatu simpul atau nilainya dinyatakan dengan NIL. Oleh karena itu sebelum diakses varabel yang bertipe pointer harus dipersiapkan terlebih dahulu, yaitu dengan menggunakan perintah New.
Deklarasi : New (peubah bertipe pointer);
Contoh :
New(P1); New(P2);
Maka sekarang kita mempunyai dua buah simpul yang ditunjuk oleh P1 dan P2. Setelah itu kita dapat melakukan pengaksesan data, yaitu dengan menuliskan :
P1^.Nama_Peg := ‘Ariswan’;
P1^.Alamat := ‘Semarang’;
P1^.Pekerjaan := ‘Pengajar’;
Jika statemen New(P1)diulang beberapa kali maka hanya simpul yang terakhir yang bisa dimasup. Hal ini terjadi karena setiap kali kita memberikan statemen New(P1) maka nilai P1 yang lama akan terhapus. Dengan terhapusnya nilai P1 maka secara otomatis simpul yang ditunjuk oleh P1 tidak ditunjuk lagi dan tidak ditunjuk pula oleh pointer yang lain sehingga karena alamatnya tidak dapat ditentukan maka simpul tersebut tidak dapat dimasup lagi.
Dari sini dapat dilihat bahwa sifat kedinamisan pointer agak tersamar, disebabkan apabila kita menghendaki sejumlah simpul aktif dalam pengingat maka kita perlu menyediakan sejumlah pointer yang sesuai untuk masing-masing simpul. Oleh karena itu, apabila kita hendak mempunyai sebuah peubah yang benar-benar dinamis maka peubah itu harus mampu memasup sejumlah lokasi tertentu.
Untuk itu akan diperkenalkan apa yang dinamakan sebagai Senarai Berantai (Linked List).
Operasi Pada Pointer
Secara umum ada 2 operasi yang dapat dilakukan dengan tipe data pointer, yaitu :
1. Mengkopy pointer, sehingga sebuah simpul akan ditunjuk oleh lebih dari sebuah pointer
2. Mengkopy isi dari simpul, sehingga dua atau lebih simpul yang ditunjuk oleh pointer yang berbeda mempunyai isi yang sama
Catatan :
Syarat yang harus dipenuhi oleh kedua operasi tersebut adalah bahwa pointer-pointer yang akan dioperasikan harus mempunyai deklarasi yang sama.
• Jika dalam statemen pemberian tanda ^ tidak diberikan maka operasinya dinamakan sebagai mengkopi pointer, dengan konsekuensi simpul yang ditunjuk oleh suatu pointer akan bisa terlepas dan tidak dapat dimasup lagi.
Contoh : P1 := P2 ;
• Jika tanda ^ diberikan maka operasinya dinamakan sebagai operasi mengkopi isi simpul pointer, dengan konsekuensi bahwa isi dua buah simpul atau lebih akan menjadi sama.
Contoh : P1^ := P2^ ;
Menghapus Pointer
Statement yang digunakan untuk menghapus pointer adalah Dispose, yang mempunyai bentuk umum :
Dispose(peubah) ;
dengan : peubah = sebarang peubah yang bertipe pointer.
Catatan :
Setelah suatu pointer dihapus maka lokasi yang semula ditempati oleh simpul yang ditujuk oleh pointer tersebut akan bebas, sehingga bisa digunakan oleh peubah yang lain.
Senarai Berantai ( Linked List )
Cara lain untuk menyimpan sekumpulan data selain dengan menggunakan record adalah dengan menggunakan bantuan tipe data pointer. Dalam hal ini, masing-masing data dengan sebuah medan yang bertipe pointer perlu digunakan.
Salah satu struktur data dinamis yang paling sederhana adalah Senarai Berantai (Linked List). Yaitu kumpulan komponen (node) yang disusun secara berurutan dengan menggunakan bantuan pointer. Node ini terbagi menjadi dua bagian yaitu bagian medan informasi, yang berisi informasi yang akan disimpan atau diolah dan bagian penyambung (link field), yang berisi alamat simpul selanjutnya.
Kelebihan tipe pointer dibandingkan tipe lainnya adalah pengalokasian memorinya secara dinamis. Untuk peubah biasa yang bertipe integer,real,dan sebagainya,memorinya segara dialokasikan begitu nama tersebut dideklarasikan.
Operasi - Operasi Pada Senarai Berantai :
1. Menambah Simpul di Depan
Pertama kali pointer pada simpul yang ditunjuk oleh pointer Baru dibuat sama dengan Awal. Kemudian Awal dibuat sama dengan Baru. Dengan cara ini maka simpul baru akan selalu diperlakukan sebagai simpul pertama dalam senarai.
Procedure Tambah_Depan(var Awal,Akhir: point; Elemen:Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info :=Elemen;
If Awal= NIL then Akhir:= Baru
Else Baru^.Berikut:= Awal;
Awal := Baru;
End;
2. Menambah/ menyisipkan Simpul di Tengah
Untuk menambah simpul ditengah maka kita perlu sebuah pointer lain misal dinamakan Bantu. Dalam hal ini simpul baru akan diletakkan setelah simpul yang ditunjuk oleh pointer Bantu. Pertama kali ditentukan dimana simpul baru akan ditempatkan. Kemudian pointer pada simpul yang ditunjuk oleh Baru dibuat sama dengan pointer pada simpul yang ditunjuk oleh Bantu. Selanjutnya pointer pada simpul yang ditunjuk oleh simpul Bantu dibuat sama dengan Baru. Urutan kedua proses ini tidak boleh dibalik.
Procedure Tambah_Tengah(Var Awal,Akhir: point; Elemen: Dat);
Var Baru,Bantu : point;
Begin
New(Baru); Baru^.Berikut:= Elemen;
If Awal = NIL then
Begin
Awal:= Baru; Akhir:= Baru;
End
Else
Begin
Bantu:= Awal;
While (Elemen > Bantu^.Berikut^.Info) and (Bantu <> NIL) then
Bantu:= Bantu^.Berikut;
Baru^.Berikut:= Bantu^.Berikut;
Bantu^.Berikut:= Baru;
End;
3. Menambah Simpul di Belakang
Misal dideklarasikan:
Type Point = ^Data ;
Data = record
Info : char ;
Berikut : Simpul
End;
Var Elemen : char ;
Awal, Akhir, Baru : Simpul ;
Untuk menyambung simpul yang ditunjuk oleh Akhir dan Baru maka pointer pada simpul yang ditunjuk oleh Akhir dibuat sama dengan Baru , kemudian diubah pointer Akhir sama dengan Baru.
Procedure Tambah_Belakang(Awal,Akhir,Elemen: Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info := elemen;
If Awal = NIL then
Awal:= Baru
Else Akhir^.Berikut := Baru;
Akhir:= Baru; Akhir^.Berikut:= NIL;
End;
4. Membaca Isi Senarai Berantai secara Maju
Pertama kali kita atur supaya pointer Bantu menunjuk ke simpul yang ditunjuk oleh pointer Awal. Setelah isi simpul itu dibaca, maka pointer Bantu kita gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang sampai pointer Bantu sama dengan pointer Akhir.
Procedure Baca_Maju(Awal,Akhir : point);
Var Bantu : point;
Begin
Bantu:= Awal;
Repeat
Write(Bantu^.info:2);
Bantu:= Bantu^.Berikut;
Until Bantu = NIL;
Writeln;
End;
5. Membaca Isi Senarai Berantai secara Mundur
Ada 2 cara membaca mundur isi dari Senarai Berantai, yaitu dengan cara biasa seperti diatas atau dengan memanfaatkan proses rekursi. Cara pertama yaitu kita atur pointer Bantu sama dengan pointer Awal. Berikutnya, pointer awal kita arahkan ke simpul Akhir dan kita pakai pointer lain misalkan Bantu1 untuk bergerak dari simpul pertama sampai simpul sebelum simpul terakhir.
Langkah selanjutnya adalah mengarahkan medan pointer dari simpul terakhir ke simpul Bantu1. Langkah ini diulang sampai pointer Akhir Berimpit dengan pointer Bantu. Cara kedua dengan rekursi. Caranya hampir sama dengan cara membaca senarai berantai secara maju hanya saja pencetakan isi simpul ditunda sampai pointer Bantu sama dengan pointer akhir.
Procedure Baca_Terbalik(var Awal,Akhir: point);
Var Bantu,Bantu1 : point;
Begin
Bantu:= Awal;
Awal:= Akhr;
Repeat
Bantu1:=Bantu;
While Bantu1^.Berikut <> Akhir do
Bantu1:= Bantu1^.Berikut;
Akhir^.Berikut:= Bantu1;
Akhir:= Bantu1;
Until Akhir = Bantu;
Akhir^.Berikut:= NIL;
End;
Dengan cara rekursi :
Procedure Terbalik(Bantu: point);
Begin
If Bantu <> NIL then
Begin
TERBALIK(Bantu^.Berikut);
Write(Bantu^.Info:2);
End;
End;
6. Mencari Data dalam Senarai Berantai
Misalkan data yang dicari disimpan dalam peubah Elemen. Pertama kali, pointer Bantu dibuat sama dengan pointer Awal. Kemudan isi simpul yang ditunjuk oleh pointer Bantu dibandingkan dengan Elemen. Jika belum sama, maka pointer Bantu dipindah ke simpul disebelah kanannya dan proses perbandingan diulang lagi sampai bisa ditentukan apakah Elemen ada dalam senarai berantai yang dimaksud atau tidak.
Function Cari_Data(Awal: point; Elemen : Dat): Boolean;
Var ketemu: Boolean;
Begin
Ketemu: false;
Repeat
If Awal^.info = Elemen then
Ketemu:= true
Else
Awal:= Awal^.Berikut;
Until (ketemu) or (Awal = NIL);
Cari_Data:= ketemu;
end;
7. Menghapus Simpul Pertama
Simpul yang dapat dihapus oleh operasi penghapusan simpul adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer, kecuali untuk simpul pertama. Untuk menghapus simpul pertama, maka pointer Bantu kita buat sama dengan pointer Awal. Kemudian pointer Awal kita pindah dari simpul yang ditunjuk oleh pointer Bantu. Selanjutnya, simpul yang ditunjuk oleh pointer Bantu kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Hapus: point;
Begin
Awal:= Awal^.Berikut;
Dispose(Hapus);
End;
8. Menghapus Simpul di Tengah atau Terakhir
Pertama kita letakkan pointer Bantu pada simpul di sebelah kiri simpul yang akan dihapus. Simpul yang akan dihapus kita tunjuk dengan pointer lain, misalnya Hapus. Kemudian pointer pada simpul yang ditunjuk oleh Bantu kita tunjukkan pada simpul yang ditunjuk oleh pointer pada simpul yang akan dihapus. Selanjutnya simpul yang ditunjuk oleh pointer Hapus kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Bantu, Hapus : point;
Begin {senarai masih kosong}
If awal= NIL then
Writeln(‘Searai berantai masih kosong !’)
Else
Begin {menghapus simpul diawal}
Hapus:= Awal;
Awal:= Hapus^.Berikut;
Dispose(Berikut);
End
Else {menghapus simpul ditengah atau akhir}
Begin
Bantu:= Awal;
While (Elemen <> Bantu^.info) and (Bantu^.Next <> NIL) do
Bantu:= Bantu^.Berikut;
Hapus:= Bantu^.Berikut;
If Hapus <> NIL then
Begin
If Hapus = Akhir then
Begin
Akhir:= Bantu;
Akhir^.Berikut:= NIL;
End
Else Bantu^.Berikut:= Hapus^.Berikut;
Dispose(Hapus);
End
Else writeln(‘Tidak ketemu yang dihapus !!’);
End;
End;
End;
Pointer adalah tipe dasar yang ranah nilainya adalah alamat di memori komputer. Nama tipe : pointer
Ranah nilai : alamat sel memori komputer
Tetapan : Satu – satunya tetapan adalah Nil, yang menunjukkan alamat tidak
terdefinisi.
Operator : Operator perbandingan yang menghasilkan nilai boolean,yaitu operator = ( sama dengan ) dan ≠ ( tidak sama dengan )
Memori terdiri atas sekumpulan sel, dan setiap sel mempunyai alamat. Alamat yang dimaksud adalah alamat fisik ( berupa angka – angka dalam sistem heksadesimal ). Dalam pemograman ,pemogram tidak berhubungan langsung dengan alamat fisik karena sulit diingat. Karena itu, pemogram mendefinisikan nama untuk lokasi memori yang menyimpan suatu nilai. Sebagi contoh , X adalah nama yang didefinisikan bertipe integer.
X adalah peubah yang menyimpan harga bertipe integer. Pemogram tidak peduli di sel memory mana harga tersebut, namun agar sel memori dikenali, pemogram memberi nama sel memori terseut dengan X.
Variabel pointer sering dikatakan sebagai variabel yang menunjuk ke obyek lain. Pada kenyataan yang sebenarnya, variabel pointer berisi alamat dari suatu obyek lain (yaitu obyek yang dikatakan ditunjuk oleh pointer). Sebagai contoh, px adalah variabel pointer dan x adalah variabel yang ditunjuk oleh px. Kalau x berada pada alamat memori (alamat awal) 1000, maka px akan berisi 1000.
Mendeklarasikan Variabel Pointer
Suatu variabel pointer dideklarasikan dengan bentuk sebagai berikut :
tipe *nama_variabel
dengan tipe dapat berupa sembarang tipe yang sudah dibahas pada bab-bab sebelumnya, maupun bab-bab berikutnya. Adapun nama_variabel adalah nama dari variabel pointer.
Sebagai contoh :
int *px; //contoh 1
char *pch1, *pch2; //contoh 2
Contoh pertama menyatakan bahwa px adalah variabel pointer yang menunjuk ke suatu data bertipe int, sedangkan contoh kedua masing pch1 dan pch2 adalah variabel pointer yang menunjuk ke data bertipe char.
Bentuk umum deklarasi pointer :
Type Pengenal = ^simpul ;
Simpul = tipe data ;
dengan pengenal : nama pengenal yang menyatakan tipe data pointer
simpul : nama simpul
tipe data : tipe data dari simpul
Tanda ^ di depan simpul harus ditulis apa adanya karena itu menunjukkan bahwa pengenal bertipe pointer. Tipe data dari simpul dapat berupa tipe data sebarang, misalnya char, integer, atau real.
Contoh :
Type Str30 = string[30] ;
Point = ^Data ;
Data = record
Nama_Peg : Str30 ;
Alamat : Str30 ;
Pekerjaan : Str30 ;
End ;
Var
P1, P2 : Point ;
A, B, C : Str30 ;
Mengatur Pointer agar Menunjuk ke Variabel Lain
Agar suatu pointer menunjuk ke variabel lain, mula-mula pointer harus diisi dengan alamat dari variabel yang akan ditunjuk. Untuk menyatakan alamat dari suatu variabel, operator & (operator alamat, bersifat unary) bisa dipergunakan, dengan menempatkannya di depan nama variabel. Sebagai contoh, bila x dideklarasikan sebagai variabel bertipe int, maka: &x . Berarti “alamat dari variabel x”. Adapun contoh pemberian alamat x ke suatu variabel pointer px (yang dideklarasikan sebagai pointer yang menunjuk ke data bertipe int) yaitu : px = &x;
Pernyataan di atas berarti bahwa px diberi nilai berupa alamat dari variabel x. Setelah pernyataan tersebut dieksekusi barulah dapat dikatakan bahwa px menunjuk ke variabel x.
Mengakses Isi Suatu Variabel Melalui Pointer
Jika suatu variabel sudah ditunjuk oleh pointer, variabel yang ditunjuk oleh pointer tersebut dapat diakses melalui variabel itu sendiri (pengaksesan langsung) ataupun melalui pointer (pengaksesan tak langsung). Pengaksesan tak langsung dilakukan dengan menggunakan operator indirection (tak langsung) berupa simbol * (bersifat unary).
Contoh penerapan operator * yaitu : *px
Yang menyatakan “isi atau nilai variabel/data yang ditunjuk oleh pointer px” . Sebagai contoh jika y bertipe int, maka sesudah dua pernyataan berikut:
px = &x;
y = *px;
y akan berisi nilai yang sama dengan nilai x. Kedua pernyataan di atas sebenarnya dapat digantikan dengan sebuah pernyataan berupa :
y = x;
Seandainya pada program di atas tidak terdapat pernyataan:
px = &x;
namun terdapat pernyataan
y = *px;
maka y tidaklah berisi nilai x, sebab px belum diatur agar menunjuk ke variabel x.
Hal seperti ini harap diperhatikan. Kalau program melibatkan pointer, dan pointer belum diinisialisasi, ada kemungkinan akan terjadi masalah yang dinamakan “bug” yang bisa mengakibatkan komputer tidak dapat dikendalikan (hang). Selain itu tipe variabel pointer dan tipe data yang ditunjuk harus sejenis. Bila tidak sejenis maka akan terjadi hasil yang tidak diinginkan.
Tipe Data Pointer
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam pengingat computer di mana data yang diwakili oleh tipe data tersebut disimpan.
Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah (Var) untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut.
Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable).
Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah.
Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasika sbb : Var matriks: array[1..100,1..100] of integer; maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data.
Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan.
Jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki,maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
Dengan kata lain, pada saat program dikompilasi, lokasi untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis.
Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan Pointer yang artinya menunjuk ke sesuatu. Dalam peubah dinamis, nilai dari data yang ditunjuk oleh suatu pointer biasanya disebut Simpul / node.
Pencarian Berdasarkan Nilai
Pencarian ini biasanya dilakukan untuk mengenali elemen senarai berdasarkan informasi yang dikandung di dalam elemen yang dicari. Keluaran proses pencarian bergantung pada kebutuhan, apakah hanya sekedar mengetahui sebuah elemen terdapat di dalam senarai, atau melakukan proses terhadap elemen yang ditemukan.
Bila tujuan kedua yang diinginkan, maka keluaran dari proses pencarian adalah alamat elemen yang dicari. Alamat ini nantinya diperlukan untuk pemrosesan elemen selanjutnya.
Contoh :
Pemanggilan prosedur ListFind.
ListFind ( S, X, ketemu, P )
if ketemu then
Proses (P) { proses terhadap elemen P }
…
else
write ( X, ‘tidak ditemukan !’ )
endif
Pencarian Berdasarkan Alamat
Misalkan P adalah sebuah alamat elemen. Ingin diketahui apakah elemen yang alamatnya P terdapat di dalam senarai S. Pencarian ini mirip dengan pencarian berdasarkan nilai.
Contoh Kasus :
Mencari alamat predesesor.
Diberikan senarai S tidak kosong dan P adalah alamat sebuah elemen. Diminta menentukan alamat predesesor (Pred) dari elemen P. Jika P alamat elemen pertama, maka alamat predesesor dari P adalah Nil.
Mengakses Data Dalam Tipe Data Pointer
Pada saat program dikompilasi maka P1 dan P2 akan menempati lokasi tertentu dalam memory. Kedua peubah ini masing-masing belum menunjuk ke suatu simpul atau nilainya dinyatakan dengan NIL. Oleh karena itu sebelum diakses varabel yang bertipe pointer harus dipersiapkan terlebih dahulu, yaitu dengan menggunakan perintah New.
Deklarasi : New (peubah bertipe pointer);
Contoh :
New(P1); New(P2);
Maka sekarang kita mempunyai dua buah simpul yang ditunjuk oleh P1 dan P2. Setelah itu kita dapat melakukan pengaksesan data, yaitu dengan menuliskan :
P1^.Nama_Peg := ‘Ariswan’;
P1^.Alamat := ‘Semarang’;
P1^.Pekerjaan := ‘Pengajar’;
Jika statemen New(P1)diulang beberapa kali maka hanya simpul yang terakhir yang bisa dimasup. Hal ini terjadi karena setiap kali kita memberikan statemen New(P1) maka nilai P1 yang lama akan terhapus. Dengan terhapusnya nilai P1 maka secara otomatis simpul yang ditunjuk oleh P1 tidak ditunjuk lagi dan tidak ditunjuk pula oleh pointer yang lain sehingga karena alamatnya tidak dapat ditentukan maka simpul tersebut tidak dapat dimasup lagi.
Dari sini dapat dilihat bahwa sifat kedinamisan pointer agak tersamar, disebabkan apabila kita menghendaki sejumlah simpul aktif dalam pengingat maka kita perlu menyediakan sejumlah pointer yang sesuai untuk masing-masing simpul. Oleh karena itu, apabila kita hendak mempunyai sebuah peubah yang benar-benar dinamis maka peubah itu harus mampu memasup sejumlah lokasi tertentu.
Untuk itu akan diperkenalkan apa yang dinamakan sebagai Senarai Berantai (Linked List).
Operasi Pada Pointer
Secara umum ada 2 operasi yang dapat dilakukan dengan tipe data pointer, yaitu :
1. Mengkopy pointer, sehingga sebuah simpul akan ditunjuk oleh lebih dari sebuah pointer
2. Mengkopy isi dari simpul, sehingga dua atau lebih simpul yang ditunjuk oleh pointer yang berbeda mempunyai isi yang sama
Catatan :
Syarat yang harus dipenuhi oleh kedua operasi tersebut adalah bahwa pointer-pointer yang akan dioperasikan harus mempunyai deklarasi yang sama.
• Jika dalam statemen pemberian tanda ^ tidak diberikan maka operasinya dinamakan sebagai mengkopi pointer, dengan konsekuensi simpul yang ditunjuk oleh suatu pointer akan bisa terlepas dan tidak dapat dimasup lagi.
Contoh : P1 := P2 ;
• Jika tanda ^ diberikan maka operasinya dinamakan sebagai operasi mengkopi isi simpul pointer, dengan konsekuensi bahwa isi dua buah simpul atau lebih akan menjadi sama.
Contoh : P1^ := P2^ ;
Menghapus Pointer
Statement yang digunakan untuk menghapus pointer adalah Dispose, yang mempunyai bentuk umum :
Dispose(peubah) ;
dengan : peubah = sebarang peubah yang bertipe pointer.
Catatan :
Setelah suatu pointer dihapus maka lokasi yang semula ditempati oleh simpul yang ditujuk oleh pointer tersebut akan bebas, sehingga bisa digunakan oleh peubah yang lain.
Senarai Berantai ( Linked List )
Cara lain untuk menyimpan sekumpulan data selain dengan menggunakan record adalah dengan menggunakan bantuan tipe data pointer. Dalam hal ini, masing-masing data dengan sebuah medan yang bertipe pointer perlu digunakan.
Salah satu struktur data dinamis yang paling sederhana adalah Senarai Berantai (Linked List). Yaitu kumpulan komponen (node) yang disusun secara berurutan dengan menggunakan bantuan pointer. Node ini terbagi menjadi dua bagian yaitu bagian medan informasi, yang berisi informasi yang akan disimpan atau diolah dan bagian penyambung (link field), yang berisi alamat simpul selanjutnya.
Kelebihan tipe pointer dibandingkan tipe lainnya adalah pengalokasian memorinya secara dinamis. Untuk peubah biasa yang bertipe integer,real,dan sebagainya,memorinya segara dialokasikan begitu nama tersebut dideklarasikan.
Operasi - Operasi Pada Senarai Berantai :
1. Menambah Simpul di Depan
Pertama kali pointer pada simpul yang ditunjuk oleh pointer Baru dibuat sama dengan Awal. Kemudian Awal dibuat sama dengan Baru. Dengan cara ini maka simpul baru akan selalu diperlakukan sebagai simpul pertama dalam senarai.
Procedure Tambah_Depan(var Awal,Akhir: point; Elemen:Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info :=Elemen;
If Awal= NIL then Akhir:= Baru
Else Baru^.Berikut:= Awal;
Awal := Baru;
End;
2. Menambah/ menyisipkan Simpul di Tengah
Untuk menambah simpul ditengah maka kita perlu sebuah pointer lain misal dinamakan Bantu. Dalam hal ini simpul baru akan diletakkan setelah simpul yang ditunjuk oleh pointer Bantu. Pertama kali ditentukan dimana simpul baru akan ditempatkan. Kemudian pointer pada simpul yang ditunjuk oleh Baru dibuat sama dengan pointer pada simpul yang ditunjuk oleh Bantu. Selanjutnya pointer pada simpul yang ditunjuk oleh simpul Bantu dibuat sama dengan Baru. Urutan kedua proses ini tidak boleh dibalik.
Procedure Tambah_Tengah(Var Awal,Akhir: point; Elemen: Dat);
Var Baru,Bantu : point;
Begin
New(Baru); Baru^.Berikut:= Elemen;
If Awal = NIL then
Begin
Awal:= Baru; Akhir:= Baru;
End
Else
Begin
Bantu:= Awal;
While (Elemen > Bantu^.Berikut^.Info) and (Bantu <> NIL) then
Bantu:= Bantu^.Berikut;
Baru^.Berikut:= Bantu^.Berikut;
Bantu^.Berikut:= Baru;
End;
3. Menambah Simpul di Belakang
Misal dideklarasikan:
Type Point = ^Data ;
Data = record
Info : char ;
Berikut : Simpul
End;
Var Elemen : char ;
Awal, Akhir, Baru : Simpul ;
Untuk menyambung simpul yang ditunjuk oleh Akhir dan Baru maka pointer pada simpul yang ditunjuk oleh Akhir dibuat sama dengan Baru , kemudian diubah pointer Akhir sama dengan Baru.
Procedure Tambah_Belakang(Awal,Akhir,Elemen: Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info := elemen;
If Awal = NIL then
Awal:= Baru
Else Akhir^.Berikut := Baru;
Akhir:= Baru; Akhir^.Berikut:= NIL;
End;
4. Membaca Isi Senarai Berantai secara Maju
Pertama kali kita atur supaya pointer Bantu menunjuk ke simpul yang ditunjuk oleh pointer Awal. Setelah isi simpul itu dibaca, maka pointer Bantu kita gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang sampai pointer Bantu sama dengan pointer Akhir.
Procedure Baca_Maju(Awal,Akhir : point);
Var Bantu : point;
Begin
Bantu:= Awal;
Repeat
Write(Bantu^.info:2);
Bantu:= Bantu^.Berikut;
Until Bantu = NIL;
Writeln;
End;
5. Membaca Isi Senarai Berantai secara Mundur
Ada 2 cara membaca mundur isi dari Senarai Berantai, yaitu dengan cara biasa seperti diatas atau dengan memanfaatkan proses rekursi. Cara pertama yaitu kita atur pointer Bantu sama dengan pointer Awal. Berikutnya, pointer awal kita arahkan ke simpul Akhir dan kita pakai pointer lain misalkan Bantu1 untuk bergerak dari simpul pertama sampai simpul sebelum simpul terakhir.
Langkah selanjutnya adalah mengarahkan medan pointer dari simpul terakhir ke simpul Bantu1. Langkah ini diulang sampai pointer Akhir Berimpit dengan pointer Bantu. Cara kedua dengan rekursi. Caranya hampir sama dengan cara membaca senarai berantai secara maju hanya saja pencetakan isi simpul ditunda sampai pointer Bantu sama dengan pointer akhir.
Procedure Baca_Terbalik(var Awal,Akhir: point);
Var Bantu,Bantu1 : point;
Begin
Bantu:= Awal;
Awal:= Akhr;
Repeat
Bantu1:=Bantu;
While Bantu1^.Berikut <> Akhir do
Bantu1:= Bantu1^.Berikut;
Akhir^.Berikut:= Bantu1;
Akhir:= Bantu1;
Until Akhir = Bantu;
Akhir^.Berikut:= NIL;
End;
Dengan cara rekursi :
Procedure Terbalik(Bantu: point);
Begin
If Bantu <> NIL then
Begin
TERBALIK(Bantu^.Berikut);
Write(Bantu^.Info:2);
End;
End;
6. Mencari Data dalam Senarai Berantai
Misalkan data yang dicari disimpan dalam peubah Elemen. Pertama kali, pointer Bantu dibuat sama dengan pointer Awal. Kemudan isi simpul yang ditunjuk oleh pointer Bantu dibandingkan dengan Elemen. Jika belum sama, maka pointer Bantu dipindah ke simpul disebelah kanannya dan proses perbandingan diulang lagi sampai bisa ditentukan apakah Elemen ada dalam senarai berantai yang dimaksud atau tidak.
Function Cari_Data(Awal: point; Elemen : Dat): Boolean;
Var ketemu: Boolean;
Begin
Ketemu: false;
Repeat
If Awal^.info = Elemen then
Ketemu:= true
Else
Awal:= Awal^.Berikut;
Until (ketemu) or (Awal = NIL);
Cari_Data:= ketemu;
end;
7. Menghapus Simpul Pertama
Simpul yang dapat dihapus oleh operasi penghapusan simpul adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer, kecuali untuk simpul pertama. Untuk menghapus simpul pertama, maka pointer Bantu kita buat sama dengan pointer Awal. Kemudian pointer Awal kita pindah dari simpul yang ditunjuk oleh pointer Bantu. Selanjutnya, simpul yang ditunjuk oleh pointer Bantu kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Hapus: point;
Begin
Awal:= Awal^.Berikut;
Dispose(Hapus);
End;
8. Menghapus Simpul di Tengah atau Terakhir
Pertama kita letakkan pointer Bantu pada simpul di sebelah kiri simpul yang akan dihapus. Simpul yang akan dihapus kita tunjuk dengan pointer lain, misalnya Hapus. Kemudian pointer pada simpul yang ditunjuk oleh Bantu kita tunjukkan pada simpul yang ditunjuk oleh pointer pada simpul yang akan dihapus. Selanjutnya simpul yang ditunjuk oleh pointer Hapus kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Bantu, Hapus : point;
Begin {senarai masih kosong}
If awal= NIL then
Writeln(‘Searai berantai masih kosong !’)
Else
Begin {menghapus simpul diawal}
Hapus:= Awal;
Awal:= Hapus^.Berikut;
Dispose(Berikut);
End
Else {menghapus simpul ditengah atau akhir}
Begin
Bantu:= Awal;
While (Elemen <> Bantu^.info) and (Bantu^.Next <> NIL) do
Bantu:= Bantu^.Berikut;
Hapus:= Bantu^.Berikut;
If Hapus <> NIL then
Begin
If Hapus = Akhir then
Begin
Akhir:= Bantu;
Akhir^.Berikut:= NIL;
End
Else Bantu^.Berikut:= Hapus^.Berikut;
Dispose(Hapus);
End
Else writeln(‘Tidak ketemu yang dihapus !!’);
End;
End;
End;
Pointer adalah tipe dasar yang ranah nilainya adalah alamat di memori komputer. Nama tipe : pointer
Ranah nilai : alamat sel memori komputer
Tetapan : Satu – satunya tetapan adalah Nil, yang menunjukkan alamat tidak
terdefinisi.
Operator : Operator perbandingan yang menghasilkan nilai boolean,yaitu operator = ( sama dengan ) dan ≠ ( tidak sama dengan )
Memori terdiri atas sekumpulan sel, dan setiap sel mempunyai alamat. Alamat yang dimaksud adalah alamat fisik ( berupa angka – angka dalam sistem heksadesimal ). Dalam pemograman ,pemogram tidak berhubungan langsung dengan alamat fisik karena sulit diingat. Karena itu, pemogram mendefinisikan nama untuk lokasi memori yang menyimpan suatu nilai. Sebagi contoh , X adalah nama yang didefinisikan bertipe integer.
X adalah peubah yang menyimpan harga bertipe integer. Pemogram tidak peduli di sel memory mana harga tersebut, namun agar sel memori dikenali, pemogram memberi nama sel memori terseut dengan X.
Sahrul.wijaya
Pengurutan (array)
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu dan proses yang sering harus dilakukan dalam pengolahan data dan proses mengatur sekumpulan objek menurut aturan atau susunan tertentu (WIR76). Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerik ataupun karakter.Pengurutan objek tersebut dapat dilakukan secara ascending (urut naik) dan descending (urut turun). Bila n buah objek (atau data) dismpan dalam larik L, maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga :
L[1] ≤ L[2] ≤ L[3 ≤ … ≤ L[N]
Sedangkan pengurutan menurun berarti menyusun lemen larik sedemikian sehingga :
L[1] ≥ L[2] ≥ L[3 ≥ … ≥ L[N]
Data yang diurut dapat berupa data bertipe dasar atau bertipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci.
Berikut ini diberikan beberapa contoh data terurut:
(i) 23, 27, 45, 67, 100, 130, 501
(data bertipe integer menaik)
(ii) 50, 27, 31.009, 20.3, 19.0, -5.2, -10.9
(data bertipe riil terurut menurun)
(iii) ‘d’, ‘e’, ‘g’, ‘i’, ‘x’
(data bertipe karakter terurut menaik)
(iv) ‘Amir’, ‘Badu’, ‘Budi’, ‘Dudi’, ‘Eno’, ‘Rudi’, ‘Zamzani’
(data bertipe string terurut menaik)
(v) <13596001, ‘Eko’, ‘A’>, <13596006, ‘Rizka’, ‘B’>,
<13596007, ‘Hamdi’, ‘D’>, <13596010, ‘Rizal, ‘C’>,
<13596012, ‘Ratna’, ‘A’>
(data mahasiswa bertipe terstruktur terurut menaik berdasarkan field NIM)
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
DEKLARASI ARRAY UNTUK SORTING
Deklarasikan:
int data[100];
int n; //untuk jumlah data
Fungsi untuk Tukar 2 Buah Data:
void tukar(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
Metode-metode Pengurutan Data
Adanya kebutuhan terhadap proses pengurutan memunculkan berbagai macam metode pengurutan. Banyak metode pengurutan yang telah ditemukan. Hal ini menunjukkan bahwa persoalan pengurutan adalah persoalan yang kaya dengan solusi algoritmik. Metode pengurutan yang ditemukan didalam literatur-literatur komputer antara lain :
1. Bubble Sort
2. Selection Sort (Maximum Sort dan Minimum Sort)
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort
Pada materi ini tidak akan membahas semua metode pengurutan tersebut, tetapi hanya empat buah metode pengurutan yang sederhana saja, yaitu:
1. Metode Pengurutan Apung (Bubble Sort)
2. Metode Pengurutan Seleksi (Selection Sort)
3. Metode Pengurutan Sisipan (Insertion Sort)
4. Metode Pengurutan Shell (Shell Sort)
Untuk setiap metode pengurutan akan ditulis algoritmanya. Dua metode pertama (bubble dan selection sort) melakukan prinsip pertukaran elemen dalam proses pengurutan sehingga keduanya dinamakan pengurutan dengan pertukaran (exchange sort), sedangkan dua metode terakhir melakukan prinsip geser dan sisip elemen dalam prose pengurutan (shift and insert sort). Semua metode pengurutan selalu melakukan operasi perbandingan elemen larik untuk menemukan posisi urutan yang tepat.
• Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
• Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and
keep sorted method)
• Insertion sort, tree sort
• Pengurutan berdasarkan pembagian dan penguasaan (devide and
conquer method)
• Quick sort, merge sort
• Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort
Metode pengurutan juga dapat diklasifikasikan sebagai metode pengurutan internal dan metode pengurutan eksternal.
1. Metode pengurutan internal, yaitu metode pengurutan untuk data yang disimpan di dala memori komputer. Umumnya struktur internal yang dipakai untuk pengurutaninternal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.
2. Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan di dalam disk storage, disebut juaga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
A. Metode Pengurutan Apung (Bubble Sort)
Metode pengurutan apung (bubble sort) diinspirasi oleh gelembung sabun yang berada di atas permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan.
Metode sorting termudah. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan kekiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Prosedur Bubble Sort
Versi 1
void bubble_sort(){
for(int i=1;i
for(int j=n-1;j>=i;j--){
if(data[j]
tukar(&data[j],&data[j-1]); //ascending
}
}
}
Versi 2
void bubblesort2(){
for(i=1;i<6;i++){
for(int j=0;j<6-i;j++){
if(data[j]>data[j+1])
tukar(&data[j],&data[j+1]); //descending
}
}
}
Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun
(descending) silhkan ubah bagian:
if (data[j]
Menjadi:
if (data[j]> data[j-1]) tukar(&data[j],&data[j-1]);
Komentar Mengenai Pengurutan Apung
Pengurutan apung merupakam metode pengurutan yang tidak mangkus (efficient). Hal ini disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan. Untuk ukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang lama. Karena alasan itu, maka metode pengurutan apung jarang digunakan dalam praktek pemrograman. Namun, kelebihan metode ini adalah pada kesederhanaannya sederhana dan mudah dipahami.
B. Metode Pengurutan Seleksi (Selection Sort)
Metode pengurutan ini disebut pengurutan seleksi karena gagasan dasarnya adalah memilih elemen maksimum/ minimum dari larik, lalu menempatkan elemen maksimum/ minimum pada awal atau akhir larik dan merupakan kombinasi antara sorting dan searching.
Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
Ada dua varian algoritma pengurutan seleksi ditinjau dari pemilihan elemen maksimum/ minimum, yaitu :
1.Algoritma pengurutan seleksi-maksimum, yaitu memilih elemen maksimum sebagai basis pengurutan. Misalkan larik L dengan N=6 sebagai berikut:
Maka langkah-langkah pengurutannya adalah:
Contoh algoritma :
Procedure SelectionSort(input/output L : Larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan maksimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]}
Deklarasi
I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imaks : integer {indeks yang berisi nilai maksimum sementara}
Procedure tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← N downto 2 do {jumlah pengulangan sebanyak N-1}
{cari elemen maksimum pada elemen L[1..I]}
Imaks ← I {elemen pertama diasumsikan sebagai elemen maksimum sementara}
For J ← 2 to I do
If L[J] > L[Imaks] then
Imaks ← J
Endif
Endfor {pertukarkan L[Imaks] dengan L[I]}
Tukar(L[Imaks], L[I])
Endfor
2.Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis pengurutan. Misalkan larik L dengan N=6 sebagai berikut:
maka langkah-langkah pengurutannya adalah:
Contoh algoritma :
Procedure SelectionSort(input/output L : larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan pilih minimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]} Deklarasi I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imin : integer {indeks yang berisi nilai maksimum sementara}
Procedure Tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← 1 to N-1 do {cari indeks dari elemen minimum di dalam larik L[I..N]}
Imin ← I
For J ← I+1 to N do
If L[J] > L[Imin] then
Imin ← J
Endif
Endfor {pertukarkan L[Imin] dengan L[I]}
Tukar(L[Imin], L[I])
Endfor
Prosedur Selection Sort
void selection_sort(){
for(int i=0;i
pos = i;
for(int j=i+1;j
if(data[j] < data[pos]) pos = j; //ascending
}
if(pos != i) tukar(pos,i);
}
}
Komentar Mengenai Metode Pengurutan Seleksi
Dibanding dengan metode pengurutan apung, metode pengurutan seleksi memiliki kinerjayang lebih baik. Alasannya, operasi pertukaran elemen hanya dilakukan sekali saja pada setiap pass, dengan demikian lamanya pengurutannya berkurang dibandingkan dengan metode pengurutan gelembung.
C. Metode Pengurutan Sisipan (Insetion Sort)
Pengurutan sisipan adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencairan posisi yang tepat dilakukan dengan cara menyisir elemen larik. Selama penyisiran dilakukan pergeseran elemen larik. Metode pengurutan sisip cocok untuk persoalan menyisipkan elemen baru ke dalam sekumpulan elemen yang sudah yang terurut.
Pada metode ini elemen terbagi menjadi 2 bagian yaitu kelompok sumber yang merupakan susunan asli dari kelompok tersebut (belum terurut) yaitu dari A1…..AN dan kelompok yang kedua adalah kelompok tujuan yaitu susunan elemen yang telah terurut dengan urutan dari A1….Ai -1. Langkah penyisipan dimulai dari i = 2 dengan pertambahan 1. Elemen ke i diambil dari kelompok sumber dan akan dipindahkan ke kelompok tujuan dengan cara menyisipkannya pada tempatnya yang sesuai.
Algoritma metode sisip langsung :
- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 sampai 5 untuk i = 2 sampai dengan N
- langkah 2 : Tentukan : T = A[i] (elemen yang akan disisipkan), A[0] = T (data sentinel) dan j = i -1.
- langkah 3 : (lakukan pergeseran). Kerjakan langkah 4 selama T < A[j]
- langkah 4 : Tentukan : A[j + 1] = A[j] dan j = j -1.
- langkah 5 : Tentukan : A[j + 1] = T
- langkah 6 : Selesai
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Prosedur Insertion Sort
void insertion_sort(){
int temp;
for(int i=1;i
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
Komentar mengenai metode pengurutan sisipan
Kelemahan metode pengurutan sisipan terletak pada banyaknya operasi pergeseran yang dilakukan dalam mencari posisi yang tepat untuk elemen larik. Pada setiap pass i, opeasi pergeseran yang diperlukan maksimum i -1 kali. Untuk larik yang berukuran besar, jumlah operasi pergeseran meningkat secara kuadratik, sehingga pengurutan sisip kurang bagus untuk volume data yang besar.
D. Metode Pengurutan Shell (Shell Sort)
Metode ini merupakan perbaikan terhadap metode pengurutan sisipan. Kelemahan metode pengurutan sisipan sudah disebutkan pada bagian sebelumnya. Jika data pada posisi ke-1000 ternyata posisi yang tepat adalah sebagai elemen kedua, maka dibutuhkan kira-kira 998 kali pergeseran elemen.
Untuk mengurangi pergeseran terlalu jauh, kita mengurutkan larik setiap k elemen dengan metode pengurutan sisip, misalkan kita urutkan setiap 5 elemen (k kita namakan juga step atau increment). Selanjutnya, digunakan nilai step yang lebih kecil, misalnya k = 3, lalu diurut setiap 3 elemen. Begitu seterusnya sampai nilai k = 1. Karena nilai step selalu berkurang maka metode pengurutan Shell kadang – kadang dinamakan juga metode pengurutan kenaikan berkurang (diminishing increment sort)
Komentar mengenai metode pengurutan shell
Metode pengurutan shell merupakan perbaikan terhadap metode pengurutan sisipan. Namun tidak seorangpun yang pernah dapat menganalisis metode pengurutan shell secara tepat, karena pemilihan ukuran step (seperti 5, 3, 1, atau pendefinisian ukuran tep dengan pernyataan step = step div 3+ 1) didasarkan pada pertimbangan sugesti.
Tidak ada aturan yang diketahui untuk menemukan ukuran step yang optimum. Jika step yang dipilih berdekatan, semakin banyak jumlah pass yan g dihasilkan, tapi setiap pass mungkin lebih cepat. Jika ukuran step menurun dengan cepat, jumlah pass akan berkurang tetapi setiap pass menjadi lebih panjang (lama).
IV. Algoritma
Type
Larik= array [1..100] of integer ;
Deklarasi
n : integer
x : integer
i : integer
L : Larik
ketemu:boolean {pertanda untuk menentukan apakah x ditemukan}
Procedure bagi_dua(input L: Larikint, input n: integer, input x : integer,output idx : integer, var ketemu:boolean)
Deklarasi
i, j : integer { indeks kiri dan indeks kanan larik}
k : integer { indeks elemen tengah }
Idx:integer
i← 1 {ujung kiri larik}
j ← n (ujung kanan larik}
Ketemu ← false {asumsikan x belum ditemukan}
While (not Ketemu) and (I <= J) do
k ← (i + j) div 2 (bagi dua larik L pada posisi k}
If L[k] = x then
{lakukan pencarian pada larik bagian kanan, set indeks ujung kiri larik yang baru}
Ketemu ← true
Idx ← k
Else
If (L[k] > x) then
J ← k - 1
Else
{lakukan pencarian pada larik bagian kiri, set indeks ujung kanan larik yang baru}
I ← k + 1
Endif
Endif
Endwhile
{ketemu = true or i > j}
If (ketemu) then { x ditemukan}
Idx← k
Else { x tidak ditemukan dalam larik }
Idx← -1
End if
V. Program
Program Searching ;
Uses wincrt;
Type
Larik= array [1..100] of integer ;
Var
N : integer;
X : integer;
i : integer;
L : Larik;
ketemu:boolean;
Procedure bagi_dua(N : integer;var ketemu:boolean);
Var
I, J : integer;
K : integer;
Idx:integer;
Begin
I := 1;
J := N;
Ketemu := false;
While (not Ketemu) and (I <= J) do
Begin
K := (I + J) div 2 ;
If L[K] = X then
Begin
Ketemu := true;
Idx := K;
End
Else
Begin
If (L[K] > X) then
J := K - 1
Else
I := K + 1 ;
End;
End;
End;
Begin
write ('Masukan Jumlah Data = '); readln (N);
for i:=1 to N do
begin
write ('Masukan Data = '); readln (L[i]);
end;
write('Masukan Data yang Dicari = '); readln (X);
bagi_dua(N,ketemu);
if ketemu then
write ('Data yang Anda Cari Ada')
else
write('Maaf, Data yang Anda Cari Tidak Ada. Coba Ulangi Lagi') ;
end.
L[1] ≤ L[2] ≤ L[3 ≤ … ≤ L[N]
Sedangkan pengurutan menurun berarti menyusun lemen larik sedemikian sehingga :
L[1] ≥ L[2] ≥ L[3 ≥ … ≥ L[N]
Data yang diurut dapat berupa data bertipe dasar atau bertipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci.
Berikut ini diberikan beberapa contoh data terurut:
(i) 23, 27, 45, 67, 100, 130, 501
(data bertipe integer menaik)
(ii) 50, 27, 31.009, 20.3, 19.0, -5.2, -10.9
(data bertipe riil terurut menurun)
(iii) ‘d’, ‘e’, ‘g’, ‘i’, ‘x’
(data bertipe karakter terurut menaik)
(iv) ‘Amir’, ‘Badu’, ‘Budi’, ‘Dudi’, ‘Eno’, ‘Rudi’, ‘Zamzani’
(data bertipe string terurut menaik)
(v) <13596001, ‘Eko’, ‘A’>, <13596006, ‘Rizka’, ‘B’>,
<13596007, ‘Hamdi’, ‘D’>, <13596010, ‘Rizal, ‘C’>,
<13596012, ‘Ratna’, ‘A’>
(data mahasiswa bertipe terstruktur terurut menaik berdasarkan field NIM)
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
DEKLARASI ARRAY UNTUK SORTING
Deklarasikan:
int data[100];
int n; //untuk jumlah data
Fungsi untuk Tukar 2 Buah Data:
void tukar(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
Metode-metode Pengurutan Data
Adanya kebutuhan terhadap proses pengurutan memunculkan berbagai macam metode pengurutan. Banyak metode pengurutan yang telah ditemukan. Hal ini menunjukkan bahwa persoalan pengurutan adalah persoalan yang kaya dengan solusi algoritmik. Metode pengurutan yang ditemukan didalam literatur-literatur komputer antara lain :
1. Bubble Sort
2. Selection Sort (Maximum Sort dan Minimum Sort)
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort
Pada materi ini tidak akan membahas semua metode pengurutan tersebut, tetapi hanya empat buah metode pengurutan yang sederhana saja, yaitu:
1. Metode Pengurutan Apung (Bubble Sort)
2. Metode Pengurutan Seleksi (Selection Sort)
3. Metode Pengurutan Sisipan (Insertion Sort)
4. Metode Pengurutan Shell (Shell Sort)
Untuk setiap metode pengurutan akan ditulis algoritmanya. Dua metode pertama (bubble dan selection sort) melakukan prinsip pertukaran elemen dalam proses pengurutan sehingga keduanya dinamakan pengurutan dengan pertukaran (exchange sort), sedangkan dua metode terakhir melakukan prinsip geser dan sisip elemen dalam prose pengurutan (shift and insert sort). Semua metode pengurutan selalu melakukan operasi perbandingan elemen larik untuk menemukan posisi urutan yang tepat.
• Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
• Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and
keep sorted method)
• Insertion sort, tree sort
• Pengurutan berdasarkan pembagian dan penguasaan (devide and
conquer method)
• Quick sort, merge sort
• Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort
Metode pengurutan juga dapat diklasifikasikan sebagai metode pengurutan internal dan metode pengurutan eksternal.
1. Metode pengurutan internal, yaitu metode pengurutan untuk data yang disimpan di dala memori komputer. Umumnya struktur internal yang dipakai untuk pengurutaninternal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.
2. Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan di dalam disk storage, disebut juaga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
A. Metode Pengurutan Apung (Bubble Sort)
Metode pengurutan apung (bubble sort) diinspirasi oleh gelembung sabun yang berada di atas permukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan.
Metode sorting termudah. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan kekiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Prosedur Bubble Sort
Versi 1
void bubble_sort(){
for(int i=1;i
for(int j=n-1;j>=i;j--){
if(data[j]
tukar(&data[j],&data[j-1]); //ascending
}
}
}
Versi 2
void bubblesort2(){
for(i=1;i<6;i++){
for(int j=0;j<6-i;j++){
if(data[j]>data[j+1])
tukar(&data[j],&data[j+1]); //descending
}
}
}
Dengan prosedur diatas, data terurut naik (ascending), untuk urut turun
(descending) silhkan ubah bagian:
if (data[j]
Menjadi:
if (data[j]> data[j-1]) tukar(&data[j],&data[j-1]);
Komentar Mengenai Pengurutan Apung
Pengurutan apung merupakam metode pengurutan yang tidak mangkus (efficient). Hal ini disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan. Untuk ukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang lama. Karena alasan itu, maka metode pengurutan apung jarang digunakan dalam praktek pemrograman. Namun, kelebihan metode ini adalah pada kesederhanaannya sederhana dan mudah dipahami.
B. Metode Pengurutan Seleksi (Selection Sort)
Metode pengurutan ini disebut pengurutan seleksi karena gagasan dasarnya adalah memilih elemen maksimum/ minimum dari larik, lalu menempatkan elemen maksimum/ minimum pada awal atau akhir larik dan merupakan kombinasi antara sorting dan searching.
Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
Ada dua varian algoritma pengurutan seleksi ditinjau dari pemilihan elemen maksimum/ minimum, yaitu :
1.Algoritma pengurutan seleksi-maksimum, yaitu memilih elemen maksimum sebagai basis pengurutan. Misalkan larik L dengan N=6 sebagai berikut:
Maka langkah-langkah pengurutannya adalah:
Contoh algoritma :
Procedure SelectionSort(input/output L : Larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan maksimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]}
Deklarasi
I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imaks : integer {indeks yang berisi nilai maksimum sementara}
Procedure tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← N downto 2 do {jumlah pengulangan sebanyak N-1}
{cari elemen maksimum pada elemen L[1..I]}
Imaks ← I {elemen pertama diasumsikan sebagai elemen maksimum sementara}
For J ← 2 to I do
If L[J] > L[Imaks] then
Imaks ← J
Endif
Endfor {pertukarkan L[Imaks] dengan L[I]}
Tukar(L[Imaks], L[I])
Endfor
2.Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis pengurutan. Misalkan larik L dengan N=6 sebagai berikut:
maka langkah-langkah pengurutannya adalah:
Contoh algoritma :
Procedure SelectionSort(input/output L : larikint, input N : integer)
{mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan pilih minimum}
{k.awal : elemen larik L sudah terdefinisi harganya}
{k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤... ≤ L[N]} Deklarasi I : integer
J : integer {pencacah untuk mencari nilai maksimum}
Imin : integer {indeks yang berisi nilai maksimum sementara}
Procedure Tukar(input/output A : integer, input/output : B : integer)
{mempertukarkan nilai A dan B}
Deskripsi
For I ← 1 to N-1 do {cari indeks dari elemen minimum di dalam larik L[I..N]}
Imin ← I
For J ← I+1 to N do
If L[J] > L[Imin] then
Imin ← J
Endif
Endfor {pertukarkan L[Imin] dengan L[I]}
Tukar(L[Imin], L[I])
Endfor
Prosedur Selection Sort
void selection_sort(){
for(int i=0;i
pos = i;
for(int j=i+1;j
if(data[j] < data[pos]) pos = j; //ascending
}
if(pos != i) tukar(pos,i);
}
}
Komentar Mengenai Metode Pengurutan Seleksi
Dibanding dengan metode pengurutan apung, metode pengurutan seleksi memiliki kinerjayang lebih baik. Alasannya, operasi pertukaran elemen hanya dilakukan sekali saja pada setiap pass, dengan demikian lamanya pengurutannya berkurang dibandingkan dengan metode pengurutan gelembung.
C. Metode Pengurutan Sisipan (Insetion Sort)
Pengurutan sisipan adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencairan posisi yang tepat dilakukan dengan cara menyisir elemen larik. Selama penyisiran dilakukan pergeseran elemen larik. Metode pengurutan sisip cocok untuk persoalan menyisipkan elemen baru ke dalam sekumpulan elemen yang sudah yang terurut.
Pada metode ini elemen terbagi menjadi 2 bagian yaitu kelompok sumber yang merupakan susunan asli dari kelompok tersebut (belum terurut) yaitu dari A1…..AN dan kelompok yang kedua adalah kelompok tujuan yaitu susunan elemen yang telah terurut dengan urutan dari A1….Ai -1. Langkah penyisipan dimulai dari i = 2 dengan pertambahan 1. Elemen ke i diambil dari kelompok sumber dan akan dipindahkan ke kelompok tujuan dengan cara menyisipkannya pada tempatnya yang sesuai.
Algoritma metode sisip langsung :
- langkah 0 : Baca vector yang akan diurutkan (dalam program utama)
- langkah 1 : Kerjakan langkah 2 sampai 5 untuk i = 2 sampai dengan N
- langkah 2 : Tentukan : T = A[i] (elemen yang akan disisipkan), A[0] = T (data sentinel) dan j = i -1.
- langkah 3 : (lakukan pergeseran). Kerjakan langkah 4 selama T < A[j]
- langkah 4 : Tentukan : A[j + 1] = A[j] dan j = j -1.
- langkah 5 : Tentukan : A[j + 1] = T
- langkah 6 : Selesai
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
Prosedur Insertion Sort
void insertion_sort(){
int temp;
for(int i=1;i
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
Komentar mengenai metode pengurutan sisipan
Kelemahan metode pengurutan sisipan terletak pada banyaknya operasi pergeseran yang dilakukan dalam mencari posisi yang tepat untuk elemen larik. Pada setiap pass i, opeasi pergeseran yang diperlukan maksimum i -1 kali. Untuk larik yang berukuran besar, jumlah operasi pergeseran meningkat secara kuadratik, sehingga pengurutan sisip kurang bagus untuk volume data yang besar.
D. Metode Pengurutan Shell (Shell Sort)
Metode ini merupakan perbaikan terhadap metode pengurutan sisipan. Kelemahan metode pengurutan sisipan sudah disebutkan pada bagian sebelumnya. Jika data pada posisi ke-1000 ternyata posisi yang tepat adalah sebagai elemen kedua, maka dibutuhkan kira-kira 998 kali pergeseran elemen.
Untuk mengurangi pergeseran terlalu jauh, kita mengurutkan larik setiap k elemen dengan metode pengurutan sisip, misalkan kita urutkan setiap 5 elemen (k kita namakan juga step atau increment). Selanjutnya, digunakan nilai step yang lebih kecil, misalnya k = 3, lalu diurut setiap 3 elemen. Begitu seterusnya sampai nilai k = 1. Karena nilai step selalu berkurang maka metode pengurutan Shell kadang – kadang dinamakan juga metode pengurutan kenaikan berkurang (diminishing increment sort)
Komentar mengenai metode pengurutan shell
Metode pengurutan shell merupakan perbaikan terhadap metode pengurutan sisipan. Namun tidak seorangpun yang pernah dapat menganalisis metode pengurutan shell secara tepat, karena pemilihan ukuran step (seperti 5, 3, 1, atau pendefinisian ukuran tep dengan pernyataan step = step div 3+ 1) didasarkan pada pertimbangan sugesti.
Tidak ada aturan yang diketahui untuk menemukan ukuran step yang optimum. Jika step yang dipilih berdekatan, semakin banyak jumlah pass yan g dihasilkan, tapi setiap pass mungkin lebih cepat. Jika ukuran step menurun dengan cepat, jumlah pass akan berkurang tetapi setiap pass menjadi lebih panjang (lama).
IV. Algoritma
Type
Larik= array [1..100] of integer ;
Deklarasi
n : integer
x : integer
i : integer
L : Larik
ketemu:boolean {pertanda untuk menentukan apakah x ditemukan}
Procedure bagi_dua(input L: Larikint, input n: integer, input x : integer,output idx : integer, var ketemu:boolean)
Deklarasi
i, j : integer { indeks kiri dan indeks kanan larik}
k : integer { indeks elemen tengah }
Idx:integer
i← 1 {ujung kiri larik}
j ← n (ujung kanan larik}
Ketemu ← false {asumsikan x belum ditemukan}
While (not Ketemu) and (I <= J) do
k ← (i + j) div 2 (bagi dua larik L pada posisi k}
If L[k] = x then
{lakukan pencarian pada larik bagian kanan, set indeks ujung kiri larik yang baru}
Ketemu ← true
Idx ← k
Else
If (L[k] > x) then
J ← k - 1
Else
{lakukan pencarian pada larik bagian kiri, set indeks ujung kanan larik yang baru}
I ← k + 1
Endif
Endif
Endwhile
{ketemu = true or i > j}
If (ketemu) then { x ditemukan}
Idx← k
Else { x tidak ditemukan dalam larik }
Idx← -1
End if
V. Program
Program Searching ;
Uses wincrt;
Type
Larik= array [1..100] of integer ;
Var
N : integer;
X : integer;
i : integer;
L : Larik;
ketemu:boolean;
Procedure bagi_dua(N : integer;var ketemu:boolean);
Var
I, J : integer;
K : integer;
Idx:integer;
Begin
I := 1;
J := N;
Ketemu := false;
While (not Ketemu) and (I <= J) do
Begin
K := (I + J) div 2 ;
If L[K] = X then
Begin
Ketemu := true;
Idx := K;
End
Else
Begin
If (L[K] > X) then
J := K - 1
Else
I := K + 1 ;
End;
End;
End;
Begin
write ('Masukan Jumlah Data = '); readln (N);
for i:=1 to N do
begin
write ('Masukan Data = '); readln (L[i]);
end;
write('Masukan Data yang Dicari = '); readln (X);
bagi_dua(N,ketemu);
if ketemu then
write ('Data yang Anda Cari Ada')
else
write('Maaf, Data yang Anda Cari Tidak Ada. Coba Ulangi Lagi') ;
end.
Searching array
Array pada dasarnya merupakan suatu tipe data yang dapat menampung serangkaian tipe data yang sama dalam suatu variabel. Bila pada dasarnya kita mengenal tipe variabel seperti character atau char, integer atau int, dan float atau real, maka tipe data tersebut umumnya hanya dapat menampung sebuah data saja bila tidak menggunakan array.
Ketika menggunakan array pun, banyak bahasa pemrograman yang menggunakan index atau key dalam array menggunakan angka bulat atau integer yang umumnya dimulai dari 0 (nol).
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Terdapat 2 metode pencarian yaitu Metode Pencarian Beruntun (Sequential Search) dan Metode Pencarian Bagidua (Binary Search), kita hanya akan membahas metode yang kedua yaitu Metode Pencarian Bagidua (Binary Search). Karena metode ini adalah metode pencarian pada data terurut yang paling efficient. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.
Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching merupakan pencarian data dengan cara menelusuri data-data tersebut Pencarian(searching) merupakan proses yang fundamental dalam pengolahan data.
Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama ( baik bertipe dasar atau bertipe bentukan ). Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Di dalam Buku Algoritma dan Pemrograman telah disebutkan bahwa aktivitas yang berkaitan dengan pengolahan data sering didahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.
Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang sama yang sama juga dilakukan pada proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahakan sudah terdapat di dalam kumpulan. Jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Binary Search Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan.
Prinsip pencarian biner adalah:v
o Data diambil dari posisi 1 sampai posisi akhir N
o Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
o Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
o Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
o Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
o Jika data sama, berarti ketemu.
Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:
Misalkan, kita ingin mencari posisi dari nilai 56. Pertama kali, larik di atas dapat kita bagi menjadi 2 sublarik sebagai berikut:
Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1
(11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi. Proses di atas diulangi lagi. Sublarik 2 dibagi 2 lagi sehingga menghasilkan sublarik dibawah ini:
Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut:
Larik merupakan tipe data terstruktur. Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan sekumpulan elemen bertipe sama secara berturutan (sequential) di dalam memori komputer. Setiap elemen larik data diacu melalui indeksnya.
Karena elemen disimpan secara berurutan, indeks larik haruslah suatu tipe yang juga mempunyai keterurutan (memiliki suksesor dan ada predesesor), misalnya tipe integer atau karakter. Jika indeks larik adalah karakter maka keterurutan indeks sesuai dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan nama larik berikut indeksnya.
Larik dipelajari lebih mendalam dalam Buku 2, karena larik adalah struktur internal (yaitu, struktur yang direalisasikan di dalam memori utama), maka pencarian elemen di dalam larik disebut juga pencarian internal. Sedangkan pada pencarian eksternal, pencarian dilakukan terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk. Penyimpanan data di dalam storage bersifat permanen dengan tujuan agar dapat dibaca kembali untuk pemrosesan lebih lanjut.
Persoalan Pencarian
Diberikan larik L yang sudah terdefinisi elemen-elemennya , dan x adalah elemen yang bertipe sama dengan elemen larik L. Carilah x di dalam larik L.
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam, bergantung pada spesifikasi (spek) rinci dari persolan tersebut, misalnya:
a. Pencarian hanya untuk memeriksa keberadaan x. Keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik.
b. Hasil pencarian adalah indeks elemen larik. Jika x ditemukan, maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat di dalam larik L, maka idx diisi dengan harga khusus, misalnya -1.
c. Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil pencarian. Jika x ditemukan, maka sebuah peubah bertipe boolean, misalnya ketemu, diisi dengan nilai true, sebaliknya “ketemu” diisi dengan nilai false. Hasil pencarian ini selanjutnya disimpulkan pada pemanggilan prosedur.
Contoh : keluaran hasil pencariaan berupa boolean
Perhatikan larik
Misalkan x = 68, maka ketemu= true, dan bila x = 100, maka ketemu = false.
Untuk kedua macam keluaran b dan c di atas, kita mengkonsultasi hasil pencariaan setelah prose pencarian selesai dilakukan, bergantung pada kebutuhan. Misalnya menampilkan pesan bahwa x ditemukan (atau tidak ditemukan) atau memanipulasi nilai x.
Contoh:
(1) If ketemu then {artinya ketemu = true}
Write (x, ‘ditemukan’)
Else
Write(x, ‘ditemukan’)
Endif
(2) If idx = -1 then {berarti x ditemukan}
L[idx] L[idx] + 1 {manipulasi nilai x}
Endif
Hal lain yang harus diperjelas dalam spesifikasi persoalan pencarian adalah mengenai duplikasi data. Apabila x yang dicari terdapat lebih dari satu banyaknya di dalam larik L, maka hanya x yang pertama kali ditemukan saja yang diacu dan algoritma pencarian selesai. Sebagai contoh, larik memiliki tiga buah nilai 36. Bila x = 36, maka algoritma pencarian selesai ketika x ditemukan pada elemen ke-2 dan menghasilkan idx=2 (atau menghasilkan ketemu = true jika mengacu pada keluaran pencarian jenis b). Elemen 36 lainnya tidak dipertimbangkan lagi.
Metode pencarian yang akan dibahas adalah :
1. Metode pencarian beruntun.
2. Metode pencarian bagidua.
Untuk masing-masing algoritma dari kedua metode percarian metode pencarian di atas, tipe larik yang digunakan dideklarasikan di dalam bagian deklarasi global seperti di bawah ini. Larik L adalah bertipe larik Int.
{kamus data global}
DEKLARASI
const Nmaks = 100{jumlah maksimum elemen larik}
type LarikInt = array[1..Nmaks] of integer
Metode pencarian beruntun
Metode pencarian yang paling sederhana yaitu metode pencarian beruntun. Nama lain metode pencarian beruntun adalah pencarian lurus (linear search). Pada dasarnya metode pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama, sampai elemen yang dicari ditemukan, atau seluruh elemen sudah diperiksa.
(a) Versi 1 (pembandingan elemen dilakukan di awal pengulangan)
1. Hasil pencarian : sebuah peubah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan tidak dihentikan bila L[i] = x atau i = n. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah sebuah peubah boolean (misal nama peubahnya ketemu) yang bernilai true jika x ditemukan atau bernilai false jika x tidak ditemukan. Untuk pencarian beruntun yang berupa fungsi, contoh cara pemanggilan fungsi SeqSearch1:
read(x)
if not SeqSearch1(L,n,x) then
write(x,’tidak ditemukan!’)
else
{proses terhadap x}
...
endif
2. Hasil pencarian : indeks elemen larik yang mengandung nilai x.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan dihentikan bila L[i] = x atau i = N. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah peubah idx yang berisi indeks larik tempat x ditemukan. Jika x tidak ditemukan, idx diisi dengan -1.
(b) Versi 2 (pembandingan elemen dilakukan di dalam badan pengulangan)
Pada versi yang kedua ini, aksi pembandingan dilakukan didalam badan pengulangan(jadi bukan diawal pengulangan seperti pada varian pertama). Untuk itu, kita memerlukan sebuah peubah boolean yang akan berfungsi untuk menyatakan apakah x sudah ditemukan.
Misalkan peubah tersebut bernama ketemu yang pada mulanya diisi nilai false. Bila x ditemukan pada elemen ke-i yaitu L[i]= x, maka ketemu diisi dengan nilai true. Pengulangan dihentikan bila ketemu = true. Hasil pencarian disimpulkan di luar badan pengulangan. Algoritma pencarian beruntun versi 2 lebih elegan dibandingkan dengan algoritma versi 1 karena semua elemen dibandingkan dengan cara yang sama. Algoritma pencarian kita buat 2 macam, yang pertama untuk hasil pencaraian berupa peubah boolean, dan algoritma kedua untuk hasil pencarian berupa indeks elemen larik.
1. Hasil pencarian : sebuah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan. Pada versi ini, peubah boolean ketemu diinisialisasi dengan nilai false dan indeks larik i diisi dengan 1(karena pembandingan dimulai dari elemen pertama). Setiap elemen L dibandingkan dengan x mulai dari elemen pertama.
Jika L[i]=x, peubah ketemu diisi nilai true dan pengulangan dihentikan. Sebaliknya L[i] tidak sama dengan x pembandingan dilanjutkan untuk elemen berikutnya(i=i+1). Pada versi 2 ini, setiap elemen larik, termasuk elemen terakhir, diperiksa dengan cara yang sama. Keluaran yang dihasilkan adalah nilai yang disimpan di dalam peubah ketemu.
2. Hasil pencarian : indeks elemen larik mengandung nilai x.
Algoritmanya sama seperti SeqSearch3 di atas, hanya saja setelah kalang while-do ditambahkan pernyataan if-then untuk memberikan hasil pencarian berupa indeks elemen larik(idx)yang bernilai x.Jika x tidak ditemukan maka idx diisi nilai 1.
Algorima pencarian beruntun versi 2 untuk kategori hasil berupa indeks elemen larik dapat kita tulis sebagai prosedur atau sebagai fungsi.
Kinerja Metode Pencarian Beruntun
Secara umum, metode pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran n elemen. Maka pada kasus di mana x tidak terdapat di dalam larik atau x ditemukan pada elemen yang terakhir, kita harus melakukan perbandingan dengan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak n kali. Kita katakan bahwa waktu pencarian dengan algoritma pencarian beruntun sebanding dengan n.
Bayangkan bila larik berukuran 100.000 buah elemen, maka kita harus melakukan perbandingan sebanyak 100.000 buah elemen. Andaikan satu operasi perbandingan elemen larik membutuhkan waktu 0,01 detik, maka untuk 100.000 buah perbandingan diperlukan waktu sebesar 1000 detik atau 16,7 menit. Semakin banyak elemen larik, semakin lama pula waktu pencariannya. Karena itulah metode pencarian beruntun tidak bagus untuk volume data yang besar.
Metode Pencarian Beruntun pada Larik Terurut
Larik yang elemen-elemennya sudah terurut dapat meningkatkan algoritma pencarian beruntun. Jika pada larik tidak terurut jumlah perbandingan elemen larik maksimum n kali, maka pada larik terurut (dengan ansumsi distribusi elemen-elemen larik adalah seragam atau uniform) hanya dibutuhkan rata-rata n/2 kali perbandingan. Hal ini karena pada larik yang terurut kita dapat segera menyimpulkan bahwa x tidak terdapat di dalam larik bila ditemukan elemen larik yang lebih besar dari x (pada larik yang terurut menaik) [TEN86].
Metode Pencarian Beruntun dengan Sentinel
Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari sebuah metode pencarian beruntun yang mangkus. Nilai x yang akan di cari sengaja ditambahkan terlebih dahulu pada elemen ke-n+1. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel. Selanjutnya, pencarian beruntun dilakukan di dalam larik L[1..n+1]. Akibatnya, proses pencarian selalu menjamin bahwa x pasti berhasil ditemukan.
Untuk menyimpulkan apakah x ditemukan pada elemen sentinel atau bukan, kita dapat mengetahuinya dengan melihat nilai idx. Jika idx = n+1 (yang berarti x ditemukan pada elemen sentinel), maka hal itu berarti bahwa x tidak terdapat di dalam larik L semula (sebelum penambahan sentinel).
Keuntungannya, elemen sentinel otomatis sudah menjadi elemen yang ditambahkan ke dalam larik. Sebaliknya, jika idx < n+1 (yang berarti x ditemukan sebelum sentinel), maka hal itu berarti bahwa x sudah ada di dalam larik L semula.
Metode Pencarian Bagidua
Pencarian pada data yang terurut menunjukan kinerja yanh lebih baik daripada pencarian pada data yang belum terurut. Hal ini sudah kita bicarakan pada metode pencarian beruntun untuk data yang sudah terurut. Data yang terurut banyak ditemukan di kehidupan sehari-hari.
Data nomor telepon di dalam buku telepon misalnya, sudah terurut berdasarkan nama/instansi pelanggan telepon dari A sampai Z. Data karyawan diurut berdasarkan nomor induknya dari nomor kecil ke nomor besar. Data mahasiswa diurut berdasarkan NIM (Nomor Induk Mahasiswa), kata-kata (entry) di dalam kamus bahasa inggris/indonesia telah diurut dari A sampai Z, dan sebagainnya.
Untuk mencari arti kata tertentu di dalam kamus (misalnya kamus bahasa inggris), kita tidak membuka halaman kamus tersebut dari halaman awal sampai halaman terakhir satu per satu, namun kita mencarinya dengan cara membelah atau membagi dua buku itu.
Jika kata yang dicari tidak terletak di halaman pertengahan itu, kita mencari lagi di belahan bagian kiri atau belahan bagian kanan dengan cara membagi dua belahan yang dimaksud. Begitu seterusnya sampai kata yang dicari ditemukan. Hal ini hanya bisa dilakukan jika kata-kata di dalam kamus sudah terurut.
Prinsip pencarian dengan cara membagi data atas dua bagian mengilhami metode pencarian bagidua. Data yang disimpan didalam larik harus sudah terurut. Untuk memudahkan pembahasan, selanjutnya kita misalkan elemen larik sudah terurut menurun. Dalam proses pencarian, kita memerlukan dua buah indeks larik, yaitu indeks terkecil dan indeks terbesar. Kita menyebut indeks terkecil sebagai indeks ujung kiri larik dan indeks terbesar sebagai indeks ujung kanan larik. Istilah “kiri” dan “kanan” dinyatakan dengan membayangkan elemen larik terentang horizontal.
Misalkan indeks kiri adalah i dan indeks kanan adalah j. Pada mulanya kita inisialisasi i dengan 1 dan j dengan n.
Langkah 1 : Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (i+j) div 2.
(Elemen tengah, L[k], membagi larik menjadi dua bagian, yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j)
Langkah 2 : Periksa apakah L[k] = x. Jika L[k] = x, pencarian selesai sebab x sudah ditemukan. Tetapi, jika L[k] tidak sama dengan x, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < x, maka pencarian dilakukan lagi pada larik bagian kiri. Sebaliknya, jika L[k] > x, pencarian dilakukan lagi pada larik bagian kanan.
Langkah 3 : Ulangi Langkah 1 hingga x ditemukan atau i > j (yaitu, ukuran larik sudah nol !)
Algoritma pencarian bagidua pada larik integer yang sudah terurut kita tuliskan di bawah ini, masing-masing sebagai prosedur dan sebagai fungsi. Untuk algoritma pencarian bagidua pada larik yang sudah terurut menaik, kita hanya perlu mengganti pernyataan if (L[k] > x ) dengan (if L[k] < x).
Kinerja Metode Pencarian Bagidua
Pembaca dapat melihat bahwa pada setiap kali pencarian, larik dibagidua menjadi dua bagian yang berukuran hampir sama. Pada setiap pembagian, elemen tengah dibandingkan apakah sama dengan x (if (L[k] = x).
Pada kasus terburuk, yaitu pada kasus x tidak terdapat di dalam larik atau x ditemukan setelah ukuran larik tinggal 1 elemen, larik akan dibagi sebanyak 2log (n) kali, sehingga jumlah pembandingan yang dibutuhkan adalah sebanyak 2log (n) kali.
Kita katakan bahwa waktu pencarian sebanding dengan 2log(n) [WIR76]. Untuk n = 256 elemen misalnya, kasus terburuk menghasilkan pembagian larik sebanyak 2log(256) = 8 kali, yang berarti jumlah pembandingan elemen adalah 8 kali (bandingkan dengan metode pencarian beruntun yang pada kasus terburuk melakukan pembandingan sebanyak 256 kali). Jadi, untuk larik yang terurut, algoritma pencarian bagidua jauh lebih cepat daripada pencarian beruntun.
Pencarian pada Larik Terstruktur
Metode pencarian yang dibahas sebelum ini menggunakan larik dengan elemen-elemen bertipe sederhana. Pada kebanyakan kasus, elemen larik sering bertipe terstruktur. Contoh, misalkan M adalah sebuah larik yang elemennya menyatakan nilai ujian seorang mahasiswa untuk suatu mata kuliah (MK) yang ia ambil. Data setiap mahasiswa adalah NIM (Nomor Induk Mahasiswa), nama mahasiswa, mata kuliah yang ia ambil, dan nilai mata kuliah tersebut. Deklarasi nama dan tipe adalah sebagai berikut :
DEKLARASI
const Nmaks = 100
type Mahasiswa : record < NIM : integer, {Nomor Induk Mahasiswa}
NamaMhs : string,{nama mahasiswa}
KodeMK : string, {kode mata kuliah}
Nilai: char {indeks nilai MK (A/B/C/D/E)}
>
type TabMhs : array [1..Nmaks] of Mahasiswa
M : TabMhs
Pencarian pada Larik yang Tidak Bertipe Numerik
Meskipun algoritma-algoritma pencarian yang sudah dikemukakan di atas diterapkan pada larik integer, mereka tetap benar untuk larik data yang bertipe bukan numerik misalnya data bertipe karakter, maupun string.
Menggunakan Metode Pencarian Beruntun atau Metode Pencarian Bagidua?
Kedua metode pencarian ini mempunyai kelebihan dan kekurangan masing-masing. Metode pencarian beruntun dapat digunakan baik untuk data yang belum terurut maupun untuk data yang sudah terurut. Sebaliknya, metode pencarian bagidua hanya dapat digunakan untuk data yang sudah terurut saja.
Ditinjau dari kierja pencarian, sudah mengtahui bahwa untuk kasus terburuk (yaitu jika pencarian gagal menemukan x), algoritma pencarian beruntun memerlukan waktu yang sebanding dengan n (banyaknya data), sedangkan algoritma pencarian membutuhkan waktu yang sebaning dengan 2log (n). Karena 2log (n) < n untuk n > 1, maka jika n semakin besar waktu pencarian dengan algoritma bagidua jauh lebih sedikit daripada waktu pencarian dengan algoritma beruntun.
Sebagai perbandingan antara algoritma pencarian beruntun dengan pencarian bagidua, ditinjau dari kasus di mana x tidak ditemukan di dalam larik yang sudah terurut. Misalkan,
(a)untuk larik yang berukuran n = 256 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 256 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (256) = 8 kali,
(b)untuk larik yang berukuran n = 1024 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 1024 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (1024) = 10 kali,
Ketika menggunakan array pun, banyak bahasa pemrograman yang menggunakan index atau key dalam array menggunakan angka bulat atau integer yang umumnya dimulai dari 0 (nol).
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Terdapat 2 metode pencarian yaitu Metode Pencarian Beruntun (Sequential Search) dan Metode Pencarian Bagidua (Binary Search), kita hanya akan membahas metode yang kedua yaitu Metode Pencarian Bagidua (Binary Search). Karena metode ini adalah metode pencarian pada data terurut yang paling efficient. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.
Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching merupakan pencarian data dengan cara menelusuri data-data tersebut Pencarian(searching) merupakan proses yang fundamental dalam pengolahan data.
Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama ( baik bertipe dasar atau bertipe bentukan ). Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Di dalam Buku Algoritma dan Pemrograman telah disebutkan bahwa aktivitas yang berkaitan dengan pengolahan data sering didahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.
Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang sama yang sama juga dilakukan pada proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahakan sudah terdapat di dalam kumpulan. Jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Binary Search Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan.
Prinsip pencarian biner adalah:v
o Data diambil dari posisi 1 sampai posisi akhir N
o Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
o Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
o Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
o Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
o Jika data sama, berarti ketemu.
Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:
Misalkan, kita ingin mencari posisi dari nilai 56. Pertama kali, larik di atas dapat kita bagi menjadi 2 sublarik sebagai berikut:
Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1
(11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi. Proses di atas diulangi lagi. Sublarik 2 dibagi 2 lagi sehingga menghasilkan sublarik dibawah ini:
Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut:
Larik merupakan tipe data terstruktur. Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan sekumpulan elemen bertipe sama secara berturutan (sequential) di dalam memori komputer. Setiap elemen larik data diacu melalui indeksnya.
Karena elemen disimpan secara berurutan, indeks larik haruslah suatu tipe yang juga mempunyai keterurutan (memiliki suksesor dan ada predesesor), misalnya tipe integer atau karakter. Jika indeks larik adalah karakter maka keterurutan indeks sesuai dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan nama larik berikut indeksnya.
Larik dipelajari lebih mendalam dalam Buku 2, karena larik adalah struktur internal (yaitu, struktur yang direalisasikan di dalam memori utama), maka pencarian elemen di dalam larik disebut juga pencarian internal. Sedangkan pada pencarian eksternal, pencarian dilakukan terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk. Penyimpanan data di dalam storage bersifat permanen dengan tujuan agar dapat dibaca kembali untuk pemrosesan lebih lanjut.
Persoalan Pencarian
Diberikan larik L yang sudah terdefinisi elemen-elemennya , dan x adalah elemen yang bertipe sama dengan elemen larik L. Carilah x di dalam larik L.
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam, bergantung pada spesifikasi (spek) rinci dari persolan tersebut, misalnya:
a. Pencarian hanya untuk memeriksa keberadaan x. Keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik.
b. Hasil pencarian adalah indeks elemen larik. Jika x ditemukan, maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat di dalam larik L, maka idx diisi dengan harga khusus, misalnya -1.
c. Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil pencarian. Jika x ditemukan, maka sebuah peubah bertipe boolean, misalnya ketemu, diisi dengan nilai true, sebaliknya “ketemu” diisi dengan nilai false. Hasil pencarian ini selanjutnya disimpulkan pada pemanggilan prosedur.
Contoh : keluaran hasil pencariaan berupa boolean
Perhatikan larik
Misalkan x = 68, maka ketemu= true, dan bila x = 100, maka ketemu = false.
Untuk kedua macam keluaran b dan c di atas, kita mengkonsultasi hasil pencariaan setelah prose pencarian selesai dilakukan, bergantung pada kebutuhan. Misalnya menampilkan pesan bahwa x ditemukan (atau tidak ditemukan) atau memanipulasi nilai x.
Contoh:
(1) If ketemu then {artinya ketemu = true}
Write (x, ‘ditemukan’)
Else
Write(x, ‘ditemukan’)
Endif
(2) If idx = -1 then {berarti x ditemukan}
L[idx] L[idx] + 1 {manipulasi nilai x}
Endif
Hal lain yang harus diperjelas dalam spesifikasi persoalan pencarian adalah mengenai duplikasi data. Apabila x yang dicari terdapat lebih dari satu banyaknya di dalam larik L, maka hanya x yang pertama kali ditemukan saja yang diacu dan algoritma pencarian selesai. Sebagai contoh, larik memiliki tiga buah nilai 36. Bila x = 36, maka algoritma pencarian selesai ketika x ditemukan pada elemen ke-2 dan menghasilkan idx=2 (atau menghasilkan ketemu = true jika mengacu pada keluaran pencarian jenis b). Elemen 36 lainnya tidak dipertimbangkan lagi.
Metode pencarian yang akan dibahas adalah :
1. Metode pencarian beruntun.
2. Metode pencarian bagidua.
Untuk masing-masing algoritma dari kedua metode percarian metode pencarian di atas, tipe larik yang digunakan dideklarasikan di dalam bagian deklarasi global seperti di bawah ini. Larik L adalah bertipe larik Int.
{kamus data global}
DEKLARASI
const Nmaks = 100{jumlah maksimum elemen larik}
type LarikInt = array[1..Nmaks] of integer
Metode pencarian beruntun
Metode pencarian yang paling sederhana yaitu metode pencarian beruntun. Nama lain metode pencarian beruntun adalah pencarian lurus (linear search). Pada dasarnya metode pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama, sampai elemen yang dicari ditemukan, atau seluruh elemen sudah diperiksa.
(a) Versi 1 (pembandingan elemen dilakukan di awal pengulangan)
1. Hasil pencarian : sebuah peubah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan tidak dihentikan bila L[i] = x atau i = n. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah sebuah peubah boolean (misal nama peubahnya ketemu) yang bernilai true jika x ditemukan atau bernilai false jika x tidak ditemukan. Untuk pencarian beruntun yang berupa fungsi, contoh cara pemanggilan fungsi SeqSearch1:
read(x)
if not SeqSearch1(L,n,x) then
write(x,’tidak ditemukan!’)
else
{proses terhadap x}
...
endif
2. Hasil pencarian : indeks elemen larik yang mengandung nilai x.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan dihentikan bila L[i] = x atau i = N. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah peubah idx yang berisi indeks larik tempat x ditemukan. Jika x tidak ditemukan, idx diisi dengan -1.
(b) Versi 2 (pembandingan elemen dilakukan di dalam badan pengulangan)
Pada versi yang kedua ini, aksi pembandingan dilakukan didalam badan pengulangan(jadi bukan diawal pengulangan seperti pada varian pertama). Untuk itu, kita memerlukan sebuah peubah boolean yang akan berfungsi untuk menyatakan apakah x sudah ditemukan.
Misalkan peubah tersebut bernama ketemu yang pada mulanya diisi nilai false. Bila x ditemukan pada elemen ke-i yaitu L[i]= x, maka ketemu diisi dengan nilai true. Pengulangan dihentikan bila ketemu = true. Hasil pencarian disimpulkan di luar badan pengulangan. Algoritma pencarian beruntun versi 2 lebih elegan dibandingkan dengan algoritma versi 1 karena semua elemen dibandingkan dengan cara yang sama. Algoritma pencarian kita buat 2 macam, yang pertama untuk hasil pencaraian berupa peubah boolean, dan algoritma kedua untuk hasil pencarian berupa indeks elemen larik.
1. Hasil pencarian : sebuah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan. Pada versi ini, peubah boolean ketemu diinisialisasi dengan nilai false dan indeks larik i diisi dengan 1(karena pembandingan dimulai dari elemen pertama). Setiap elemen L dibandingkan dengan x mulai dari elemen pertama.
Jika L[i]=x, peubah ketemu diisi nilai true dan pengulangan dihentikan. Sebaliknya L[i] tidak sama dengan x pembandingan dilanjutkan untuk elemen berikutnya(i=i+1). Pada versi 2 ini, setiap elemen larik, termasuk elemen terakhir, diperiksa dengan cara yang sama. Keluaran yang dihasilkan adalah nilai yang disimpan di dalam peubah ketemu.
2. Hasil pencarian : indeks elemen larik mengandung nilai x.
Algoritmanya sama seperti SeqSearch3 di atas, hanya saja setelah kalang while-do ditambahkan pernyataan if-then untuk memberikan hasil pencarian berupa indeks elemen larik(idx)yang bernilai x.Jika x tidak ditemukan maka idx diisi nilai 1.
Algorima pencarian beruntun versi 2 untuk kategori hasil berupa indeks elemen larik dapat kita tulis sebagai prosedur atau sebagai fungsi.
Kinerja Metode Pencarian Beruntun
Secara umum, metode pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran n elemen. Maka pada kasus di mana x tidak terdapat di dalam larik atau x ditemukan pada elemen yang terakhir, kita harus melakukan perbandingan dengan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak n kali. Kita katakan bahwa waktu pencarian dengan algoritma pencarian beruntun sebanding dengan n.
Bayangkan bila larik berukuran 100.000 buah elemen, maka kita harus melakukan perbandingan sebanyak 100.000 buah elemen. Andaikan satu operasi perbandingan elemen larik membutuhkan waktu 0,01 detik, maka untuk 100.000 buah perbandingan diperlukan waktu sebesar 1000 detik atau 16,7 menit. Semakin banyak elemen larik, semakin lama pula waktu pencariannya. Karena itulah metode pencarian beruntun tidak bagus untuk volume data yang besar.
Metode Pencarian Beruntun pada Larik Terurut
Larik yang elemen-elemennya sudah terurut dapat meningkatkan algoritma pencarian beruntun. Jika pada larik tidak terurut jumlah perbandingan elemen larik maksimum n kali, maka pada larik terurut (dengan ansumsi distribusi elemen-elemen larik adalah seragam atau uniform) hanya dibutuhkan rata-rata n/2 kali perbandingan. Hal ini karena pada larik yang terurut kita dapat segera menyimpulkan bahwa x tidak terdapat di dalam larik bila ditemukan elemen larik yang lebih besar dari x (pada larik yang terurut menaik) [TEN86].
Metode Pencarian Beruntun dengan Sentinel
Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari sebuah metode pencarian beruntun yang mangkus. Nilai x yang akan di cari sengaja ditambahkan terlebih dahulu pada elemen ke-n+1. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel. Selanjutnya, pencarian beruntun dilakukan di dalam larik L[1..n+1]. Akibatnya, proses pencarian selalu menjamin bahwa x pasti berhasil ditemukan.
Untuk menyimpulkan apakah x ditemukan pada elemen sentinel atau bukan, kita dapat mengetahuinya dengan melihat nilai idx. Jika idx = n+1 (yang berarti x ditemukan pada elemen sentinel), maka hal itu berarti bahwa x tidak terdapat di dalam larik L semula (sebelum penambahan sentinel).
Keuntungannya, elemen sentinel otomatis sudah menjadi elemen yang ditambahkan ke dalam larik. Sebaliknya, jika idx < n+1 (yang berarti x ditemukan sebelum sentinel), maka hal itu berarti bahwa x sudah ada di dalam larik L semula.
Metode Pencarian Bagidua
Pencarian pada data yang terurut menunjukan kinerja yanh lebih baik daripada pencarian pada data yang belum terurut. Hal ini sudah kita bicarakan pada metode pencarian beruntun untuk data yang sudah terurut. Data yang terurut banyak ditemukan di kehidupan sehari-hari.
Data nomor telepon di dalam buku telepon misalnya, sudah terurut berdasarkan nama/instansi pelanggan telepon dari A sampai Z. Data karyawan diurut berdasarkan nomor induknya dari nomor kecil ke nomor besar. Data mahasiswa diurut berdasarkan NIM (Nomor Induk Mahasiswa), kata-kata (entry) di dalam kamus bahasa inggris/indonesia telah diurut dari A sampai Z, dan sebagainnya.
Untuk mencari arti kata tertentu di dalam kamus (misalnya kamus bahasa inggris), kita tidak membuka halaman kamus tersebut dari halaman awal sampai halaman terakhir satu per satu, namun kita mencarinya dengan cara membelah atau membagi dua buku itu.
Jika kata yang dicari tidak terletak di halaman pertengahan itu, kita mencari lagi di belahan bagian kiri atau belahan bagian kanan dengan cara membagi dua belahan yang dimaksud. Begitu seterusnya sampai kata yang dicari ditemukan. Hal ini hanya bisa dilakukan jika kata-kata di dalam kamus sudah terurut.
Prinsip pencarian dengan cara membagi data atas dua bagian mengilhami metode pencarian bagidua. Data yang disimpan didalam larik harus sudah terurut. Untuk memudahkan pembahasan, selanjutnya kita misalkan elemen larik sudah terurut menurun. Dalam proses pencarian, kita memerlukan dua buah indeks larik, yaitu indeks terkecil dan indeks terbesar. Kita menyebut indeks terkecil sebagai indeks ujung kiri larik dan indeks terbesar sebagai indeks ujung kanan larik. Istilah “kiri” dan “kanan” dinyatakan dengan membayangkan elemen larik terentang horizontal.
Misalkan indeks kiri adalah i dan indeks kanan adalah j. Pada mulanya kita inisialisasi i dengan 1 dan j dengan n.
Langkah 1 : Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (i+j) div 2.
(Elemen tengah, L[k], membagi larik menjadi dua bagian, yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j)
Langkah 2 : Periksa apakah L[k] = x. Jika L[k] = x, pencarian selesai sebab x sudah ditemukan. Tetapi, jika L[k] tidak sama dengan x, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < x, maka pencarian dilakukan lagi pada larik bagian kiri. Sebaliknya, jika L[k] > x, pencarian dilakukan lagi pada larik bagian kanan.
Langkah 3 : Ulangi Langkah 1 hingga x ditemukan atau i > j (yaitu, ukuran larik sudah nol !)
Algoritma pencarian bagidua pada larik integer yang sudah terurut kita tuliskan di bawah ini, masing-masing sebagai prosedur dan sebagai fungsi. Untuk algoritma pencarian bagidua pada larik yang sudah terurut menaik, kita hanya perlu mengganti pernyataan if (L[k] > x ) dengan (if L[k] < x).
Kinerja Metode Pencarian Bagidua
Pembaca dapat melihat bahwa pada setiap kali pencarian, larik dibagidua menjadi dua bagian yang berukuran hampir sama. Pada setiap pembagian, elemen tengah dibandingkan apakah sama dengan x (if (L[k] = x).
Pada kasus terburuk, yaitu pada kasus x tidak terdapat di dalam larik atau x ditemukan setelah ukuran larik tinggal 1 elemen, larik akan dibagi sebanyak 2log (n) kali, sehingga jumlah pembandingan yang dibutuhkan adalah sebanyak 2log (n) kali.
Kita katakan bahwa waktu pencarian sebanding dengan 2log(n) [WIR76]. Untuk n = 256 elemen misalnya, kasus terburuk menghasilkan pembagian larik sebanyak 2log(256) = 8 kali, yang berarti jumlah pembandingan elemen adalah 8 kali (bandingkan dengan metode pencarian beruntun yang pada kasus terburuk melakukan pembandingan sebanyak 256 kali). Jadi, untuk larik yang terurut, algoritma pencarian bagidua jauh lebih cepat daripada pencarian beruntun.
Pencarian pada Larik Terstruktur
Metode pencarian yang dibahas sebelum ini menggunakan larik dengan elemen-elemen bertipe sederhana. Pada kebanyakan kasus, elemen larik sering bertipe terstruktur. Contoh, misalkan M adalah sebuah larik yang elemennya menyatakan nilai ujian seorang mahasiswa untuk suatu mata kuliah (MK) yang ia ambil. Data setiap mahasiswa adalah NIM (Nomor Induk Mahasiswa), nama mahasiswa, mata kuliah yang ia ambil, dan nilai mata kuliah tersebut. Deklarasi nama dan tipe adalah sebagai berikut :
DEKLARASI
const Nmaks = 100
type Mahasiswa : record < NIM : integer, {Nomor Induk Mahasiswa}
NamaMhs : string,{nama mahasiswa}
KodeMK : string, {kode mata kuliah}
Nilai: char {indeks nilai MK (A/B/C/D/E)}
>
type TabMhs : array [1..Nmaks] of Mahasiswa
M : TabMhs
Pencarian pada Larik yang Tidak Bertipe Numerik
Meskipun algoritma-algoritma pencarian yang sudah dikemukakan di atas diterapkan pada larik integer, mereka tetap benar untuk larik data yang bertipe bukan numerik misalnya data bertipe karakter, maupun string.
Menggunakan Metode Pencarian Beruntun atau Metode Pencarian Bagidua?
Kedua metode pencarian ini mempunyai kelebihan dan kekurangan masing-masing. Metode pencarian beruntun dapat digunakan baik untuk data yang belum terurut maupun untuk data yang sudah terurut. Sebaliknya, metode pencarian bagidua hanya dapat digunakan untuk data yang sudah terurut saja.
Ditinjau dari kierja pencarian, sudah mengtahui bahwa untuk kasus terburuk (yaitu jika pencarian gagal menemukan x), algoritma pencarian beruntun memerlukan waktu yang sebanding dengan n (banyaknya data), sedangkan algoritma pencarian membutuhkan waktu yang sebaning dengan 2log (n). Karena 2log (n) < n untuk n > 1, maka jika n semakin besar waktu pencarian dengan algoritma bagidua jauh lebih sedikit daripada waktu pencarian dengan algoritma beruntun.
Sebagai perbandingan antara algoritma pencarian beruntun dengan pencarian bagidua, ditinjau dari kasus di mana x tidak ditemukan di dalam larik yang sudah terurut. Misalkan,
(a)untuk larik yang berukuran n = 256 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 256 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (256) = 8 kali,
(b)untuk larik yang berukuran n = 1024 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 1024 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (1024) = 10 kali,
Tidak ada komentar:
Posting Komentar