Dalam ilmu komputer,
algoritma pengurutan adalah algoritma yang menempatkan unsur-unsur daftar dalam
urutan tertentu. Perintah yang paling sering digunakan adalah nomor urut dan
ketertiban leksikografis. Efisien sortasi penting untuk mengoptimalkan penggunaan algoritma
lainnya (seperti pencarian dan menggabungkan algoritma) yang membutuhkan daftar
diurutkan untuk bekerja dengan benar, melainkan juga sering berguna untuk
canonicalizing data dan untuk menghasilkan output terbaca-manusia. Lebih
formal, output harus memenuhi dua kondisi:
Output adalah dalam
rangka nondecreasing (setiap elemen tidak lebih kecil dari elemen sebelumnya
sesuai dengan total order yang diinginkan);
Output adalah permutasi,
atau penataan ulang, dari input.
Sejak awal komputasi,
masalah pengurutan telah menarik banyak penelitian, mungkin karena kompleksitas
penyelesaian secara efisien meskipun sederhana pernyataannya, akrab. Sebagai contoh, bubble sort
dianalisis sejak 1956. Walaupun banyak yang menganggapnya masalah dipecahkan,
berguna algoritma pengurutan baru masih ditemukan (misalnya, seperti
perpustakaan pertama kali diterbitkan pada tahun 2004). Sorting algoritma yang
lazim di kelas pengantar ilmu komputer, di mana kelimpahan algoritma untuk
masalah memberikan pengenalan lembut ke berbagai konsep algoritma inti, seperti
membagi besar O, notasi dan menaklukkan algoritma, struktur data, algoritma
acak, terbaik, terburuk dan analisis kasus rata-rata, pengorbanan waktu-ruang, dan batas
bawah.
Klasifikasi
Sorting algoritma yang
digunakan dalam ilmu komputer sering dikelompokkan berdasar:
Komputasi kompleksitas (rata-rata terburuk, dan perilaku terbaik) perbandingan unsur dalam hal ukuran daftar. Untuk algoritma pengurutan khas perilaku yang baik dan perilaku buruk. (Lihat notasi Big O.) Ideal perilaku untuk mengurutkan, tapi hal ini tidak mungkin dalam kasus rata-rata. Perbandingan algoritma pengurutan berbasis, yang mengevaluasi elemen daftar melalui operasi perbandingan abstrak kunci, membutuhkan perbandingan setidaknya untuk input yang paling.
Komputasi kompleksitas (rata-rata terburuk, dan perilaku terbaik) perbandingan unsur dalam hal ukuran daftar. Untuk algoritma pengurutan khas perilaku yang baik dan perilaku buruk. (Lihat notasi Big O.) Ideal perilaku untuk mengurutkan, tapi hal ini tidak mungkin dalam kasus rata-rata. Perbandingan algoritma pengurutan berbasis, yang mengevaluasi elemen daftar melalui operasi perbandingan abstrak kunci, membutuhkan perbandingan setidaknya untuk input yang paling.
Komputasi kompleksitas
swap (untuk "di tempat" algoritma).
Penggunaan memori (dan
penggunaan sumber daya komputer lain). Secara khusus, beberapa
algoritma pengurutan adalah "di tempat". Ini berarti bahwa mereka hanya
perlu atau memori di luar item yang disortir dan mereka tidak perlu membuat
lokasi tambahan untuk data yang akan disimpan sementara, seperti dalam
algoritma pengurutan lain.
Rekursi. Beberapa algoritma yang baik
rekursif atau non-rekursif, sementara yang lain mungkin baik (misalnya, menggabungkan
sort). Stabilitas: algoritma pengurutan stabil menjaga urutan
relatif dari record dengan kunci yang sama (yaitu, nilai-nilai). Lihat di bawah untuk informasi
lebih lanjut. Apakah atau tidak mereka adalah semacam perbandingan. Semacam perbandingan memeriksa
data hanya dengan membandingkan dua elemen dengan operator perbandingan.
Metode Umum:
penyisipan, pertukaran, seleksi, penggabungan, dll. jenis Efek termasuk bubble
sort dan quickSort. Seleksi macam termasuk semacam shaker dan heapsort.
Kemampuan beradaptasi:
Apakah atau tidak presortedness input mempengaruhi waktu berjalan. Algoritma yang
mempertimbangkan hal ini diketahui adaptif.
Stabilitas
Algoritma pengurutan
Stabil menjaga urutan relatif dari record dengan kunci yang sama.Jika semua
tombol berbeda maka perbedaan ini tidak diperlukan. Tetapi jika ada kunci sama,
maka algoritma sorting stabil jika setiap kali ada dua catatan (katakanlah R
dan S) dengan tombol yang sama, dan R muncul sebelum S dalam daftar yang asli,
maka R akan selalu muncul sebelum S di daftar diurutkan. Apabila terdapat unsur yang
sama tidak dapat dibedakan, seperti dengan bilangan bulat, atau lebih umum,
data dimana seluruh elemen kunci, stabilitas tidak menjadi masalah. Namun, menganggap bahwa
pasangan berikut nomor harus diurutkan berdasarkan komponen pertama mereka:
0 komentar: