MAKALAH
SISTEM
BERKAS
ORGANISASI
BERKAS LANGSUNG
Disusun oleh:
Lusi Efrenti 1001091018
Desi Lasri Rahma Ayu 1001091014
Hardian Erlanda 1001091016
JURUSAN
TEKNOLOGI INFORMASI
POLITEKNIK
NEGERI PADANG
TAHUN
2012/2013
Pengertian Berkas Sequential
Adalah
merupakan cara yang paling dasar untuk mengorganisasikan kumpulan record-record
dalam sebuah berkas
Keuntungan
Kemampuan
untuk mengakses record berikutnya secara tepat
Pembuatan
Berkas Sequential
Meliputi penulisan record-record dalam serangkaian yang diinginkan pada
media penyimpanan.Tugas-tugasnya
:10.Pengumpulan data11.Perubahan data
dalam bentuk bahasa yang dapat dibaca oleh mesin12.Pengeditan data13.Pemeriksaan transaksi yang
ditolak 14.Penyortiran edit data
Kerugian
Korespondensi Satu-Satu
o
Dengan
menerjemahkan langsung dari kunci rekaman ke alamat rekaman, maka akan berlaku
suatu hubungan korespondensi satu-satu antara kunci dengan alamat rekaman.
o
Hal ini
menyebabkan harus disediakannya ruang yang sangat besar untuk menampung setiap
kemungkinan nilai kunci yang ada.
o
Contohnya :
untuk menyimpan data PNS yang kuncinya adalah NIP (terdiri dari 9 digit)
dibutuhkan sebanyak satu milyar alamat, karena kemungkinan yang dapat muncul
dari kode 9 digit adalah mulai dari angka 000000000 hingga 999999999).
o
Selain itu
dari cara korespondensi satu-satu juga akan mengakibatkan banyaknya pemborosan
ruang penyimpan, atau terjadi banyak alamat yang tidak dipergunakan alias
kosong.
o
Contohnya :
Kode NIP diawali dengan tiga digit kode departemen, yang tidak mungkin ada kode
departemen 000. Sehingga alamat 000000000 sampai 000999999 (sebanyak sejuta
alamat) tidak akan terpakai karena tidak ada rekaman dengan NIP di antara range
tersebut.
Pencarian Interpolasi
Berbeda dengan pencarian biner yang memilih posisi rekaman yang akan
diperbandingkan berikutnya sebagai tepat berada ditengah sisa berkas yang belum
diperiksa.
Pencarian interpolasi tidak mencari posisi TENGAH seperti halnya algoritma
pencarian biner, melainkan menentukan posisi berikutnya, dengan menggunakan
algoritma sebagai berikut :
Proc
pencarian_interpolasi
/* n buah
rekaman dalam berkas diurutkan menaik menurut kunci rekaman */
AWAL := 1
Akhir := n
while AWAL ≤ AKHIR do
BERIKUT :=
if kunci (cari) = kunci (berikut)
then pencarian berakhir.
else if kunci (cari) > kunci (berikut)
then AWAL := berikut + 1
else AKHIR := berikut – 1
End
Rekaman
tidak ditemukan
End
pencarian_biner
- Untuk rekaman dengan susunan sebagai berikut, berapa probe untuk menemukan rekaman dengan kunci 49 bila digunakan pencarian interpolasi.
1 2 3
4 5 6 7
8 9
[21 25 28 33 38
39 48 49 69]
21 25 28 33
38 39 [48 49 69]
Perhitungan
:
BERIKUT1 =
= 5,6666 ,
dibulatkan 6
Kcari :
Kberikut = 49 > 38 AWAL = BERIKUT1 + 1 = 6 + 1
= 7
|
BERIKUT2 = |
Pencarian Biner (Binary Search) pada array yang sudah terurut
Pencarian Biner (Binary Search)
dilakukan untuk :
♪ memperkecil
jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan
data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar
ukurannya.
♪ Prinsip dasarnya
adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai
data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada
kemungkinan data tidak ditemukan).
♪ Syarat utama
untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan
terurut menaik.
ALGORITMA
Kamus
Const
N : integer = 8 { misalkan jumlah elemen
array maksimum = 8 }
Type
A = array [ 1 ..... N ] of integer
Cari,
BatasAtas, BatasBawah, Tengah : Integer
Ketemu
: boolean
ALGORITMA
Input
(cari) { meminta nilai data yang akan dicari}
BatasAtas ¬ 1 { indeks array dimulai dari 1 }
BatasBawah ¬ N
Ketemu ¬ False
While
(BatasAtas < BatasBawah) and (not ketemu) do
Tengah
¬ (BatasAtas
+ BatasBawah) div 2
If
A [Tengah] = cari then
Ketemu ¬ true
Else
If ( A
[Tengah] < cari ) then { cari
di bagian kanan }
BatasAtas
¬ Tengah + 1
Else
BatasBawah
¬ Tengah – 1 {
cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output
( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif
Contoh Nilai-Nilai data
yang sudah terurut :
|
A
|
2
|
5
|
8
|
12
|
15
|
25
|
37
|
57
|
|
|
1
|
2
|
3
|
3
|
5
|
6
|
7
|
8
|
Kasus 1 : cari = 12
Loop
pertama : Tengah = (BatasAtas + BatasBawah) div
2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12, berarti loop
pertama data langsung ditemukan
Kasus 2 : cari = 15
Loop
pertama : Tengah = (BatasAtas + BatasBawah) div
2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 < cari = 15,
berarti BatasAtas = Tengah + 1 = 4 + 1 = 5
Loop
kedua : Tengah =
(BatasAtas + BatasBawah) div 2 = (5 +
8) div 2 = 6
A [Tengah] = A [6] = 25 > cari = 15,
berarti BatasBawah = Tengah - 1 = 6 - 1 = 5
Loop
ketiga : Tengah =
(BatasAtas + BatasBawah) div 2 = (5 +
5) div 2 = 5
A [Tengah] = A [5] = 15, berarti setelah loop ketiga, data ditemukan
Kasus 3 : cari = 10
Loop
pertama : Tengah = (BatasAtas + BatasBawah) div
2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 > cari = 10,
berarti BatasBawah = Tengah - 1 = 4 - 1 = 3
Loop
kedua : Tengah =
(BatasAtas + BatasBawah) div 2 = (1 +
3) div 2 = 2
A [Tengah] = A [2] = 5 < cari = 10,
berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop
ketiga : Tengah =
(BatasAtas + BatasBawah) div 2 = (3 +
3) div 2 = 3
A [Tengah] = A [3] = 8, berarti setelah loop ketiga, data tidak ditemukan
Untuk jumlah data
sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali.
Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak
3 kali.
Referensi
http://ebestmateri.blogspot.com/2010/12/modul-organisasi-berkas-langsung.html
