Masalah
dalam penyortiran adalah untuk mengatur ulang item dari daftar yang diberikan di
rangka nondecreasing. Tentu saja, untuk masalah ini menjadi bermakna, sifat
dari daftar item harus memungkinkan pemesanan tersebut. Sebagai masalah
praktis, biasanya kita perlu memilah daftar angka, karakter dari alfabet,
karakter string, dan yang paling penting catatan mirip dengan yang dikelola
oleh sekolah tentang siswa mereka, perpustakaan tentang kepemilikan mereka dan
perusahaan tentang karyawan mereka. Dalam kasus catatan kami harus memilih
sepotong informasi untuk memandu penyortiran. Sebagai contoh, kita bisa memilih
untuk menyortir catatan siswa dalam urutan abjad nama atau nomor siswa atau
oleh siswa kelas rata-rata. Seperti sepotong khusus dipilih dari informasi
disebut kunci. ilmuwan komputer sering berbicara tentang menyortir daftar kunci
bahkan ketika item daftar ini tidak catatan tetapi mengatakan hanya bilangan
bulat.
Mengapa
kita ingin daftar diurutkan? Untuk mulainya dengan, daftar diurutkan dapat
menjadi Output yang dibutuhkan dari tugas seperti peringkat hasil pencarian
Internet atau peringkat siswa. Selanjutnya, penyortiran membuat banyak
pertanyaan tentang daftar mudah untuk menjawab. Yang paling penting dari mereka
adalah mencari, itu sebabnya kamus, buku telepon, daftar kelas, dan sebagainya
diurutkan. Dalam nada yang sama, pemilahan digunakan sebagai langkah tambahan di
beberapa algoritma penting di daerah lain, misalnya algoritma geometrik dan
data kompresi.
Sekarang,
ilmuwan komputer telah menemukan puluhan algoritma sorting yang berbeda. Bahkan,
menciptakan algoritma sorting baru telah disamakan dengan merancang perangkap
tikus pepatah. Dan saya senang melaporkan bahwa perburuan perangkap tikus
penyortirannya lebih baik. ketekunan ini mengagumkan mengingat fakta-fakta
berikut. Di satu sisi, ada beberapa algoritma pengurutan yang baik semacam array
sewenang-wenang ukuran n menggunakan sekitar n log2 n perbandingan. Di samping
itu, tidak ada algoritma yang macam oleh perbandingan kunci (sebagai lawan, katakanlah,
membandingkan potongan-potongan kecil dari kunci) dapat melakukan jauh lebih
baik dari itu.
Ada
alasan untuk malu ini kekayaan algoritmik di tanah penyortiran. Meskipun
beberapa algoritma yang memang lebih baik daripada yang lain, tidak ada algoritma
yang akan menjadi solusi terbaik dalam segala situasi. Beberapa algoritma sederhana
namun relatif lambat, sementara yang lain lebih cepat tetapi lebih kompleks. beberapa
pekerjaan yang lebih baik di acak memerintahkan masukan, sementara yang lain lebih
baik pada daftar hampir diurutkan , beberapa hanya cocok untuk daftar yang berada
di memori cepat, sementara yang lain dapat disesuaikan untuk menyortir file
besar yang disimpan pada disk, dan seterusnya.
Dua
sifat dari algoritma pengurutan layak algoritma mention. Asorting khusus disebut
stabil jika mempertahankan urutan relatif dari dua elemen yang sama dalam input.
Dengan kata lain, jika daftar masukan berisi dua elemen yang sama di posisi i
dan j mana i <j, maka dalam daftar diurutkan mereka harus berada di posisi i
dan j masing-masing, sehingga i <j. Properti ini dapat diinginkan jika,
misalnya kita memiliki daftar mahasiswa diurutkan berdasarkan abjad dan kita ingin
mengurutkan sesuai dengan mahasiswa IPK. algoritma yang stabil akan
menghasilkan daftar di mana mahasiswa dengan IPK yang sama masih akan diurutkan
berdasarkan abjad. Secara umum, algoritma yang dapat bertukar kunci terletak
berjauhan tidak stabil, tetapi mereka biasanya bekerja lebih cepat.
Fitur
penting kedua algoritma sorting membutuhkan jumlah memori tambahan. Sebuah
algoritma dikatakan di tempat jika tidak memerlukan memori tambahan. kecuali,
mungkin untuk beberapa unit memor.
Atau dapat disimpulkan :
- · Problem: menyusun ulang hal-hal yang terdapat pada daftar dengan urutan naik atau turun
- · Jika ada records, kita perlu sebuah key
- · Terdapat bermacam-macam algoritma sorting
- · Dua properti algoritma sorting:
o
Stabil:
Mempertahankan urutan relatif sembarang dua elemen input yang sama.
o
Di
tempat: tidak memerlukan memori ekstra, kecuali,mungkin, beberapa unit memori.
Tidak ada komentar:
Posting Komentar