Pertemuan 14

PENGENALAN KONTROL INPUT/OUTPUT

Assalamualaikum Warahmatullahi Wabarakatu.

Jumpa lagi dengan saya pada pertemuan hari ini, semoga kalian sehat selalu dan selalu berada pada lindungan ALLAH SWT. Aamiin Yaa Rabbal Alaamiin.

Apasih Control Input/Output itu ?????

Ok , Langsung saja kita ke pembahasan.
Pengaksesan (membaca dan menulis) data pada alat penyimpanan sekunder memerlukan banyak aktifitas pada programmer aplikasi. Pemrograman bahasa komputer memungkinkan programmer untuk menjabarkan teknik organisasi berkas yang agak kompleks (missal pada organisasi berkas indeks-sequential) dengan pernyataan bahasa yang sangat sederhana. Dukungan sistem manajemen berkas mengubah pernyataan-pernyataan tersebut menjadi instruksi input/output tingkat bawah (low-level). Demikian pula sebuah permintaan sederhana dari programmer terhadap READ atau WRITE sebuah record pada berkas, secara khusus diperlukan suatu urutan yang komplek dari peralatan dukungan operasi manajemen. Bagian-bagian ini biasanya tidak dapat dilihat oleh programmer. Pekerjaan programmer akan menjadi lebih sukar jika pekerjaan itu menyangkut operasi control input/output yang lebih terinci. Sebuah sistem control I/O bertujuan untuk memberikan bantuan kepada user untuk memungkinkan mereka mengakses berkas, tanpa memperhatikan detail dari karakteristik dan waktu penyimpanan.
Kontrol I/O menyangkut manajemen berkas dan peralatan manajemen yang merupakan bagian dari sistem operasi. Bagian lain dari sistem operasi mencakup sebuah pengaturan memori primer (main memory) dan sebuah pengatur proses dan penjadwalan. Kadang-kadang bagian dari sistem operasi yang melaksanakan control I/O ini disebut pengawas input/output (supervisor I/O). Akses berkas memerlukan dukungan manajemen berkas, yang memberikan teknik organisasi berkas dan dukungan alat manajemen, yang memberikan akses ke alat penyimpan fisik. Pada beberapa sistem operasi sebuah pengatur berkas (file manager) dan sebuah pengatur alat (device manager) berbeda satu sama lain, sedang pada sistem lain, mereka digabungkan untuk membentuk fungsi control I/O tunggal. Tugas dari sistem kontrol I/O sangat banyak dan beraneka ragam.
Beberapa tugas yang dikerjakan oleh kontrol I/O adalah sbb:
1. Memelihara direktori dari berkas dan lokasi informasi.
2. Menentukan jalan (pathway) bagi aliran data antara memori primer (main memory) dan alat penyimpan sekunder.
3. Mengkoordinasi komunikasi antara CPU dan alat penyimpanan sekunder, dan sebaliknya, termasuk:
a. Mengatur/menangani ketidakseimbangan kecepatan pengiriman data antara CPU dengan alat penyimpanan sedemikian rupa, sehingga CPU tidak menunggu terlalu lama (membuang waktu) untuk menyelesaikan pekerjaan I/O.
b. Mengatur data sedemikian rupa, sehingga data dapat disimpan, bila pengirim (CPU atau alat penyimpan sekunder) dan penerima (alat penyimpanan sekunder atau CPU) tidak siap pada waktu yang bersamaan.
4. Menyiapkan berkas penggunaan I/O.
5. Mengatur berkas, bila penggunaan input atau output telah selesai.
A. DIREKTORI BERKAS DAN KONTROL INFORMASI
Sebelum berkas dapat di akses oleh sebuah program, sistem operasi harus mengetahui pada alat penyimpanan sekunder yang mana berkas tersebut berada. Hampir semua sistem operasi menggunakan beberapa jenis struktur direktori yang digunakan untuk menyimpan trek dari berkas pada sistem manajemen berkas. Direktori yang diperlihatkan pada gambar dibwah ini adalah untuk satu unit dari penyimpanan sekunder. Labelnya berisi indentifikasi informasi, akses kontrol informasi, dan sebuah primer yang menunjuk ke isi tabel, yang berisi kontrol blok untuk setiap berkas pada unit tersebut.
Sebuah kontrol blok berisi informasi tentang nama dari berkas, atributnya (seperti panjang record, ukuran blok, organisasi berkas), dan batasnya pada media penyimpanan. Sebuah kontrol blok menunjukkan awal dari berkas yang bersangkutan. Jadi bila sebuah berkas dicari, isi tabel dari unit yang dimaksud, diperiksa untuk menemukan berkas pada alat penyimpan.

