Struktur Data – Search & Sort

on


8.1   Sort

8.1.1 Definisi Sorting  method

Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat dua jenis pengurutan :

– Ascending (Naik).

– Descending (Turun).

Contoh :

Data : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);

Data Acak : 22 10 15 3 8 2

Terurut Ascending : 2 3 8 10 15 22

Terurut Descending : 22 15 10 8 3 2

Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.

8.1.2  Metode pengurutan data dengan Sorth

1.   Bubble/Exchange Sort

Metode ini merupakan metode yang paling sederhana dan paling tidak efisien,karena memerlukan waktu yang relatif lebih lama dibandingkan dengan metodemetode yang lainnya. Konsep dasar dari Bubble sort ialah membandingkan elemen yang sekarang degan elemen yang berikutnya, jika elemen sekarang > elemen berikutnya (untuk ascending), maka dilakukan proses penukaran. Proses sorting dapat dimulai dari data awal atau data akhir.

2.  Selection Sort

Cara kerja metode ini didasarkan pada pencarian elemen dengan nilai terkecil, kemudian dilakukan penukaran dengan elemen ke-I. Secara  ingkat, metode ini bisa dijelaskan sebagai berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai data terakhir. Kemudian data tersebut kita tukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data lain. Pada langkah kedua, data terkecil kita cari mulai dari data kedua sampai data terakhir. Data terkecil yang kita peroleh kita tukar dengan data kedua. Demikian seterusnya sampai suluruh data terurut.

3.  Shell Sort

Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen yang dibandingkan dan ditukarkan tertentu.Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu  dari elemen pertama tersebut. Kemudian elemen kedua kita bandingkan dengan

4. Quick Sort

Metode ini dikembangkan oleh C.A.R Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang mempunyai N elemen. Kita pilih sembarang elemen dari data tersebut, bisanya elemen pertama, misalnya X. kemudian semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa sehingga elemen ke 1 sampai ke J- 1 mempunyai nilai lebih kecil dari X dan elemen J+1 sampai ke N mempunyai nilai lebih besar dari X. Sampai saat ini kita sudah mempunyai dua sub data (kiri dan kanan). Langkah berikutnya diulang untuk setiap sub data. Contoh dari proses Sorting dengan menggunakan metode Quick Sort :

5.  Insertion Sort (Metode Penyisipan)

–        Straight Insertion Sort (Metode Penyisipan langsung)

Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut :  

Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

–        Binary Insertion Sort (Metode Penyisipan Biner)

Metode ini merupakan pengembangan dari metode penyisipan langsung. Dengan cara penyisipan langsung, perbandingan selalu dimulai dari elemen pertama (data ke-0), sehingga untuk menyisipkan elemen ke i kita harus melakukan perbandingan sebanyak i- 1 kali. Ide dari metode ini didasarkan pada kenyataan bahwa pada saat menggeser data ke-i, data ke 0 s/d i-1 sebenarnya sudah dalam keadaan terurut.

6.  Merge Sort (Metode Penggabungan)

Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut :

Mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data pertama (T1) adalah sebagai berikut :

3 11 12 23 31

Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :

9 15 17 20 35

Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya sehingga didapat hasil sebagai berikut :

3 9 11 12 15 17 20 23 31 35

8.2  Search

8.2.1 Definisi Search

Searching merupakan suatu proses pendarian data dari sejumlah data yang ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau juga pada data yang sama sekali belum terurut. Kita mencoba menggunakan dua metode pencarian yaitu :

1.  Pencarian Berurutan (Sequential Searching).

2.  Pencarian Biner (Binary Seacrh).

8.2.2. Metode pencarian

1.  Pencarian Berurutan (Sequential Searching)

Metode ini merupakan metode paling sederhana, secara garis besar metode ini bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan. Pada saat data yang dicari sudah ditemukan, maka proses pencarian langsung dihentikan. Tetapi jika belum ditemukan, maka pencarian diteruskan sampai seluruh data dibandingkan. Dalam kasus paling buruk, untuk data dengan N

2.  Metode Pencarian Biner (Binary Search)

Metode ini digunakan jika sejumlah data telah diurutkan. Jika dibandingkan dengan metode awal tadi metode ini jauh lebih cepat. Secara garis besar metode ini bisa dijelaskan sebagai berikut. Urutkan dahulu sejumlah data. Lalu bagi dua data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan berulang sampai data ditemukan atau tidak ditemukan.

7 Comments Add yours

  1. Juegos infantiles mengatakan:

    De seguro que este articulo ha sido repasado por la casi todos los foreros, de internet
    ya que se trata de algo un llamativo fragmento de texto
    para lla fabricacion de recientes websites.

  2. juegos gratis mengatakan:

    Ahaa, ees una discusion fascinante lo escrito en este
    articulo que me he encontrado en este lugar web, lo he leido
    detenidamente y ahora me encantaria poder hablar. een este site.

  3. Hello there! Do you know if they make any plugins to safeguard against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?

  4. juegos de navegador mengatakan:

    Este es uno de los webblog que bastante mas me emocionan! Tus posteo resultan ser increiblemente sobresalientes!
    Te dejo en predilectos!

  5. Destiny cazador mengatakan:

     Bien escrito, si bien es cierto que hay ciertas sugerencias een las que no
    coincido en consonancia.

  6.  Tengo integramente en armonia con absolutamente todos los conseguir puntos que has posteado , si bien no en el
    conjunto. Un forum perfecto.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s