Mavzu: murakkab saralash algortmlari juda ham katta sonlar bilan ishlash

Vaqtning murakkabligi: bu kirish hajmiga nisbatan algoritm tomonidan qabul qilingan vaqtning o'sish sur'ati. Ba'zi algoritmlar boshqalarga qaraganda tezroq. Algoritmning ishlash vaqti algoritmni bajarishdan oldin bajarishi kerak bo'lgan operatsiyalar sonini tavsiflaydi.

Fazoviy murakkablik yoki xotiradan foydalanish: Ushbu parametr saralash algoritmini joyida emas va joyida saralashga tasniflaydi. - Joylashtirish bo'yicha algoritm: Ushbu tartiblash algoritmi ro'yxatdagi elementlarni qayta tartiblash uchun doimiy ravishda qo'shimcha xotiradan foydalanadi. Bu elementni tartibini to'g'ridan-to'g'ri massiv ichida o'zgartirish orqali massivni tartiblaydi. Qo'shimcha ma'lumotlar tuzilishi ishlatilmaydi. Joylashtirish bo'yicha saralash algoritmlariga misollar - qabariqlarni saralash, saralash, qo'shib taqsimlash, to'plangan saralash. - Joy bo'lmagan joyda saralash algoritmi: Ushbu saralash algoritmi massivni tartiblash uchun qo'shimcha ma'lumotlar tuzilmasidan foydalanadi, shuning uchun qo'shimcha joy yoki xotira ishlatiladi. Birlashtirish operatsiyasini amalga oshirish uchun qo'shimcha O (n) bo'sh joyni talab qiladigan Birlashtirish Saralashi va Tez Saralash kiradi.

Barqarorlik: Tartibni aniqlashda foydalaniladigan kalit yoki mulk teng bo'lgan taqdirda turg'un algoritm elementlarning nisbiy tartibini saqlaydi. Shuning uchun, agar ro'yxatda bir xil narsalar mavjud bo'lsa, ushbu tartiblash algoritmi ushbu bir xil elementlar kirishda paydo bo'lgan tartibda saralanishini ta'minlaydi. Bunga barqaror saralash algoritmi kafolatlanadi. Bunga misollar: pufakchalarni saralash, qo'shimchalarni saralash, saralash, saralashni hisoblash. Bezovsiz turda, bir xil elementlarning tartiblari kirishda ko'rinadigan darajada chiqishlarida bir xil bo'lishiga kafolat berilmaydi. Bunga tezkor saralash, uyali tartiblash, saralash navlari kiradi. Odatda, turg'un bo'lmagan algoritm barqaror tartiblash algoritmiga qaraganda tezroq.

Ichki va tashqi: Agar saralash kerak bo'lgan barcha ma'lumotlar asosiy xotirada yoki operativ xotirada bo'lsa, bunday tartib ichki tartibda bo'ladi. Ko'pincha kichik ma'lumotlar uchun foydalaning. Tashqi tartib - bu ma'lumotlar to'plami ko'pincha qattiq disk kabi yordamchi saqlash joyida bo'lib, ularning hammasini bir vaqtning o'zida xotirada saqlashning iloji yo'q. Odatda bir vaqtning o'zida juda katta miqdordagi ma'lumotlarni qayta ishlash uchun ishlatiladi. Rekursiv yoki rekursiv emas: Ba'zi saralash algoritmlari rekursivdir, masalan, Tez tartiblash va birlashtirish Tartibga solish (Ikkalasi ham ketma-ketlikni saralash uchun bo'linish va zabt etish usulidan foydalanadi), ba'zilari esa Kirish va Saralash kabi rekursivdir.