1. Saralash algoritmi haqida qisqacha

Heap sort saralash algoritmi

Reja:

1. Saralash algoritmi haqida qisqacha.

2. Heapsort ning ishlash tartibi.

3. Heapsort saralash algoritmi bo’yicha misollar.

Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktabda jismoniy tarbiya dars boshida bolalar bo`ylariga qarab safda turishadi.

Me`yor topshirish jarayonida esa sinf jurnalidagi familiyalar ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alvabit tartibida saralanadi.

Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi

Tartiblangan ma'lumotlar hammaga yoqadi. Saralash ma'lumotlarni kerakli ketma-ketlikda tartibga solish imkonini beradi, masalan, o'sish yoki kamayish tartibida.

Saralash algoritmlari taqqoslash operatorlari yordamida ro'yxatlar va massivlarda berilgan ma'lumotlarni tartiblab beradi. Bu operatorlar massiv elementlariga qo’llaniladi va ularning ma’lumotlar strukturasidagi tartibini belgilaydi. Misol uchun, quyidagi belgilar (1-rasm)

ASCII kodi bo'yicha o'sish tartibida saralangan. Saralash jarayonida elementlar bir-biri bilan taqqoslanadi. ASCII jadvalidagi belgining qiymati qanchalik katta bo'lsa, u ro'yxat boshidan shunchalik uzoqroqda joylashgan bo'ladi.




Biz bu bo’limda saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni nazarda tutamiz va bu kabi saralash algoritmlarining olti xili ni ko’rib chiqamiz:

1. 
   Selection sort (Tanlab saralash)
   
2. 
   Bubble sort (Pufakchali saralash)
   
3. 
   Insertion sort (Joylashtirib saralash)
   
4. 
   Quick sort (Tezkor saralash)
   
5. 
   Merge sort (Qo’shib saralash)
   
6. 
   Radix sort
   

Ularning deyarli hammasi (6-sidan tashqari) ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi.


“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.

Heapsort ning ishlash tartibi:

Heapify. Tartiblanmagan array’dan max heap yasab olamiz. Binary heap’da hisoblashni osonlashtirish uchun array[0] ni bo’sh qoldirgan bo’lsak, bu safar array[0] ishtirok etadi. Sababi hozirgi holatda bizda array tayyor beriladi va qo’shimcha heap’ni qo’shimcha o’zgaruvchiga yig’masdan array’ning o’zida yasaymiz (in-place).

Swap. Root’dagi maksimum qiymatli elementni ohirgi element bilan almashtiramiz va uni heap’dan chiqaramiz.

Reheapify. Ohirgi element root bo’lgach, u albatta o’z joyini topishi kerak. Heap tartibini to’g’rilaymiz.

Repeat. Ikkinchi va uchinchi qadamlarni heap’da bitta element qolguncha davom ettiramiz.

Vizualizatsiya

Bizdagi max heap

[50, 47, 30, 33, 9, 13, 24, 20, 12, 5]
array’ni tartiblashni boshlaymiz.

Arrayning birinchi va ohirgi elementlari – 50 va 5 ning o’rnini almashtiramiz va 50 ni heapdan chiqaramiz. Keyin 5 ni joyiga qo’yish uchun reheapify – qaytadan heap tartibini to’g’rilaymiz

.