Pengurutan Data - Struktur Data
Pengurutan data (sorting) secara umum bisa didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu.
Tujuan pengurutan data adalah untuk lebih mempermudah pencarian data.
Secara umum ada dua jenis pengurutan data, yaitu pengurutan 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 dinyatakan dalam tabel ASCII.
Pengurutan data menjadi satu bagian yang penting dalam ilmu komputer karena waktu yang diperlukan untuk melakukan proses pengurutan perlu dipertimbangkan. Selain itu, masih ada beberapa aspek lain yang cukup menarik untuk dipelajari. Data yang harus kita urutkan tentunya sangat bervariasi baik dalam hal banyak data maupun jenis data yang akan diurutkan.
Beberapa faktor yang mempengaruhi pada efektifitas suatu algoritma pengurutan antara lain:
- banyak data yang akan diurutkan,
- kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki,
- tempat penyimpanan data.
Dalam keadaan terurutkan, kita mudah mencek apakah ada data yang hilang (misalnya dalam tumpukan kartu bridge).
Pengurutan juga digunakan dalam mengkompilasi program komputer jika tabel-tabel simbol harus dibentuk, dan juga memegang peran penting untuk mempercepat proses pencarian data yang harus dilakukan berulang kali.
Pemilihan algoritma sangat ditentukan oleh struktur data yang digunakan.
Dengan alasan ini maka sejumlah metoda pengurutan yang akan dijelaskan bisa diklasifikasikan menjadi dua kategori, yaitu pengurutan larik (array), dan pengurutan berkas masup urut (sequential access file). 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 disk.
Contoh sederhana untuk membedakan dua kategori ini adalah pengurutan sejumlah kartu yang telah diberi nomor.
Penyusunan kartu sebagai sebuah larik bisa kita bayangkan bahwa semua kartu terletak dihadapan kita sehingga semua kartu terlihat dengan jelas nomornya, dan setiap kartu bisa dimasup sendiri-sendiri. Penyusunan kartu sebagai sebuah berkas, agak berbeda, yakni semua kartu kita tumpuk sehingga hanya kartu bagian atas saja yang bisa kita lihat nomornya.
Batasan ini akan membawa konsekuensi yang serius dalam pemilihan metoda yang akan digunakan, tetapi mungkin tidak bisa dihindarkan karena jumlah kartu cukup banyak sehingga meja tidak cukup luas untuk meletakkan seluruh kartu di atasnya.
Pengurutan Larik
Dalam pengurutan larik, yang disimpan dalam pengingat utama komputer, ada aspek ekonomis yang perlu dipertimbangkan. Aspek ini antara lain menyangkut kapasitas pengingat yang tersedia. Aspek lain adalah dalam hal waktu, yaitu waktu yang diperlukan untuk melakukan permutasi sehingga semua elemen akhirnya menjadi terurutkan.
Ukuran efisiensi yang baik bisa diperoleh dari banyaknya pembandingan dan perpindahan yang harus dilakukan. Angka-angka ini merupakan fungsi dari N yaitu banyaknya elemen yang akan diurutkan.
Algoritma yang baik memerlukan pembandingan sebanyak N log N kali. Meskipun demikian kita akan melihat beberapa metoda yang disebut dengan metoda langsung (straight method), yang seluruhnya memerlukan N2 pembandingan.
Metoda langsung ini bisa dikelompokkan menjadi tiga metoda, yaitu penyisipan (insertion), seleksi (selection), dan penukaran (exchange).
Sebelum kita melihat masing-masing metoda, marilah kita melihat terlebih dahulu deklarasi larik yang akan kita gunakan. Dalam hal ini kita akan menggunakan larik dimensi satu (vektor) yang elemennya bertipe real.
Deklarasi.
const N = 100;
type Larik = array [1 .. N] of real;
Dalam deklarasi di atas, N adalah banyaknya elemen vektor. Anda bisa mengubah nilai konstanta N sesuai kebutuhan. Selain deklarasi di atas, berikut ini 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.
{ Prosedur untuk menukarkan nilai dua buah elemen }
procedure TUKARKAN (var A, B: real);
var T: real;
begin
T:=A;
A:=B;
B:=T
end;
Metoda Penyisipan Langsung
Metoda penyisipan langsung (straight insertion) banyak digunakan oleh pemain kartu.
Dalam metoda ini elemen-elemen (kartu) terbagi menjadi dua kelompok. Kelompok pertama, yaitu kelompok tujuan (kartu yang ada di tangan pemain yang sudah dalam keadaan urut) dengan urutan A1 … AI-1. Kelompok kedua disebut kelompok sumber (kartu yang masih ada di atas meja, dan masih belum terurutkan), dengan urutan AI…AN.
Dalam setiap langkah, dimulai dari I = 2, dengan pertambahan 1, elemen ke I diambil dari kelompok sumber akan dipindah ke kelompok tujuan dengan cara menyisipkannya pada tempatnya yang sesuai.
Algoritma SISIP_LANGSUNG
[Pengurutan elemen menggunakan metoda penyisipan langsung. Masukan dinyatakan sebagai vektor A (belum terurut), dan N (banyak elemen). Keluaran adalah vektor A yang sudah dalam keadaan terurut]
Langkah 0 Baca vektor yang akan diurutkan (dalam program utama).
Langkah 1 Kerjakan langkah 2 sampai langkah 5 untuk I=2 sampai N.
Langkah 2 Tentukan T=A[I] (elemen yang disisipkan);
A=[0]=T (data sentinel), dan
J=I-1.
Langkah 3 (Lakukan perggeseran).
Kerjakan langkah 4 selama T <A[J]
Langkah 4 Tentukan: A[J+1]=A[J], dan
= J-1.
Langkah 5 Tentukan: A[J+1]=T
Langkah 6 Selesai.
Penyisipan Biner
Dengan cara penyisipan langsung, pembandingan selalu dimulai dari elemen pertama, sehingga untuk menyisipkan elemen ke I kita harus melakukan pembandingan sebanyak I-1 kali. Hal ini bisa dipercepat dengan mengingat bahwa elemen pertama sampai elemen ke I-1 telah dalam keadaan urut, sehingga pembandingan tidak harus dimulai dari elemen pertama.
Metoda penyisipan biner (binary insertion) merupakan perbaikan terhadap metoda penyisipan langsung, dimana pembandingan tidak dilakukan dimulai dari elemen pertama sampai ke I-1, tetapi dengan pembandingan biner.
Caranya, kelompok yang sudah dalam keadaan urut (elemen ke 1 sampai I-1) dibagi menjadi dua bagian, kemudian elemen yang akan disisipkan dilihat kira-kira akan disisipkan pada bagian pertama atau kedua. Jika diperkirakan akan menempati bagian pertama, maka bagian kedua tidak perlu dilihat lagi, atau sebaliknya.
Cara ini diulang sampai posisi yang tepat untuk elemen baru ditemukan. Sebagai contoh, kita ambil satu langkah pada proses penyisipan langsung, yaitu dalam langkah ke-7, dengan akan disisipkannya elemen yang bernilai 27.
I=6 |12 23 24 34 45 56 27 23 26 |
I=7 |12 23 24 27 34 45 56 23 26 |
Pada langkah ke-7 kita telah memperoleh 6 elemen pertama dalam keadaan terurutkan. Keenam elemen ini kita bagi dua (sama besar), yaitu (12 23 24) dan (34 45 56).
Karena yang akan disisipkan adalah 27, maka pastilah akan menempati bagian (34 45 56). Dengan demikian pencarian posisi dilakukan hanya pada bagian ini. Bagian ini dipecah lagi menjadi dua bagian dan dicari lagi sampai posisi nilai yang akan disisipkan diketahui dengan tepat. Berikut adalah algoritmanya
Algoritma SISIP_BINER
Pengurutan elemen menggunakan metoda penyisipan biner. Masukan dinyatakan sebagai vektor A (belum terurutkan), dan N (banyak elemen). Keluaran adalah vektor A yang sudah dalam keadaan terurutkan.
Langkah 0 Baca vektor yang akan diurutkan (dalam program utama).
Langkah 1 Kerjakan langkah 2 sampai langkah 8 untuk I = 2 sampai N.
Langkah 2 Tentukan: T = A [I] (elemen yang akan disisipkan);
Kiri = 1 (batas kiri), dan
Kanan = I – 1 (batas kanan).
Langkah 3 (Lakukan pembandingan biner).
Kerjakan langkah 4 dan 5 selama Kiri <= Kanan.
Langkah 4 (Membagi elemen pertama sampai I-1 menjadi dua bagian.)
Tentukan: Tengah = (Kiri + Kanan) div 2.
Langkah 5 Test: apakah T < A[Tengah]?
Jika ya, tentukan: Kanan = Tengah-1.
Jika tidak, tentukan: Kiri = Tengah+1.
Langkah 6 (Lakukan penggeseran.)
Kerjakan langkah 7 untuk J = I-1 sampai dengan Kiri dengan langkah mundur.
Langkah 7 Tentukan: A[J+1] = A[J].
Langkah 8 Tentukan: A[Kiri] = T.
Langkah 9 Selesai.
Telah dikatakan di atas bahwa metoda penyisipan biner adalah perbaikan dari metoda penyisipan langsung. Dalam hal ini yang diperbaiki adalah banyaknya pembandingan, sedangkan banyaknya penggeseran tetap. Dalam metoda ini banyaknya pembandingan adalah:
C = (log N – log e ± 0.5)
Metode Seleksi
Cara kerja metode seleksi didasarkan pada pencarian elemen dengan nilai terkecil, kemudian dilakukan penukaran dengan elemen ke-I. Secara singkat, metoda ini bisa dijelaskan sebagai berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai data terakhir. Kemudian data terkecil tersebut kita tukar dengan data pertama.
Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibandingkan data yang lain. Pada langkah kedua, data terkecil kita cari mulai data kedua sampai data terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua. Demikian seterusnya sampai seluruh vektor dalam keadaan terurutkan.
Algoritma SELEKSI
Pengurutan elemen menggunakan metoda seleksi. Masukan dinyatakan sebagai vektor A (belum terurutkan), dan N (banyak elemen). Keluaran adalah vektor A yang sudah dalam keadaan terurutkan.
Langkah 0 Baca vektor yang akan diurutkan (dalam program utama).
Langkah 1 Kerjakan langkah 2 sampai langkah 4 untuk I = 1 sampai N-1.
Langkah 2 Tentukan: lok = I
Kerjakan langkah 3 untuk J = I + 1 sampai N.
Langkah 3 (Mencari data terkecil).
Test: apakah A[lok] > A[j] ?
Jika ya, tentukan: lok = J.
Langkah 4 Tukarkan nilai A[lok] dengan A[I]
Langkah 5 Selesai.
Metoda ini secara garis besar merupakan kebalikan dari metoda penyisipan langsung. Dalam setiap langkah pada metoda penyisipan langsung kita hanya memperhatikan satu elemen dari sumber dan semua elemen dari larik tujuan untuk menetukan posisinya yang tepat; sehingga sering disebut dengan one source-multiple destinations.
Dalam metoda ini seleksi terjadi sebaliknya, yakni kita memperhatikan semua elemen dalam larik sumber untuk menentukan elemen terkecil yang akan kita tempatkan pada tujuan; sehingga sering disebut dengan multiple source one destination.
Dalam metoda ini banyaknya pembandingkan ( untuk mencari elemen dengan nilai terkecil) besarnya tak gayut terhadap urutan semula. Banyaknya pembandingkan adalah sebesar:
C = (N2 – N) / 2
Metode Gelombang
Metoda gelombang (BubleSort), sering juga disebut dengan metoda penukaran (ExchangeSort), adalah metoda yang mendasarkan penukaran dua buah elemen untuk mencapai keadaan ururt yang diingkinkan. Metoda ini cukup mudah untuk dipahami dan diprogram. Tetapi dari beberapa metoda yang akan pelajari, metoda ini merupakan metoda yang paling tidak efisien.
Untuk membawa vektor menjadi dalam keadaan urut bisa dilaksanakan dengan dua cara. Cara pertama adalah selalu meletakkan elemen dengan nilai paling besar pada posisi terakhir (posisi ke N). kemudian elemen dengan nilai paling besar kedua diletakkan pada posisi N-1, dan seterusnya. Cara kedua adalah kebalikan cara pertama. Dalam hal ini yang digunakan sebagai patokan adalah nilai terkecil.
Dengan kata lain, pada iterasi pertama kita akan meletakkan elemen dengan nilai terkecil pada posisi ke 1. Kemudian elemen dengan nilai elemen terkecil kedua diletakkan pada posisi ke 2, dan seterusnya. Dalam hal ini kita akan menggunakan cara pertama.
Algoritma GELOMBANG
Pengurutan elemen menggunakan metoda gelombang. Masukan dinyatakan sebagai vektor A (belum terurutkan), dan N (banyak elemen). Keluaran adalah vektor A yang sudah dalam keadaan terurutkan.
Langkah 0 Baca vektor yang akan diurutkan (dalam program utama).
Langkah 1 Kerjakan langkah 2 untuk I = 1 sampai N-1.
Langkah 2 Kerjakan langkah 3 untuk J = 1 sampai N-I.
Langkah 3 Test: apakah A[J] > A[J+1] ?
Jika ya, tukarkan nilai kedua elemen ini.
Langkah 5 Selesai.
Berdasarkan algoritma di atas, kita bisa menyusun prosedurnya seperti tersaji dalam program 5. Di atas telah disebutkan bahwa metoda ini merupakan metoda yang paling tidak efesien.
Alasanya adalah bahwa apabila kita mengurutkan vektor sebanyak N elemen dan pada iterasi yang kurang dari N-1, maka iterasi tersebut harus tetap dilaksanakan sampai N-1.
Dengan demikian, dalam metoda Gelombang akan terjadi pembandingkan dan pemindahan atau penukaran dua elemen sebanyak:
Mmin = 0
Mrata2 = 3 (N2 – N) / 4
C = (N2 – N) / 2 Mmaks = 3 (N2 – 4) / 2