11-Маъруза: Merge sort (birlashtirib saralash) va uning ishlash prinsiplari. Ikkilik birlashtirish va to'planganlarni saralash. Alifbo tartibida saralash algoritmi. Reja

11-Маъруза:
Merge sort (birlashtirib saralash) va uning ishlash prinsiplari.
Ikkilik birlashtirish va to'planganlarni saralash.
Alifbo tartibida saralash algoritmi.
Reja:
1. To´g´ridan-to´g´ri qo´shish usuli bilan saralash algoritmi.
2.Tanlash orqali saralash algoritmi.
3.Pufaksimon saralash va tez saralash (quiksort) algoritmlari
https://www.youtube.com/watch?v=BAK-vy4xiF4
https://www.youtube.com/watch?v=GT3uBCjYB3k
Kalit so‘zlar: 
binar saralash usuli, piramidali saralash usuli, tez saralash usuli, birlashtirish orqali saralash: ikki yo’lli birlashtirish, yuqoriga yo’naltirilgan, pastga yo’naltirilgan.
Mergesort effektiv tartiblash algoritmlaridan biri bo’lib uning ishlash prinsipi «bo’lib tashla va hukmronlik qil» (divide and conquer) tamoyiliga asoslanadi. U tartiblash jarayonida ro’yhatni (array’ni) ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, ikki tarafini yana ikkiga bo’ladi, … ikki tarafda bitta son (yoki bir tarafda bitta son) qolguncha bo’lishda davom etadi. Keyin ularni tartiblashni boshlaydi. Bittalik yonma-yon turgan sonlar tartiblanib bo’lingach, ularni array sifatida birlashtiriladi. Birlashtirilgan, yonma-yon turgan ikkita elementli array’lar o’zaro tartiblanadi va birlashtiriladi. Keyin to’rtta elementli arraylar o’zaro tartiblanib birlashtiriladi. Shu tariqa bo’laklar bitta butun array’ga yig’ilguncha davom etadi.
Mergesort’ning effektivligi – uning ishlash vaqtida, time complexity – O(n log n). Insertion sort va Selection sort bilan solishtirganda, ishlash vaqti ancha samarali.
Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

• Berilgan arrayni rekursiv holda teng ikkita qismlarga bo’lib chiqish. Bu qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo’lib qolguncha davom etadi.
• Hosil bo’lgan arraylarni qaytib birlashtirib chiqish va bir vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash.

https://medium.com/@algorithmuzb/merge-sort-birlashtirib-saralash-a870fae60e1e
Heapsort – binary heap ma’lumotlar tuzilmasi asosidagi tartiblash algoritmi. Biz heap har doim ma’lum bir tartibga rioya qilishini bilganimiz uchun, uning bu hususiyatidan tartiblashda foydalanishimiz – array’ning eng katta qiymatini olib uni array’ning ohiriga qo’yib borish orqali array’ni tartiblashimiz mumkin.
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.

https://walker.uz/2020/10/05/heapsort-binary-heap-asosida-tartiblash/

• https://visualgo.net/bn/sorting
• https://toptal.com/developers/sorting...
• Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni almashtirishlar ko’p vaqt va katta hajmdagi xotira sarfini talab qiladi.
• Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari almashtirilib, elementlar o’z joyida qoladi.
• Bu usul adreslar jadvalini saralash usuli deyiladi.

Mustaqil ishlash uchun savollar:
1. Saralashning yaxshilangan usullarini sanab bering.
2. Daraxt yordamida (binar) saralash usulida foydalaniladigan ma’lumotlar tuzilmasi
3. Piramidali saralash usuli nima uchun shunday nomlangan?
4. Tez saralash usulining samaradorligini baholang
5. Birlashtirish orqali saralash usullarini tushuntirib bering va ularning samaradorligini alohida baholang.
Foydalanilgan adabiyotlar:
1.[EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.
2.[UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
3.[UZ] Boynazarov I.M., To’xtayeva M.Sh. Ma’lumotlar tuzilmasi fanidan mustaqil ishlarni bajarish uchun uslubiy ko’rsatma. -Samarqand, TATU Samarqand filiali, 2018 y. 53 bet.
4.[RU] Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.
5.[RU] Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов. - Краснодар: КубГАУ. 2000. - 261 с., ил.
Havolalar
https://studfile.net/preview/7882389/page:12/
https://newtravelers.ru/uz/bluetooth/puzyrkovaya-sortirovka-si-puzyrkovaya-sortirovka-bubble-sort-a.html
https://hozir.org/saralash-usullari-va-ularning-qollanilishi-saralashning-yaxshi.html
https://medium.com/@algorithmuzb/saralash-algoritmlari-tanishuv-e7a36f5bb8b1
https://donolik.com/72783154
file:///C:/Users/Azex_PC/Downloads/algoritmga_kirish_fanidan_laboratoriya_mashgulotlari_boyicha_uslubiy_kursatma.pdf
THANK YOU
that you took the time to watch