Sistem manajemen berkas yang berbeda, menggunakan struktur yang berbeda untuk blok kontrol berkasnya. Sebuah sistem representative/perwalian membentuk dua tabel untuk menjelaskan setiap berkas. Yang pertama, berisi informasi pada organisasi berkas dan pola pemrosesan, deskripsi ukuran dan jenis record, ukuran pemblokan, kesalahan hitung dan flag, informasi yang digunakan oleh rutin sistem kontrol I/O untuk menentukan status berkas dan posisinya, dan nama dari logika berkas (eksternal). Juga berisi sebuah pointer pada tabel deskriptif berkas kedua, yang dihubungkan dengan sebuah alat penyimpan tertentu dan berisi informasi tentang karakteristik fisik dan status alat yang sedang digunakan.
Alat pengontrol rutin menggunakan tabel ini untuk menetapkan (meng-interface) permintaan terhadap berkas dan untuk memonitor status aktifitas input/output berkas. Kontrol informasi pada sistem ini terpecah antar tabel dengan tujuan untuk memisahkan pendeskripsian berkas dan alat.
B. KONTROL PERALATAN
Aktivitas input/output terutama mencakup perpindahan data antara memori utama (main memori) dengan alat penyimpanan skunder atau alat input/output seperti printer, terminal, dan
card reader/punch. Pada kebanyakan sistem komputer, CPU tidak dibebani menangani tugas yang berhubungan dengan I/O. Tetapi, tanggung jawab untuk kontrol peralatan diserahkan pada prosesor I/O, yang dikenal sebagai saluran I/O. Saluran I/O itu sendiri merupakan prosesor yang sudah diprogram. Program-program yang di execute ini disebut channel program. Channel program ini menentukan operasi yang diperlukan untuk akses peralatan dan mengontrol jalur data (data pathway). Sistem operasi memberikan rutin standard yang digunakan untuk menjalankan saluran I/O.

C. MANAJEMEN SALURAN
Tujuan dari saluran I/O yang bertindak sebagai perantara antara CPU-memori utama dengan unit pengontrol penyimpan. CPU berkomunikasi dengan saluran melalui beberapa perintah yang sederhana. Beberapa saluran akan member perintah seperti:
• Test I/O, untuk menentukan apakah jalur (pathway) yang menuju peralatan sedang sibuk.
• Start I/O, pada peralatan tertentu.
• Halt I/O, pada peralatan tertentu.
Saluran biasanya berkomunikasi dengan CPU melalui cara interupsi. Interupsi akan terjadi jika keadaan error terdeteksi, misalnya interuksi CPU yang salah atau jika aktivitas I/O telah diakhiri. Jika interupsi terjadi, kontrol akan bercabang melalui rutin pengendali interupsi (interrupt-handler routine), dimana kontrol akan menentukan penyebab dari intertupsi, melakukan kegiatan yang tepat, kemudian mengembalikan kontrol pada pemanggil (caller). Jika sebuah program membutuhkan READ dari suatu berkas, maka serangkaian peristiwa pada gambar 3 ini akan terjadi.

