Лекция 2 Алгоритмы сортировки и поиска

4) Yakuniy hisoblash tartiblash protsedurasini yaratish uchun barcha uchta protsedurani birlashtirish

Protseduralarni sanash-Sartlash(A,n,m).
Tizimga kirish:
• A – 0 dan m-1 oralig‘idagi butun sonlar massivi,
• n – A massivdagi elementlar soni,
• m – A massividagi qiymatlar diapazonini belgilaydi.
Chiqish: saralangan tartibda A massivining elementlarini o'z ichiga olgan B massivi.
Jarayon bosqichlari:
1. Count-Keys-Equal(A,n,m) protsedurasini chaqiring va uning natijasini teng massiv sifatida saqlang.
2. Count-Keys-Less(teng,m) protsedurasini chaqiring va uning natijasini kamroq massiv sifatida saqlang.
3. Rearrange(A,less,n,m) protsedurasini chaqiring va uning natijasini B massivida saqlang.
4. B massivini qaytaring.

Saralash ish vaqtini hisoblash

• Count-Keys-Equal (D) protseduralarining ishlash vaqti asosidam+n)), Sanoq tugmalari (D()m)) va Qayta tartibga solish (D(m+n)), sanash-Sortlash protsedurasi vaqtida bajarilganligini olamizd(m+n), yoki shunchaki D(n), Agarmdoimiyni ifodalaydi.
• Hisoblash tartibioshib ketadipastki chegara Ō(njurnal2n) solishtirma tartiblash, chunki u hech qachon tartiblash kalitlarini bir-biri bilan solishtirmaydi.
• Saralash tugmalari uchun ishlatiladimassivni indekslash, bu tartiblash tugmalari kichik butun son qiymatlari bo'lsa, bu juda realdir.
• Agar tartiblash tugmalari haqiqiy sonlar yoki, masalan, belgilar qatorlari bo'lsa, hisoblash tartibidan foydalaningbu taqiqlangan.

Saralash barqarorligi

Hisoblash tartibi yana bir muhim xususiyatga ega. Bu barqaror: bir xil saralash tugmachasiga ega elementlar kirish massividagi kabi chiqish massivida paydo bo'ladi.
Boshqacha qilib aytadigan bo'lsak, stablesort tugmalari teng bo'lgan ikkita elementga duch kelganda, kirish massivida birinchi bo'lib chiqadigan elementni chiqish massiviga birinchi bo'lib qo'yish orqali noaniqlikni hal qiladi.