6 ta saralash algoritmlarini taqqoslash: qabariq, tanlash, yig'ish, kiritish, birlashtirish va tez

Saralash algoritmlarini samaradorligini baholash mumkinmi?

Ha mumkin.
Saralash algoritmining samaradorligini baholash mezonlari fazo va vaqt murakkabligi hisoblanadi.

Fazoviy murakkablik

Algoritmni bajarish uchun ishlatiladigan xotira hajmini ko'rsatadi. Kosmik murakkablik yordamchi xotira va kirish xotirasini o'z ichiga oladi.
Yordamchi xotira - kirish ma'lumotlariga qo'shimcha ravishda algoritm egallagan qo'shimcha joy. Algoritmlarning fazoviy murakkabligini hisoblashda hisobga olinadi.

Vaqtning murakkabligi

Kirish ma'lumotlarini hisobga olgan holda algoritm vazifani bajaradigan vaqtni bildiradi. Uni quyidagi belgilar yordamida ifodalash mumkin:

1. 
   Omega belgisi (Ō)
   
2. 
   Katta "O" belgisi (O)
   
3. 
   Teta yozuvi (T)
   

Jadvalda yuqorida aytib o'tilgan algoritmlarning murakkabligi taxminiy ko'rsatilgan.

Saralash algoritmi	Eng yomon ish vaqti	O'rtacha ish vaqti	Eng yaxshi holatda ish vaqti	Fazoviy murakkablik
pufakchali tartiblash	n ^ 2	n ^ 2	n	bitta
Tanlash tartibi	n ^ 2	n ^ 2	n ^ 2	bitta
Tez tartiblash	n ^ 2	n log n	n log n	n log n
Uyumni tartiblash	n log n	n log n	n log n	bitta
Kiritish tartibi	n ^ 2	n ^ 2	n	bitta
Birlashtirish tartibi	n log n	n log n	n log n	n

***
Har bir saralash algoritmi o'ziga xos vaqt va makon murakkabligiga ega. Vazifalarga qarab, taqdim etilgan algoritmlarning har qandayidan foydalanishingiz mumkin. Lekin mening sub'ektiv fikrimcha, tez tartiblash eng yaxshi algoritmdir. U pivotni tanlash imkonini beradi va massivni 3 qismga ajratadi: kichik, teng va pivotdan katta.