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.