Pengenalan Pengurutan Data (Sorting)
Pengurutan data (ada juga yang menyebutnya sebagai pemilihan data) secara umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Secara umum ada dua jenis pengurutan data, yaitu pengurutan data secara urut naik (Ascending) yaitu dari data yang nilainya paling kecil sampai data yang nilainya paling besar, atau pengurutan data secara urut turun (Descending), yaitu dari data yang mempunyai nilai paling besar sampai paling kecil. Dalam hal pengurutan data yang bertipe string atau char, nilai data dikatakan lebih kecil atau lebih besar dari yang lain didasarkan pada urutan relatif (Collating Sequence) seperti yang telah dinyatakan dalam tabel ASCII.
Keuntungan yang diperoleh dari data yang sudah dalam keadaan terurut adalah bahwa data mudah dicari (misalnya dalam buku telepon atau kamus bahasa), mudah untuk dibetulkan, dihapus, disisip, atau digabungkan, dan mudah mencek apakah ada data yang hilang (misalnya dalam tumpukan kartu bridge). Algoritma sangat ditentukan oleh struktur data yang digunakan, maka sejumlah algoritma pengurutan yang dijelaskan bisa diklasifikasikan menjadi dua kategori, yaitu pengurutan larik (Array), dan pengurutan berkas masup urut (Sequential Acces File). (Insap Santoso, 1992 : 322).
Kategori yang pertama disebut sebagai pengurutan secara internal, dan kategori kedua disebut dengan pengurutan eksternal. Dikatakan demikian karena larik tersimpan dalam memori utama komputer yang mempunyai kecepatan tinggi, sedangkan berkas biasanya tersimpan dalam pengingat luar (tambahan), misalnya cakram, atau pita magnetis.
Contoh sederhana untuk membedakan dua kategori ini adalah pengurutan sejumlah kartu yang telah diberi nomor. Penyusunan kartu sebagai larik, misalkan semua kartu terletak dihadapan pemakai sehingga semua terlihat dengan jelas nomornya, dan kartu bisa dimasup sendiri-sendiri.
Penyusunan kartu sebagai sebuah berkas, agak berbeda yakni semua kartu harus ditumpukkan sehingga hanya satu kartu bagian atas saja yang bisa dilihat nomornya. Batasan ini akan membawa konsekuensi yang serius dalam pemilihan metode yang akan dibangun, tetapi mungkin tidak dapat dihindarkan karena jumlah kartu cukup banyak sehingga meja tidak cukup luas untuk meletakkan seluruh kartu di atasnya (Insap Santoso, 1992 : 322).
Larik (Array)
Larik (Array) adalah tipe terstruktur yang mempunyai komponen dalam jumlah yang tepat dan setiap komponen mempunyai tipe data yang sama. Posisi masing-masing komponen dalam larik dinyatakan sebagai nomor index.
Bentuk umum dari deklarasi larik adalah :
Tipe pengenal = array [tipe_index] of tipe;
Dalam pengurutan larik, yang disimpan dalam pengingat komputer, ada aspek yang ekonomis yang perlu dipertimbangkan. Aspek ini antara lain menyangkut kapasitas pengingat yang tersedia. Apsek lain adalah dalam hal waktu, yakni waktu yang diperlukan untuk melakukan permutasi sehingga semua elemen akhirnya menjadi terurut.
Ukuran efisiensi yang baik bisa diperoleh dari banyaknya perbandingan atau perpindahan yang harus dilakukan. Algoritma yang baik memerlukan perbandingan sebanyak N log N kali. Meskipun demikian dapat dilihat beberapa metode yang disebut dengan metode langsung (straight method), yang seluruhnya memerlukan N2 pembanding. Metode langsung ini bisa dikelompokkan menjadi tiga metode, yaitu penyisipan (insertion), seleksi (selection), dan penukaran (exchange). Sebelum melihat masing-masing metode terlebih dahulu melihat deklarasi larik yang akan digunakan. Dalam hal ini akan menggunakan larik dimensi satu (vektor) yang elemennya bertipe real.
Deklarasinya adalah :
Const N = 100;
Tipe larik = array [1..N] of real;
Dalam deklarasi di atas, N adalah banyaknya elemen vektor dan bisa dirubah nilai konstanta N sesuai kebutuhan.
Selain deklarasi di atas, berikut disajikan satu prosedur sederhana untuk menukar nilai dua buah elemen. Dalam prosedur ini, nilai elemen yang akan saling dipertukarkan antara perubah A dan B yang masing-masing bertipe real. (Insap Santoso, 1992 : 323).
Procedure TUKARKAN (var A, B : real );
VarT : real;
Begin
T := A;
A := B;
B := T;
End;
Prosedure TUKARKAN di atas akan digunakan oleh bebrapa prosedur yang akan dibahas. Selain itu, metode-metode pengurutan masing-masing akan diimplementasikan dalam sebuah prosedur.
Record
Dengan tipe record, dapat dikumpulkan beberapa item data yang masing-masing data mempunya tipe data yang berbeda-beda. Masing-masing item data disebut dengan field. Jadi record terdiri dari kumpulan field yang dapat berbeda tipe. Misalnya record pegawai terdiri dari NIM, NAMA, ALAMAT, STATUS.
Cara mendeklarasikan record diawali dengan kata cadangan record dan diikuti oleh suatu daftar field dan diakhiri dengan kata cadangan End.
Type
Lgn = record
Kode : string;
Nama : string;
Alamat : srting;
Piutang: string;
End;
Var
Mahasiswa : mhs;
Deklarasi variabel tipe data record dapat juga dilakukan langsung di bagian deklarasi variabel sebagai berikut :
Var
Langganan : record;
Kode : string;
Nama : string;
Alamat : string;
Piutang: string;
End;
Tiap-tiap komponen field dari record dapat dipergunakan dengan cara menuliskan :
Pengenal-record.pengenal-field[pengenal-field]
Tipe data yang telah dideklarasikan di atas dapat diruaikan sebagi berikut :
Pengenalrecord : langganan
Pengenalfield : kode, nama, alamat, piutang;
Metode Seleksi
Cara kerja metode seleksi didasarkan pada pencarian elemen dengan nilai terkecil, kemudian dilakukan penukaran dengan elemen ke I. secara singkat, metode ini bisa dijelaskan sebagai berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai data terakhir. Kemudian data terkecil tersebut ditukarkan dengan data yang paling kecil dibanding data yang lain. Pada langkah kedua, data terkecil dicari mulai data kedua sampai data terakhir. Data terkecil yang diperoleh ditukar dengan data kedua (Insap Santoso, 1992 : 322).
Metode ini secara garis besar merupakan kebalikan dari metode penyisipan langsung. Dalam setiap langkah pada metode penyisipan hanya memperhatikan satu elemen dari sumber dan semua elemen dari larik tujuan untuk menentukan posisinya yang tepat, sehingga sering disebut dengan one source-multiple destination. Dalam metode seleksi terjadi sebaliknya, yakni memperhatikan semua elemen dalam larik sunber untuk menentukan elemen terkecil yang akan ditempatkan pada tujuan, sehingga sering disebut dengan multiple sources-one destination. Dalam metode ini banyak perbandingan (untuk mencari elemen dengan nilai terkecil). Banyaknya pembanding adalah :
C = (N2 – N ) / 2
Metode ShellSort
Metode yang akan dijelaskan di bawah ini disebut dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donal L. Shell pada tahun 1959, sehingga sering disebut dengan Metode ShellSort. Seperti metode-metode terdahulu, metode ini juga memanfaatkan penukaran sepasang elemen untuk mencapai keadaan terurut. Dalam hal ini jarak dua elemen yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut (Insap Santoso, 1992 : 334).
Pada langkah pertama, ambil elemen pertama dan bandingkan dengan jarak yang sama seperti di atas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses di atas diulang tetapi dengan jarak yang lebih kecil. Pada langkah ketiga jarak tersebut diperkecil lagi. Seluruh proses dihentikan setelah memproses untuk jarak sama dengan 1. untuk mempermudah pemrogramannya, pertama kali jarak diambil separoh banyaknya elemen yang akan diurutkan.
Metode QuickSort
Metode QuickSort juga sering disebut dengan metode patition exchange sort. Metode ini diperkenalkan oleh C.A.R Hoare. Untuk mempertinggi efektifitasnya, dalam metode ini jarak kedua elemen yang akan ditukarkan nilainya ditentukan cukup besar.
Misalkan N elemen dalam keadaan urut turun. Untuk mengurutkan N elemen tersebut dengan N/2 kali, yakni dengan pertama kali menukarkan elemen paling kiri dengan paling kanan, kemudian secara bertahap menuju ke elemen yang ada ditengah. Tetapi hal ini hanya bisa dilakukan jika tahu pasti bahwa urutannya adalah urut turun (Insap Santoso, 1992 : 337).
Secara garis besar metode ini dijelaskan sebagai berikut. Misalkan ingin mengurutkan vektor A yang mempunyai N elemen. Pilih sembarang elemen dari vektor tersebut, biasanya elemen pertama, misalnya 10. Kemudian semua elemen tersebut disusun dengan menempatkan 10pada posisi J sedemikian rupa sehingga elemen ke I sampai ke J – 1 mempunyai nilai lebih kecil dari 10dan elemen ke J + 1 sampai ke N mempunyai nilai lebih besar dari 10. Dengan demikian ada dua buah subvektor, subvektor pertama nilai elemennya lebih kecil dari 10, subvektor kedua nilai elemennya lebih besar dari 10.
Pada langkah berikutnya, proses di atas diulang pada kedua subvektor, sehingga akan mempunyai empat subvektor. Proses di atas diulang pada setiap subvektor sehingga seluruh vektor semua elemennya menjadi terurutkan.
Diambil elemen pertama, yaitu 23. Elemen ini akan diletakkan pada suatu posisi sehingga akan membagi vektor di atas menjadi dua subvektor, dengan vektor pertama (subvektor kiri) nilai elemennya selalu lebih kecil dari 23, dan subvektor kedua (subvektor kanan) nilainya selalu lebih besar dari 23.
Kemudian pada kedua subvektor tersebut proses seperti di atas sampai seluruh vektor dalam keadaan terurutkan.
Dari ilustrasi di atas bisa dilihat bahwa metode QuickSort bisa diimplementasikan menggunakan dua cara . Cara pertama adalah dengan cara non rekursif dan cara kedua adalah rekursif. Pada kedua cara implementasi di atas, persoalan utama yang perlu diperhatikan adalah bagaimana meletakkan suatu elemen pada posisinya yang tepat sehingga memenuhi ketentuan di atas dan bagaimana menyimpan batas-batas subvektor pada saat vektor dibagi menjadi 2 subvektor, kemudian menjadi 4 subvektor, 8 subvektor dan seterusnya.