PENGURUTAN REKAMAN

Metode sorting yang sering digunakan adalah:

1. Pengurutan gelembung (Bubble sort)
2. Pengurutan cepat (Quick sort)
3. Pengurutan heap (Heap sort)

A. PENGURUTAN GELEMBUNG (BUBBLE SORT)

Salah satu prosedur pengurutan paling sederhana adalah pengurutan gelembung. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat meggelembung ke posisi yang tepat. Salah satu karakter dari pengurutan ini adalah sangat mudah untuk dipahami dan diprogramkan. Akan tetapi dari semua prosedur pengurutan yang akan dibahas, prosedur pengurutan gelembung merupakan prosedur yang paling tidak efisien. Pada pembahasan berikut, x merupakan suatu array interger di mana n rekaman pertamanya akan diurutkan sehingga x [i] ≤ x [j] untuk 1 ≤ i ≤ n. Gagasan dasar pengurutan gelembung adalah langkah-langkah melewatkan satu rekaman melalui rekaman-rekaman lain di dalam berkas. Masing-masing langkah mengandung proses untuk membandingkan rekaman pendahulunya, atau x [i] dengan x [i-1] dan mempertukarkan kedua rekaman bila urutan mereka tidak tepat.

Perhatikan bahwa rekaman tertinggi yaitu dengan kunci 78 sudah berada pada posisi yang tepat. Pada umumnya diperlukan sebanyak i putaran agar x[n-i+1] sampai pada posisi yang tepat

Perhatikan bahwa rekaman kedua tertinggi yaitu dengan kunci 65 sudah berada pada posisi yang tepat. Karena setiap satu putaran menempatkan satu elemen baru ke dalam posisi yang tepat, maka sebuah berkas dengan n rekaman membutuhkan tidak lebih dari n-1 putaran untuk menghasilkan berkas yang urut.

B. PENGURUTAN CEPAT (QUICK SORT)

Pengurutan 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. Pengurutan cepat mengurutkan rekaman dalam berkas dengan membuat partisi antar rekaman menjadi beberapa kelompok berdasar hasil perbandingan terhadap anggota berkas tertentu. Proses tersebut diulang sampai semua kelompok sudah dalam keadaan urut. Berkas (atau kelompok) dibagi berdasarkan perbandingan dengan rekaman pertama dari berkas. Semua rekaman dengan kunci lebih kecil dari kunci pada rekaman pertama diletakkan disebelah kiri rekaman pembanding, sedangkan rekaman dengan kunci yang lebih besar diletakkan pada bagian sebelah kanan rekaman pembanding.

Algoritma pengurutan cepat adalah sebagai berikut:

1. Jika terdapat banyak rekaman yang harus diurutkan, pisahkan rekaman-rekaman tersebut dalam tiga kelompok (yaitu rekaman-rekaman dengan kunci rekaman lebih besar dari kunci rekaman pertama) dengan menggunakan prosedur ‚pertukaran_cepat‛, yaitu :
2. Urutkan cepat rekaman-rekaman data yang berada dalam kelompok pertama menjadi tiga kelompok
3. Urutkan cepat rekaman-rekaman data yang berada dalam kelompok ketiga menjadi tiga kelompok
4. Jika tidak, maka proses berakhir

C. PENGURUTAN HEAP (HEAP SORT)

Pengurutan heap merupakan algoritma yang menarik karena sangat sederhana. Nama heap diambil dari struktur data yang mendasari pengurutan tersebut, yaitu struktur heap. Pengurutan heap memanfaatkan keunggulan sifat-sifat yang dimiliki oleh pohon biner lengkap, yaitu: Heap biner atau heap, merupakan pohon biner lengkap dengan kunci yang disimpan dalam masing-masing titik memiliki nilai lebih kecil atau sama dengan nilai kunci dari masing-masing anaknya. Definisi tersebut memberikan indikasi bahwa akar akan berisi rekaman dengan kunci tertinggi.