• Program mengeluarkan sebuah READ, yang menginterupsi pengontrol I/O.
• Pengontrol I/O membuat sebuah saluran program pada memori utama.
• Saluran program dibaca dan dieksekusi oleh pemanggil saluran.
• Sinyal yang tepat akan ditransmisikan ke pemanggil unit kontrol.
• Sinyal ini diterjemahkan oleh unit kontrol dan digunakan untuk mengontrol peralatan operasi untuk membaca data yang diminta.
• Data yang diminta akan mengalir dari peralatan sepanjang jalur (pathway) ke daerah penampung berkas (file buffer area) dalam ruang memori utama.
• Interupsi yang dikeluarkan oleh saluran, digunakan untuk meneruskan sinyal pada waktu eksekusi program.
• Kontrol kembali ke program.
D. MANAJEMEN BUFFER
1. Single Buffering
Gambar dibawah ini menunjukkan struktur data dari buffer dalam bentuk yang sederhana, yang terdiri dari satu record perblok dan satu buffer per berkas, dimana buffer ini berfungsi mengisikan permintaan dari sebuah program. Struktur buffer ini berisi sebuah pointer pada alamat awal dan channel program untuk berkas yang sedang dioperasikan.

Struktur dasar dari channel program untuk mengisi buffer adalah:
Tunggu instruksi READ dari program
Memberitahukan instruksi start I/O ke kontrol unit Tunggu hingga buffer dikosongkan
Memberitahukan interupsi pada program sehingga dapat mulai membaca dari buffer.
• Double Buffering
Untuk mengurangi kemungkinan dari program menunggu, double buffering dapat digunakan. Dua dari tempat buffer yang ada, hanya satu yang ditetapkan untuk berkas. Ide dasar dari double buffering adalah jika consumer mengosongkan salah satu buffer, maka producer dapat mengisikan ke dalam buffer yang lain, pada saat buffer pertama sudah kosong, maka buffer yang kedua harus dalam keadaan penuh. Kemudian consumer dapat mengosongkan buffer kedua, pada saat producer mengisi buffer pertama, demikian seterusnya.
Struktur buffer untuk double buffering terdiri dari sebuah pointer yang menunjuk ke buffer berikutnya. Pada gambar di bawah ini. Adanya printer ini memungkinkan rutin producer dan consumer menjadi hal yang sangat umum.

Pertemuan 13

SORT DAN MERGE FILE

Assalamualaikum Warahmatullahi Wabarakatu.

Jumpa lagi dengan saya pada pertemuan hari ini, semoga kalian sehat selalu dan selalu berada pada lindungan ALLAH SWT. Aamiin Yaa Rabbal Alaamiin.

Apasih sort and merge file itu ?????

Ok , Langsung saja kita ke pembahasan.

Dalam sistem penyortiran dikenal 2 motode, yaitu:

1. Metode Sort Internal

Semua record yang akan diproses dimuat kedalam memori komputer lalu diproses sort (sortir)

2. Metode Sort Eksternal

Record-record diproses tidak semuanya dapat dimuat ke dalam memori komputer, karena keterbatasan memori komputer

Contoh: Sebuah file berisi 2000 record harus disortir ke dalam memori yang hanya dapat menampung 5000 record sekaligus. Untuk itu digunakan metode sort eksternal. Langkah-langkah penyortiran ini adalah:

1. Record-record dibagi ke dalam beberapa file agar dapat ditampung sekaligus di memori komputer, lalu masing-masing bagian di sortir internal. Bagian-bagian file yang telah tersortir ini disebut sorted sublist. Maka didapat:

1. Sorted sublist 1 (record 1-1000) dan

• Sorted sublist 2 (record 1001-2000)

• Setelah itu kedua sorted sublist ini (RUN) digabung (merge), sehingga didapat berkas gabungan (merge file) yang record-recordnya telah disortir.

• Kita simpulkan langkah-langkah metode sort eksternal ini adalah:

• Internal sort, dimana file dibagi menjadi beberapa bagian file kemudian di sortir.

• 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.

• Output, dimana menyalin file gabungan yang telah disortir kemudian storage terakhir.

Faktor-faktor yang mempengaruhi motode sort eksternal:

• Jumlah record yang akan disortir

• Ukuran record (panjang record)

• Jumlah storage yang digunakan

• Kapasitas internal memori

• Distribusi nilai key dalam input file

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

• Metode sort internal yang digunakan

• Jumlah main memori yang digunakan untuk sort internal

