Algoritma penyortiran dan pencarian
Kami akan mulai menganalisis beberapa algoritma pengurutan. Seperti namanya, tujuannya adalah mengurutkan item dalam struktur data.
Sortir Gelembung
Bubble sort adalah algoritma paling sederhana yang diusulkan dalam artikel ini. Dengan adanya daftar, ia membandingkan dua angka yang berdekatan dan jika angka yang lebih besar berada di posisi pertama maka ia berpindah tempat ke kedua angka tersebut. Ini menelusuri seluruh daftar dengan cara ini. Untuk mendapatkan hasil yang benar, pengurutan gelembung harus dilakukan beberapa kali pada daftar yang sama dan oleh karena itu terdiri dari dua siklus:
● Internal, berapa kali diperlukan untuk mengulang algoritma eksternal dalam daftar;
● Eksternal, perbandingan antara angka-angka yang berdekatan.
Algoritme ini diuntungkan ketika daftar sudah setengah terurut dan hanya direkomendasikan pada daftar berukuran kecil, jika ukurannya terlalu diperluas, waktu proses juga dapat meningkat secara signifikan.
Contoh dengan gambar:
Dalam contoh ini, daftar delapan item diurutkan, seperti yang Anda lihat setiap item dibandingkan dengan item berikutnya dan jika item berikutnya lebih besar maka posisinya akan diperdagangkan.
Seperti yang Anda lihat, hasil akhirnya belum terurut sepenuhnya, jadi Anda perlu melakukan perbandingan berpasangan hingga seluruh daftar terurut.
Sortir Penyisipan
Pengurutan penyisipan dimulai dengan memilih dua item pertama dalam daftar, membuat perbandingan, dan mendorong item terbesar ke posisi yang tepat. Kemudian ia juga memilih elemen ketiga dengan mengingat dua elemen sebelumnya dan mengulangi langkah yang sama, sehingga mengubah urutan elemen sesuai dengan nilainya.
Algoritme ini juga direkomendasikan pada kumpulan data kecil, kinerja akan semakin memburuk seiring bertambahnya ukuran kumpulan data.
Contoh dengan gambar:
Seperti yang dapat dilihat dalam kasus ini, tidak hanya dua elemen yang dipertimbangkan tetapi setelah dua elemen pertama, perbandingannya meluas menjadi tiga elemen dan kemudian meluas menjadi empat. Setiap kali jumlah item yang dipertimbangkan bertambah, daftarnya diurutkan.
Pada contoh pada perbandingan pertama tidak ada perubahan karena 25 dan 26 sudah berada pada posisi yang tepat. Namun pada pemilihan 22 daftarnya berubah karena 22 dipindahkan ke posisi pertama mengingat itu adalah angka terkecil dari angka yang dipilih.
Dalam hal ini tidak perlu menjalankan algoritma beberapa kali seperti pada kasus bubble sort. Ketika semua item dipilih maka daftar akan diurutkan.
Gabungkan Sortir
Performa Pengurutan Gabungan tidak bergantung pada urutan elemen dalam struktur data, ia beroperasi dalam dua langkah:
● Pemisahan, daftar dibagi menjadi dua dan kemudian menjadi dua lagi hingga daftar kecil dengan panjang 1 dibuat;
● Penggabungan, daftar dengan panjang 1 disatukan dan saat dikumpulkan, elemen-elemennya diurutkan.
Contoh dengan gambar:
Seperti yang Anda lihat, daftar selalu dibagi dua dengan membuat daftar lebih kecil yang terdiri dari dua bagian. Proses ini, Pemisahan, berlaku hingga daftar kecil dengan panjang 1 tersisa. Ketika hanya daftar dengan panjang satu yang tersisa, Penggabungan dimulai dan daftar disatukan dengan mengurutkan item.
Sortir Kerang
Daftar tersebut dibagi menjadi daftar-daftar kecil yang terdiri dari dua elemen pada jarak standar.
Misalnya memiliki daftar dua belas elemen, jika elemen pertama dimasukkan ke dalam daftar kedua dengan elemen keempat maka elemen kedua akan dimasukkan ke dalam daftar dengan elemen berikutnya, dengan cara ini jarak elemen-elemen yang membentuk kedua daftar tersebut tidak berbeda.
Proses ini terjadi pada semua item dalam daftar.
Unsur-unsur tersebut kemudian diperhatikan dengan mempertimbangkan pasangan-pasangan yang telah tercipta.
Pada langkah kedua tidak ada lagi pasangan melainkan trio yang akan dibandingkan, bahkan dalam hal ini jarak pada daftar setiap elemen harus sama di semua sublist yang dibuat.
Ini akan berlanjut hingga hanya tersisa satu daftar yang terdiri dari semua item di awal tetapi dalam daftar yang diurutkan.
Dianjurkan untuk menggunakan shell sort dalam daftar dengan kurang dari sepuluh ribu elemen.
Contoh dengan gambar:
Setiap warna mewakili sebuah daftar, di setiap warna elemen selalu berada pada jarak yang sama. Seperti yang dapat dicatat, item dalam setiap daftar diurutkan. Penyortiran berakhir ketika hanya ada satu daftar seukuran daftar aslinya, dengan cara ini daftar sudah setengah terurut dan waktu penyortiran akhir akan jauh lebih singkat.
Sortir seleksi
Ini mirip dengan bubble sort tetapi tidak memilih dua elemen yang berdekatan, pada interaksi pertama ia memilih elemen pertama dan terakhir, membandingkannya dan menempatkan elemen terbesar di bagian atas daftar. Pada interaksi kedua ia akan memilih elemen pertama dan elemen pada posisi kedua dari belakang, sekali lagi melakukan perbandingan dan pertukaran.
Sekali lagi ini tidak disarankan pada daftar besar.
Contoh dengan gambar:
Seperti yang ditunjukkan pada contoh, ini sangat mirip dengan Bubble Sort tetapi elemen yang dipilih bukanlah yang pertama dan berikutnya, melainkan yang pertama dan terakhir — 1 pada setiap iterasi.
Algoritma Pencarian
Pencarian Linier
Ini menelusuri daftar dari item pertama hingga terakhir. Waktu eksekusi tergantung pada panjang daftar tetapi item tidak harus diurutkan agar dapat berfungsi.
Pencarian biner
Untuk jenis pencarian ini daftar harus diurutkan dan kemudian daftar tersebut dibagi menjadi dua titik. Poin pertama adalah elemen pertama sedangkan poin kedua adalah elemen yang berada di tengah daftar. Mengingat nilai elemen pertama dan kedua, separuh dari daftar sudah dapat dikecualikan. Misalnya jika elemen pertama adalah 0 dan yang kedua (jadi yang di tengah daftar) adalah 10 dan elemen yang saya cari adalah 17 maka saya tahu saya tidak dapat mempertimbangkan semuanya antara 0 dan 10 karena daftarnya dipesan.
Sekarang elemen kedua tetap sama, 10, elemen pertama akan menjadi elemen di tengah daftar baru, seperti 15.
Sekali lagi semua elemen dari 10 sampai 15 dapat dikecualikan karena saya tahu bahwa 17 lebih besar dari 15 sehingga akan berada pada bagian yang jumlahnya lebih besar dari 15. Seleksi berlanjut seperti ini sampai nilai yang dicari ditemukan.
Contoh dengan gambar:
Dalam contoh ini daftar diurutkan dan kita tahu bahwa kita harus mencari nilai 2. Item yang berada di tengah daftar adalah 5. 2 kurang dari 5 sehingga item yang dicari berada di sebelah kiri daftar. daftar, jadi sisi kanan dikecualikan. Anda kemudian memilih separuh baru dari daftar yang dipertimbangkan yang dalam hal ini sesuai dengan nilai yang dicari.
Cari berdasarkan Interpolasi
Sekali lagi, daftar harus diurutkan dan diperlukan dua nilai, item pertama dalam daftar dan item terakhir dalam daftar. Jika nilai yang dicari lebih tinggi dari nilai elemen di tengah daftar, maka nilai pertama menjadi elemen di tengah daftar.
Misalnya:
Memiliki daftar dari 0 hingga 10 di mana saya mencari nilai 7.
a (elemen pertama) akan sama dengan 0
B (elemen kedua) akan sama dengan 10.
Setengah dari daftarnya adalah 5.
Tujuh lebih besar dari lima sehingga elemen a sekarang akan mengambil nilai 5 dan daftarnya menjadi dari 5 hingga 10. Setengah yang baru adalah 8. Jadi elemen b akan menjadi 8 dan sekarang Anda memiliki daftar antara 5 dan 8. Pembagian ini terjadi hingga barang yang anda cari ditemukan.
Contoh dengan gambar:
Bahkan dalam kasus ini daftarnya sudah diurutkan dan mengetahui nilai yang harus dicari. Nilai pusat dipilih dan, seperti dalam pencarian biner, bagian dari daftar yang tidak dapat memahami nilai yang dicari dikecualikan. Ketika yang terakhir dibagi, pusatnya tidak dipilih, tetapi nilai pertama dan terakhir dari daftar baru yang dipilih. Jika nilainya tidak cocok maka nilai tersebut akan dikecualikan dan nilai tetangganya akan dipilih hingga salah satu nilai cocok dengan nilai yang dicari.
