SORT AND SEARCH FILE

·         Definisi Pengurutan File

Setelah satu kebutuhan dalam sistern informasi adalah kesanggupan komputer dalam menyortir data. Record-record dari file transaksi harus disusun dalarn urutan tertentu  untuk membantu pengupdatean sequential master file secara efisien. Juga di dalarn pembuatan laporan, umunya record-record disusun dalam urutan tertentu untuk mendapatkan laporan yang mudah dibaca.

Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.

·         Jenis Pengurutan File

Dalam sistem penyortiran ini dikenal dua  metode yaitu metode              sort internal dan metode sort eksternal. Perbebedaan yang mendasar dari kedua metode ini adalah pada metode sort internal, semua record yang akan diproses dimuat ke dalam memori komputer lalu diproses sort (sortir ). Sedangkan pada metode sort eksternal record- record diproses tidak semuanya dapat dimuat ke dalarn memori komputer, karena keterbatasan memri komputer. Metode           sort eksternal di dalam penerapannya nanti, menggunakan pula metode          sort internal.

Contoh,

Sebuah file berisi 2000 record harus disortir ke dalam memori yang hanya, dapat menampung 5000 record sekaligus. Untuk itu dugunakan metode sort ekstemal. Langkah awal dalam penyortiran ini adalah record-record dibagi kedalam beberapa file agar dapat ditampung sekaligus di memori komputer, lalu masing-­masing bagian disortir internal. Bagian-bagian file yang telah tersortir ini disebut sorted sublist. Kita kenal, sorted sublist 1 (record 1- 1000) dan sorted sublist 2 (record 1001-2000). Setelah itu kedua sorted sublist ini (atau disebut juga Run) digabung (merge) sehingga didapat file gabungan (merge file)yang record-recordnyatelah disortir (lihat gambar 1).

Kita simpulkan,langkah-langkah metode sort eksternal ini adalah

a.         Internal sort, dimana file dibagi menjadi beberapa bagian file kemudian disortir.

b.        Merge, dimana bagian-bagian file ini (sorted sublist) digabung menjadi satu atau lebih file gabungan. File-file gabungan ini kemudian digabung lagi sampai akhirnya didapatkan sebuah file gabungan yang berisi semua record-record yang telah tersortir.

c.         Cutput, dimana menyalin file gabungan yang telah tersortir kemediun storage terakhir.

Faktor-faktor yang mempengaruhi metode eksternal sort antara lain:

a.       Jumlah record yang akan disortir.

b.      Ukuran record (panjang record).

c.       Jumlah storage yang digunakan.

d.      Kapasitas internal memori.

e.       Distribusi nilai key dalam input file.

Teknik sort/merge file ini berbeda satu dengan yang lainnya dalam hal:

a.       Metode sort internal yang digunakan.

b.      Jumlah main memori yang disediakan untuk sort internal.

c.       Distribusi dari sorted sublist di secondary storage menjadi satu atau lebih file gabungan dalam satu langkah gabungan (merge pass).

macam-macam teknik sort/merge file ini adalah:

a.    Natural Merge File

b.    Balance Merge File

c.    Polypase Merge File

d.   Cascade Merge File

·         Definisi Pencarian File

Pencarian file adalah sebuah operasi untuk mencari informasi atau file tentang semua item yang jatuh dalam kategori tertentu,penggalian informasi untuk item manapun di mana informasi yang dicatat memenuhi kriteria tertentu, dan menentukan apakah ada atau tidak ada pola tertentu dari informasi mana saja di file. Dalam melakukan pencarian ada teknik pencarian atau pelacakan.Dimana teknik pencarian adalah suatu teknik atau cara yang dilakukan untuk mencari solusi dari suatu permasalahan dengan sekumpulan kemungkinan yang ada. Empat kriteria yang dapat  digunakan untuk mengukur perfomansi teknik pencarian :

1.    Completeness artinya apakah teknik yang digunakan akan menjamin penemuan solusi jika solusinya memang ada

2.    Time complexity artinya berapa lama waktu yang diperlukan

3.    Space complexity artinya berapa banyak memori yang diperlukan

4.    Optimality artinya apakah teknik yang digunakan akan menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda

·         Jenis Pencarian File

Dalam melakukan pencarian  ada dua jenis pencarian file, yaitu pencarian buta (blind search) dan Pencarian terbimbing (heuristic search)

A.    Pencarian buta (blind search)

             Pencarian buta merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir ditemukan. Idenya adalah menguji seluruh kemungkinan yang ada untuk menemukan solusi.

Jenis-jenis Pencarian buta (blind search) :

1.      Pencarian melebar pertama (Breadth – First Search)

 Breadth – First Search Semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan.

Keuntungan :

·         tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik

·         jika ada 1 solusi, maka breadth – first search akan menemukannya,jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan.

·         Kesimpulan : complete dan optimal

Kelemahan :

·         membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan. Hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah

·         membutuhkan waktu yang cukup lama

2.      Pencarian mendalam pertama (Depth – First Search)

Depth – First Search pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan padasimpul sebelah kanan dan simpul sebelah kiri dapat dihapus dari memory. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.

Keuntungan :

·         membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan

·         Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat ->  waktu cepat

Kelemahan :

·         Memungkinkan tidak ditemukannya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga) -> tidak complete karena tidak ada jaminan menemukan solusi

·         Hanya mendapat 1 solusi pada setiap pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik -> tidak optimal.

B. Pencarian terbimbing (heuristic search)

            Kata heuristic berasal dari bahasa Yunani heuriskein dari kata dasar eureka atau heurika yang berarti mengungkap atau menemukan. Dalam Artificial Intelligence, heuristic diperkenalkan sebagai suatu teknik yang meningkatkan efisiensi proses pencarian, yang dimungkinkan dengan mengorbankan kelengkapan.Menggunakan heuristic kita berharap mendapatkan solusi yang baik dari masalah yang sulit.

Pencarian terbimbing (heuristic search) adalah yaitu terdapatnya informasi awal yang digunakan dalam proses pencarian. Pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, disebabkan karena waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang besar, teknik pencarian buta (blind search) bukan teknik yang baik untuk digunakan karena keterbatasan kecepatan komputer dan memori.

Dengan adanya teknik heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Fungsi dari teknik heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan. Contoh aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine. Ada empat jenis pencarian terbimbing (heuristic search) :

1.   Pembangkitan dan pengujian (Generate and Test)

Teknik ini merupakan gabungan dari DFS dan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Dimana nilai pengujian berupa jawaban “ya” atau “tidak”.

2.      Pendakian Bukit (Hill Climbing)

Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap kesalahan-kesalahan lainnya yang mungkin.

3.      Pencarian terbaik pertama (Best First Search)

Teknik Best First Search merupakan kombinasi dari teknik depth first search dan breadth first search dengan mengambil kelebihan dari kedua teknik tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node pada lebih rendah meskipun node tersebut memiliki nilai heuristic lebih baik. Pada best first search, pencarian diperbolehkan mengunjungi node di lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristic lebih buruk.

4.   Branch and Bound Search

v  Membentuk antrian satu-elemen, sampai jalur pertama adalah antrian berakhir pada node tujuan atau antrian kosong

v  Hapus jalur pertama dari antrian, kemudian membuat jalur baru dengan memperpanjang jalan pertama untuk semua dari node terminal

v   Menolak semua path baru dengan loop

v  Jika ada tambahkan jalur baru yang tersisa ke antrian

v  Urutkan seluruh antrian dengan panjang lintasan yang paling dekat di depan

v   Jika node tujuan ditemukan, berarti berhasil, jika tidak ditemukan berarti gagal