Algoritma Searching and Sorting

1. Sorting

Dalam ilmu komputer, algoritme penyortiran adalah algoritme yang menempatkan elemen daftar dalam urutan tertentu. Pesanan yang paling sering digunakan adalah urutan numerik dan urutan leksikografis. Pengurutan efisien penting untuk mengoptimalkan efisiensi algoritme lain (seperti penelusuran dan penggabungan algoritme) yang memerlukan data masukan untuk diurutkan daftar. Penyortiran juga sering berguna untuk data kanonikalisasi dan untuk menghasilkan keluaran yang dapat dibaca manusia. Lebih formal, output dari algoritma penyortiran apa pun harus memenuhi dua kondisi:

• Outputnya dalam urutan yang tidak teratur (setiap elemen tidak lebih kecil dari elemen sebelumnya sesuai dengan total order yang diinginkan);

• Outputnya adalah permutasi (pengurutan ulang, namun tetap mempertahankan semua elemen asli) dari input.

Lebih lanjut, data input sering disimpan di dalam array, yang memungkinkan akses acak, bukan daftar, yang hanya memungkinkan akses berurutan; meskipun banyak algoritma dapat diterapkan untuk kedua jenis data setelah modifikasi yang sesuai.

     2. Searching

Algoritma pencarian adalah algoritma yang memecahkan masalah pencarian, yaitu, untuk mengambil informasi yang tersimpan dalam beberapa struktur data, atau dihitung dalam ruang pencarian domain masalah. Contoh struktur tersebut termasuk tetapi tidak terbatas pada daftar tertaut, struktur data larik, atau pohon pencarian. Algoritme pencarian yang sesuai seringkali tergantung pada struktur data yang sedang dicari, dan mungkin juga termasuk pengetahuan sebelumnya tentang data. Pencarian juga mencakup algoritma yang menanyakan struktur data, seperti perintah SQL SELECT.

Algoritma pencarian dapat diklasifikasikan berdasarkan mekanisme pencarian mereka. Algoritma pencarian linier memeriksa setiap catatan untuk yang terkait dengan kunci target secara linier. Binary, atau setengah interval pencarian, berulang kali menargetkan pusat struktur pencarian dan membagi ruang pencarian menjadi dua. Perbandingan algoritma pencarian memperbaiki pencarian linier dengan secara berturut-turut menghilangkan catatan berdasarkan perbandingan kunci sampai catatan target ditemukan, dan dapat diterapkan pada struktur data dengan urutan yang ditentukan. Algoritme pencarian digital bekerja berdasarkan properti digit dalam struktur data yang menggunakan tombol angka. Akhirnya, hashing langsung memetakan kunci ke catatan berdasarkan fungsi hash. Pencarian di luar pencarian linear mengharuskan data diurutkan dalam beberapa cara.

Fungsi pencarian juga dievaluasi berdasarkan kompleksitasnya, atau waktu berjalan teoritis maksimum. Fungsi pencarian biner, misalnya, memiliki kompleksitas maksimum O (log n), atau waktu logaritmik. Ini berarti bahwa jumlah maksimum operasi yang diperlukan untuk menemukan target pencarian adalah fungsi logaritmik dari ukuran ruang pencarian.