• Distribusi dari sorted sublist di secondary storge menjadi satu atau lebih file gabungan dalam satu langkah gabungan (merge pass)

1. NATURAL MERGE

Merge yang menangani dua input file sekaligus disebut dua way natural merge, merge yang menangani M input file sekaligus disebut M way natural merge. M menunjuk derajat merge. M way natural merge dapat didefinisikan sebagai merge dengan M input file dan hanya satu output file. Contoh, sebuah file yang terdiri dari 6000 record hendak disortir ke dalam memori komputer yang kapasitasnya 1000 record. Pada contoh ini, sebagai eksternal storage digunakan tiga tape. Tape satu berisi tiga sorted sublist yaitu record 1-1000, record 2001-3000 dan record 4001-5000. Sedangkan tape 2 berisi tiga sorted sublist yang terdiri dari record 1001-2000, record 3001-4000 dan record 5001-6000. Dengan 2 way natural merge, dimana dua input file sekaligus digabung menjadi sebuah output file di tape tiga.

Langkah selanjutnya, 1 dari 3 file digabung (record 1 – 2000) pada tape 3 ini disalin ke tape 1. Pengerjaan seterusnya dapat dilihat pada gambar dibawah ini. Hasil akhirnya adalah sebuah file gabungan berisi 6000 record yang telah terseortir di tape 3.

2 way merge. Diasumsikan 2 input file dan 1 output file

