Ma’lumotlarni saralash algoritmlari. Saralash tushunchasi va uning vazifasi Saralash algoritmi


Download 80.4 Kb.
bet5/5
Sana25.12.2022
Hajmi80.4 Kb.
#1065171
1   2   3   4   5
Bog'liq
Ma’lumotlarni saralash algoritmlari

Merge sort

  • Birlashtirish saralash algoritmi eng mashhur saralash algoritmlaridan biri boʻlib, “Boʻl va zabt et” algoritmiga asoslangan.
  • Bu yerda muammo bir nechta kichik muammolarga bo'linadi. Har bir kichik muammo alohida hal qilinadi. Nihoyat, yakuniy yechimni shakllantirish uchun kichik muammolar birlashtiriladi.
  • “Bo‘l va zabt et” texnikasidan foydalanib, masalani kichik muammolarga ajratamiz. Har bir kichik muammoning yechimi tayyor bo'lgach, biz asosiy muammoni hal qilish uchun kichik muammolardan olingan natijalarni "birlashtiramiz".
  • Faraz qilaylik, biz A massivni saralashimiz kerak edi. Kichik muammo bu massivning p indeksidan boshlanib, r indeksi bilan tugaydigan, A[p..r] deb belgilangan kichik bo‘limini saralash bo‘ladi.
  • Agar q p va r o‘rtasidagi yarim yo‘l nuqtasi bo‘lsa, u holda A[p..r] pastki massivni ikkita A[p..q] va A[q+1, r] massivlarga ajratishimiz mumkin.
  • Zabt etish bosqichida biz A[p..q] va A[q+1, r] pastki massivlarni ham saralashga harakat qilamiz. Agar biz hali ham asosiy holatga etib bormagan bo'lsak, biz yana ikkala pastki qatorlarni ajratamiz va ularni saralashga harakat qilamiz.
  • Zabt etish bosqichi asosiy bosqichga yetganda va biz A[p..r] massiv uchun ikkita tartiblangan A[p..q] va A[q+1, r] pastki massivlarni olamiz, natijalarni tartiblangan A massivini yaratish orqali birlashtiramiz. A[p..q] va A[q+1, r] ikkita tartiblangan pastki massivlardan [p..r].

Download 80.4 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling