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. Pengurutan data dalam struktur data sangat penting untuk data yang beripe data numerika ataupun karakter.
Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu.
Pada umumnya terdapat dua jenis pengurutan :
- Ascending (Naik).
- Descending (Turun).
- Ascending (Naik).
- Descending (Turun).
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
Searching
• Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching.
• Searching adalah pencarian data dengan cara menelusuri data-data tersebut.
• Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Sequential Search
• Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
• Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).
• Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
• Misalnya terdapat array satu dimensi sebagai berikut:
• Kemudian program akan meminta data yang akan dicari, misalnya 6.
• Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.
Array pada dasarnya merupakan suatu tipe data yang dapat menampung serangkaian tipe data yang sama dalam suatu variabel. Bila pada dasarnya kita mengenal tipe variabel seperti character atau char, integer atau int, dan float atau real, maka tipe data tersebut umumnya hanya dapat menampung sebuah data saja bila tidak menggunakan array.
Ketika menggunakan array pun, banyak bahasa pemrograman yang menggunakan index atau key dalam array menggunakan angka bulat atau integer yang umumnya dimulai dari 0 (nol).
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Terdapat 2 metode pencarian yaitu Metode Pencarian Beruntun (Sequential Search) dan Metode Pencarian Bagidua (Binary Search), kita hanya akan membahas metode yang kedua yaitu Metode Pencarian Bagidua (Binary Search). Karena metode ini adalah metode pencarian pada data terurut yang paling efficient. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.
Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching merupakan pencarian data dengan cara menelusuri data-data tersebut Pencarian(searching) merupakan proses yang fundamental dalam pengolahan data.
Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama ( baik bertipe dasar atau bertipe bentukan ). Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Di dalam Buku Algoritma dan Pemrograman telah disebutkan bahwa aktivitas yang berkaitan dengan pengolahan data sering didahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.
Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang sama yang sama juga dilakukan pada proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahakan sudah terdapat di dalam kumpulan. Jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Binary Search Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan.
Ketika menggunakan array pun, banyak bahasa pemrograman yang menggunakan index atau key dalam array menggunakan angka bulat atau integer yang umumnya dimulai dari 0 (nol).
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Terdapat 2 metode pencarian yaitu Metode Pencarian Beruntun (Sequential Search) dan Metode Pencarian Bagidua (Binary Search), kita hanya akan membahas metode yang kedua yaitu Metode Pencarian Bagidua (Binary Search). Karena metode ini adalah metode pencarian pada data terurut yang paling efficient. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.
Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching merupakan pencarian data dengan cara menelusuri data-data tersebut Pencarian(searching) merupakan proses yang fundamental dalam pengolahan data.
Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama ( baik bertipe dasar atau bertipe bentukan ). Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Di dalam Buku Algoritma dan Pemrograman telah disebutkan bahwa aktivitas yang berkaitan dengan pengolahan data sering didahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.
Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang sama yang sama juga dilakukan pada proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahakan sudah terdapat di dalam kumpulan. Jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Binary Search Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan.
Prinsip pencarian biner adalah:v
o Data diambil dari posisi 1 sampai posisi akhir N
o Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
o Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
o Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
o Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
o Jika data sama, berarti ketemu.
Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:
Misalkan, kita ingin mencari posisi dari nilai 56.
o Data diambil dari posisi 1 sampai posisi akhir N
o Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
o Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
o Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
o Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
o Jika data sama, berarti ketemu.
Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:
Misalkan, kita ingin mencari posisi dari nilai 56.
Pertama kali, larik di atas dapat kita bagi menjadi 2 sublarik sebagai berikut:
Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1
(11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi.
Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1
(11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi.
Proses di atas diulangi lagi. Sublarik 2 dibagi 2 lagi sehingga menghasilkan sublarik dibawah ini:
Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut:
Larik merupakan tipe data terstruktur. Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan sekumpulan elemen bertipe sama secara berturutan (sequential) di dalam memori komputer. Setiap elemen larik data diacu melalui indeksnya.
Karena elemen disimpan secara berurutan, indeks larik haruslah suatu tipe yang juga mempunyai keterurutan (memiliki suksesor dan ada predesesor), misalnya tipe integer atau karakter. Jika indeks larik adalah karakter maka keterurutan indeks sesuai dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan nama larik berikut indeksnya.
Larik dipelajari lebih mendalam dalam Buku 2, karena larik adalah struktur internal (yaitu, struktur yang direalisasikan di dalam memori utama), maka pencarian elemen di dalam larik disebut juga pencarian internal. Sedangkan pada pencarian eksternal, pencarian dilakukan terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk. Penyimpanan data di dalam storage bersifat permanen dengan tujuan agar dapat dibaca kembali untuk pemrosesan lebih lanjut.
Persoalan Pencarian
Diberikan larik L yang sudah terdefinisi elemen-elemennya , dan x adalah elemen yang bertipe sama dengan elemen larik L. Carilah x di dalam larik L.
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam, bergantung pada spesifikasi (spek) rinci dari persolan tersebut, misalnya:
a. Pencarian hanya untuk memeriksa keberadaan x. Keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik.
b. Hasil pencarian adalah indeks elemen larik. Jika x ditemukan, maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat di dalam larik L, maka idx diisi dengan harga khusus, misalnya -1.
c. Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil pencarian. Jika x ditemukan, maka sebuah peubah bertipe boolean, misalnya ketemu, diisi dengan nilai true, sebaliknya “ketemu” diisi dengan nilai false. Hasil pencarian ini selanjutnya disimpulkan pada pemanggilan prosedur.
Contoh : keluaran hasil pencariaan berupa Boolean
Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut:
Larik merupakan tipe data terstruktur. Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan sekumpulan elemen bertipe sama secara berturutan (sequential) di dalam memori komputer. Setiap elemen larik data diacu melalui indeksnya.
Karena elemen disimpan secara berurutan, indeks larik haruslah suatu tipe yang juga mempunyai keterurutan (memiliki suksesor dan ada predesesor), misalnya tipe integer atau karakter. Jika indeks larik adalah karakter maka keterurutan indeks sesuai dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan nama larik berikut indeksnya.
Larik dipelajari lebih mendalam dalam Buku 2, karena larik adalah struktur internal (yaitu, struktur yang direalisasikan di dalam memori utama), maka pencarian elemen di dalam larik disebut juga pencarian internal. Sedangkan pada pencarian eksternal, pencarian dilakukan terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk. Penyimpanan data di dalam storage bersifat permanen dengan tujuan agar dapat dibaca kembali untuk pemrosesan lebih lanjut.
Persoalan Pencarian
Diberikan larik L yang sudah terdefinisi elemen-elemennya , dan x adalah elemen yang bertipe sama dengan elemen larik L. Carilah x di dalam larik L.
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam, bergantung pada spesifikasi (spek) rinci dari persolan tersebut, misalnya:
a. Pencarian hanya untuk memeriksa keberadaan x. Keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik.
b. Hasil pencarian adalah indeks elemen larik. Jika x ditemukan, maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat di dalam larik L, maka idx diisi dengan harga khusus, misalnya -1.
c. Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil pencarian. Jika x ditemukan, maka sebuah peubah bertipe boolean, misalnya ketemu, diisi dengan nilai true, sebaliknya “ketemu” diisi dengan nilai false. Hasil pencarian ini selanjutnya disimpulkan pada pemanggilan prosedur.
Contoh : keluaran hasil pencariaan berupa Boolean
SUMBER : materi praktikum struktur data
Free Template Blogger collection template Hot Deals SEO
0 komentar:
Posting Komentar