1. Pengurutan terdistribusi terhadap 2 file (bisa diselesaikan dalam konjungsi dengan tahap pengurutan internal.

• Tahap Penggabungan/Merge 1

• Salah satu dari 3 hasil penggabungan sementara pada file 3 dipindah ke file 1

• Tahap penggabungan kedua

B. BALANCED MERGE

Keperluan penggunaan tape pada natural merge dapat dikurangi dengan menggunakan balanced merge. Pada balanced merge, tidak ada lagi langkah pendistribusian hasil merge ke dalam beberapa tape. Berlainan dengan natural merge, balanced merge pada awalnya ada keseimbangan antara input file dan output file, walaupun pada akhirnya tidak ada lagi keseimbangan antara input dan output file. Seperti halnya natural merge, balance merge juga ada beberapa cara yaitu 2 way balance merge, 3 way balance merge, dan M way balance merge. 2 way balance merge berarti merge dengan 2 input file sekaligus dan hasilnya 2 output file. M way balance merge berarti M input file dengan M output file

2 way merge. Diasumsikan 2 input file dan 1 output file

1. Pengurutan terdistribusi terhadap 2 file (bisa diselesaikan dalam konjungsi dengan tahap pengurutan internal.

• Tahap Penggabungan/Merge 1

3.

• Salah satu dari 3 hasil penggabungan sementara pada file 3 dipindah ke file 1

• Tahap penggabungan kedua

C. POLYPHASE MERGE

Kita telah lihat bahwa M way balance merge menggunakan 2 M file (M input file dan M output file). Karena yang digunakan setiap saat hanya M file sebagai input dan direkam ke sebuah file maka ada M-1 file yang nganggur (idle). Untuk itulah perbaikan dari kelemahan ini diambil oleh poplyphase merge. Pada M way polyphase merge digunakan 2M-1 input file dengan 1 output file sekaligus.

D. CASCADE MERGE

Jenis lain dari unbalanced merge yang berusaha mengurangi penyalinan dan pembacaan record-record disebut cascade merge. Cascade merge dengan derajat M menggunakan input file 2M-1, kemudian 2M-2 dan 2M-3, …, 2 input file selama tiap tahap merge. 3 way cascade menggunakan 3 dan 2 input file selama tiap tahap merge.

Pengurutan Rekaman

Assalamualaikum Warahmatullahi Wabarakatu.

Jumpa lagi dengan saya pada pertemuan hari ini, semoga kalian sehat selalu dan selalu berada pada lindungan ALLAH SWT. Aamiin Yaa Rabbal Alaamiin.

Apasih Pengurutan Rekaman itu ?????

Ok , Langsung saja kita ke pembahasan.

• Pengukuran data merupakan komponen dasar dari struktur data, misalnya pencarian biner, pencarian interpolasi
• pengurutan data juga di manfaatkan untuk mengeliminasi rekaman rekaman yang ganda
• pengurutan rekaman yang kami bahas
• 1. pengurutan gelembung
• 2. pengurutan dengan penyisipan
• 3. pengurutan dengan cepat

PENGURUTAN GELEMBUNG

di beri nama bubble karena proses pengurutan karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat.

satu karakter dari pengurutan ini adalah bahwa pengurutan gelembung ini sangat mudah untuk dipahami dan diprogramkan.

Salah satu karakter dari pengurutan ini adalah bahwa pengurutan gelembung ini sangat mudah untuk dipahami dan diprogramkan.

Pengurutan data Bubble Sort dilakukan dengan cara membandingkan elemen sekarang dengan elemen berikutnya

Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.

Pengurutan Ascending (urut naik) Yaitu: Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar Pengurutan Descending ( urut turun) Yaitu: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar

Pada putaran pertama dilakukan pembandingan sebagai berikut:

x[1] dengan x[2] (15 dengan 31) tidak ada pertukaran

x[2] dengan x[3] (31 dengan 28) pertukaran

x[3] dengan x[4] (31 dengan 43) tidak ada pertukaran

x[4] dengan x[5] (43 dengan 65) tidak ada pertukaran

x[5] dengan x[6] (65 dengan 35) pertukaran

x[6] dengan x[7] (65 dengan 78) tidak ada pertukaran

x[7] dengan x[8] (78 dengan 20) pertukaran

x[8] dengan x[9] (78 dengan 19) pertukarn

Perhatikan contoh berikut: x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] x[9] 15 31 28 43 65 35 78 20 19

Putaran 1 15 31 28 43 65 35 78 20 19 15 31 28 43 65 35 78 20 19 15 28 31 43 65 35 78 20 19 15 28 31 43 65 35 78 20 19 15 28 31 43 65 35 78 20 19 15 28 31 43 35 65 78 20 19 15 28 31 43 35 65 78 20 19 15 28 31 43 35 65 20 78 19 15 28 31 43 35 65 20 19 78 Perhatikan bahwa rekaman tertinggi yaitu dengan kunci 78 sudah berada pada posisi yang tepat.

Sesudah putaran ke-dua, berkas akan mempunyai bentuk: 15 28 31 35 43 20 19 65 78 Perhatikan bahwa rekaman kedua tertinggi yaitu dengan kunci 65 sudah berada pada posisi yang tepat. Karena setiap 1 putaran menempatkan satu elemen baru kedalam posisi yang tepat, maka sebuah berkas dengan n rekaman membutuhkan tidak lebih dari n-1 putaran untuk menghasilkan berkas yang urut. Putaran ke-tiga dan seterusnya adalah sebagai berikut: 15 28 31 35 20 19 43 65 78 15 28 31 20 19 35 43 65 78 15 28 20 19 31 35 43 65 78 15 20 19 28 31 35 43 65 78 15 19 20 28 31 35 43 65 78

Pengurutan dengan Penyisipan Jika rekaman-rekaman dalam sebuah berkas akan diurutkan, cara yang mudah untuk melakukannya adalah dengan menyisipkan rekaman demi rekaman dalam berkas pada tempat yang sesuai dalam daftar yang urut yang terbentuk oleh rekaman-rekaman yang mendahuluinya. Kunci rekaman yang berada sesudah rekaman yang diproses dibandingkan dengan rekaman yang berada tepat disebelah kiri rekaman, jika lebih kecil, maka kedua rekaman ditukar posisinya. Kunci rekaman yang baru saja ditukar, kini mendapat giliran untuk dibandingkan dengan rekaman yang berada tepat disebelah kirinya.

Penyelesaian Langkah pertama adalah mengidentifikasi rekaman dalam berkas yang memiliki kunci terkecil (dalam soal ini adalah 15 yang ada pada posisi 3), kemudian tukar posisinya dengan rekaman pertama dalam berkas . Maka susunan rekaman akan menjadi sebagai berikut: 15 31 28 43 65 35 78 20 19 ^ Simbol ^ menunjukkan lokasi rekaman yang akan disisipkan kembali ke dalam berkas dan menunjukkan lokasi anggota kiri pasangan rekaman yang ditukar posisinya.Rekaman kemudian diurukan sebagai berikut: Untuk berkas dengan kunci rekaman sebagai berikut: 28 31 15 43 65 35 78 20 19

1 2 3 4 5 6 7 8 9 15 28 31 43 65 35 78 20 19 ^ 15 28 31 43 65 35 78 20 19 ^ 15 28 31 43 65 35 78 20 19 ^ 15 28 31 43 65 35 78 20 19 ^ 15 28 31 43 35 65 78 20 19 ^ 15 28 31 35 43 65 78 20 19 ^ 15 28 31 35 43 65 78 20 19 ^ 15 28 31 35 43 65 78 20 19 ^ 15 28 31 43 65 35 20 78 19 ^ 15 28 31 35 43 20 65 78 19 ^

15 28 31 35 20 43 65 78 19 ^ 15 28 31 20 35 43 65 78 19 ^ 15 28 20 31 35 43 65 78 19 ^ 15 20 28 31 35 43 65 78 19 ^ 15 20 28 31 35 43 65 78 19 ^ 15 20 28 31 35 43 65 19 78 ^ 15 20 28 31 35 43 19 65 78 ^ 15 20 28 31 35 19 43 65 78 ^ 15 20 28 31 19 35 43 65 78 ^ 15 20 28 19 31 35 43 65 78 ^ 15 20 19 28 31 35 43 65 78 ^ 15 19 20 28 31 35 43 65 78 ^

Pengurutan dengan Cepat

Memproses berkas dengan membagi rekaman-rekaman menjadi beberapa kelompok kemudian mengurutkannya.

Bila sebuah kelompok hanya berisi satu item maka proses pengurutan kelompok tersebut dihentikan.

Bila proses pengurutan untuk semua kelompok sudah selesai, maka keseluruhan rekaman dalam berkas sudah dalam keadaan urut.

Prosedur quick sort melakukan pengurutan berkas dengan mengelompokkan rekaman-rekaman menjadi beberapa kelompok berdasar hasil perbandingan terhadap anggota berkas tertentu. Proses tersebut diulang sampai semua kelompok sudah dalam keadaan urut. Berkas / kelompok dibagi berdasar pada perbandingan dengan rekaman pertama dari berkas/kelompok. Semua rekaman dengan kunci lebih kecil dari kunci pada rekaman pertama di letakkan di sebelah kiri rekaman pembanding. Semudian rekaman dengan kunci yang lebih besar di letakkan pada bagian sebelah kanan rekaman pembanding.

Pengurutan: 1 2 3 4 5 6 7 8 9 Rekaman pertama (dengan kunci 28) di bandingkan dengan :

Rekaman ke-dua (dengan kunci 31) lebih besar rekaman ke-dua dialokasikan disebelah kanan pembanding.

Rekaman ke-tiga (dengan kunci 15) lebih kecil rekaman ke-tiga dialokasikan disebelah kiri pembanding.

Rekaman ke-empat (dengan kunci 43) lebih besar rekaman ke- empat dialokasikan disebelah kanan pembanding

Rekaman ke-lima (dengan kunci 65) lebih besar rekaman ke- lima dialokasikakan disebelah kanan perbanding Contoh untuk rekaman-rekaman yang akan diurutkan (berkas asli) sbb: 28 31 15 43 65 35 78 20 19

Rekaman ke-enam (dengan kunci 35) lebih besar rekaman ke-enam dialokasikan disebelah kanan pembanding

Rekaman ke-tujuh (dengan kunci 78) lebih besar rekaman ke-tujuh dialokasikan disebelah kanan pembanding

Rekaman ke-delapan (dengan kunci 20) lebih besar rekaman ke-delapan dialokasikan disebelah kiri pembanding

Rekaman ke-sembilan (dengan kunci 19) lebih besar rekaman ke-sembilan dialokasikan disebelah kiri pembanding

Sekarang berkas asli akan memiliki bentuk sebagai berikut : 1 2 3 <28 >28 Berkas terbagi menjadi 3 subbagian masing-masing beranggotakan 15, 20, dan 19 sebagai subbagian pertama (semuanya < 28), subbagian 2 dengan satu anggota yaitu 28 (juga pembanding) dan subbagian ke 3 beranggotakan 31, 43, 65, 35 dan 78 (semuanya > 28 15 20 19 28 31 43 65 35 78

Dengan cara yang sama pembanding dilakukan terhadap semua subbagian dengan rekaman pertama (kunci 15) subbagian pertama sebagai pembanding, dan rekaman pertama (kunci 31) subbagian ketiga sebagai pembanding. Subbagian 2 sudah urut. 1 11 12 13 15 20 19 15 19 20 11 12 13 1 3 31 43 65 35 78 >28 3.2 3.2.1 3.2.2 43 65 35 7 8 >43

 3 3.1 3.2 3.1 43 65 35 78 >31 3 3.2.2.1 3.2.2.2 3.2.2.3 35 65 78 <65 >65 Gambar 7-3 Hasil proses pengurutan cepat 1.1 1.2 1.3 2 3.1 3.2.2.1 3.2.1 3.2.2.2 3.2.2.3 15 19 20 28 31 35 43 65 78 Bentuk berkas sesudah pengurutan adalah sebagi berikut :

• Pengurutan data merupakan komponen dasar struktur data

                Misal  : Pencarian biner, Pencarian interpolasi

• Pengurutan data juga dimanfaatkan untuk mengeliminasi rekaman-rekaman yang ganda.
• Pengurutan rekaman yang akan di bahas :

1. Pengurutan gelembung

• Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat.
• Salah satu karakter dari pengurutan ini adalah bahwa pengurutan gelembung ini sangat mudah untuk dipahami dan diprogramkan.
• Pengurutan data Bubble Sort dilakukan dengan cara membandingkan elemen sekarang dengan elemen berikutnya
• Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1.

Pengurutan Ascending (urut naik)Yaitu: Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukarPengurutan Descending ( urut turun)Yaitu: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar

2. Pengurutan dengan penyisipan                Jika rekaman-rekaman dalam sebuah berkas akan diurutkan, cara yang mudah untuk melakukannya adalah dengan menyisipkan rekaman demi rekaman dalam berkas pada tempat yang sesuai dalam daftar yang urut yang terbentuk oleh rekaman-rekaman yang mendahuluinya.                                Kunci rekaman yang berada sesudah rekaman yang diproses dibandingkan dengan rekaman yang berada tepat disebelah kiri rekaman, jika lebih kecil, maka kedua rekaman ditukar posisinya. Kunci rekaman yang baru saja ditukar, kini mendapat giliran untuk dibandingkan dengan rekaman yang berada tepat disebelah kirinya.
3. Pengurutan dengan cepat

• Memproses berkas dengan membagi rekaman-rekaman menjadi beberapa kelompok kemudian mengurutkannya.
• Bila sebuah kelompok hanya berisi satu item maka proses pengurutan kelompok tersebut dihentikan.
• Bila proses pengurutan untuk semua kelompok sudah selesai, maka keseluruhan rekaman dalam berkas sudah dalam keadaan urut.

Ď                Prosedur quick sort melakukan pengurutan berkas dengan mengelompokkan rekaman-rekaman menjadi beberapa kelompok berdasar hasil perbandingan terhadap anggota berkas tertentu. Proses tersebut diulang sampai semua kelompok sudah dalam keadaan urut.                Berkas / kelompok dibagi berdasar pada perbandingan dengan rekaman pertama dari berkas/kelompok. Semua rekaman dengan kunci lebih kecil dari kunci pada rekaman pertama di letakkan di sebelah kiri rekaman pembanding. Semudian rekaman dengan kunci yang lebih besar di letakkan pada bagian sebelah kanan rekaman pembanding.

                                  MANAJEMEN KOLISI

Assalamualaikum Warahmatullahi Wabarakatu.

Jumpa lagi dengan saya pada pertemuan hari ini, semoga kalian sehat selalu dan selalu berada pada lindungan ALLAH SWT. Aamiin Yaa Rabbal Alaamiin.

Apasih manajemen kolisi itu ?????

Ok , Langsung saja kita ke pembahasan.

Salah satu alasan di aplikasikannya fungsi hash adalah akan mendistribusikan kunci seperangkat data yang lebih merata. Kalau tujuan tersebut tidak tercapai, maka salah satu cara yang dipakai adalah mengkombinasikan beberapa fungsi sederhana dalam satu aplikasi. Terkadang dalam fungsi hash dapat menghasilkan kolisis atau sinonim. Makin sedikit jumlah kolisi makin baik pula fungsi hashing tersebut. 

Penyelesaian yang dapat dilakukan adalah memberikan penunjuk pada lokasi rekaman sinonim. Bila terjadi sinonim jamak pada satu home address tertentu maka akan dibentuk rantai rekaman sinonim.

Sebagai contoh : R1, R2 dan R3 sinonim dengan home addres  r menunjuk pada lokasi s dimana tersimpan sinonim pertama yaitu R2  Simbul ^ menunjuk nol pada penghubung t  menunjukan akhir dari rantai sinonim.

Kriteria Fungsi Hash Yang Baik 

• Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision (tabrakan). 
• Dapat dieksekusi secara efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja.

Collision (Tabrakan)

• Dengan menggunakan metode hashing, maka secara otomatis hubungan korespondensi satu-satu antara kunci rekaman dengan alamat rekaman menjadi hilang.
• Selalu ada kemungkinan terjadinya peristiwa dimana terdapat dua buah kunci yang berbeda namun memiliki home address yang sama.
• Kejadian seperti ini dinamakan Collision atau Tabrakan atau Tumbukan.

Manajemen Kolisi

• Semakin sedikit jumlah kolisi, maka makin baik bagi fungsi hashing tersebut, karena makin sedikit jumlah waktu yang diperlukan untuk melihat tempat yang berbeda dalam menemukan rekaman yang diinginkan. 
• Beberapa cara untuk mengantisipasi kolisi adalah dengan mengganti fungsi hashing, atau mengkombinasikan faktor packing.
• Faktor packing suatu berkas adalah perbandingan (rasio) antara jumlah rekaman yang disimpan dalam berkas dengan kapasitas berkas, atau dapat dinyatakan sbb :

Resolusi Kolisi

• Yang menjadi tujuan utama metode resolusi adalah menempatkan rekaman synonim pada suatu lokasi yang membutuhkan probe tambahan yang minimum pada home address rekaman tersebut , Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama
• Salah satu penyelesaian yang dapat dilakukan adalah dengan memberikan petunjuk pada lokasi rekaman sinonim
• Karena collision dapat di pastikan akan selalu terjadi, maka dapat dikatan bahwa output dari fungsi hash (home-address) bukanlah merupakan alat yang unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati
• Jika home-addrees dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus di carikan alamat lain untuk ditempati oleh rekaman tersebut 
• Proses pencarian alamat lain ini dinamakan sebagai Collision Resolution
• Berikut beberapa Metode Untuk Mengatasi Kolisi / Tubrukan => ;

Beberapa Metode Untuk Mengatasi Koisi

1. Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong, salah satu nya dengan cara Linier Probing
•  Linier Probing Pencarian dilakukan dengan jararak pencarian yang fix (tetap), biasanya satu-satu
• Linier Probing Contoh : Sesuai dengan namanya jika lokasi yang telah ditempati telah terisi, maka dilihat lokasi selanjutnya apakah masih belum terisi
• Fungsi Hash yang dipakai adalah : f(key) = key mod 10
• Ruang alamat yang tersedia : 10 alamat
• Metode collision resolution yang dipakai adalah open addressing dengan linier probing jarak 3 Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15

2. Metode Coalesced Hashing 

• Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
• Contoh : misalkan akan dilakukan penyisipan rekamanrekaman dengan kunci 38, 51, 40, 61, 83, 24, dan 60
• Langkah 1 lakukan proses hashing semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka dihasilkan :