4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Birlashtirib saralash (Merge sort)



Yüklə 0,64 Mb.
Pdf görüntüsü
səhifə1/8
tarix17.02.2023
ölçüsü0,64 Mb.
#84776
  1   2   3   4   5   6   7   8
4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Bir



63 
4-§ Birlashtirib saralash algoritmlari 
Merge sort algoritmi. Birlashtirib saralash (Merge sort) – 
tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash 
―boʻlib tashla va hukmronlik qil‖ prinsipining yaxshi namunasidir. 
Birinchidan, vazifa bir nechta kichik topshiriqlarga boʻlinadi. Keyin 
ushbu vazifalar rekursiv chaqiruv yordamida yoki toʻgʻridan-toʻgʻri 
ularning hajmi yetarlicha kichik boʻlsa hal qilinadi. Nihoyat, ularning 
yechimlari birlashtirilib, asl muammoning echimi olinadi. 
Algoritmning bajarilishi. Saralash muammosini hal qilish uchun 
uch bosqich quyidagicha boʻladi: 
1. Saralanadigan massiv taxminan bir xil oʻlchamdagi ikki qismga 
boʻlinadi; 
2. Olingan qismlarning har biri alohida saralanadi (masalan, xuddi 
shu algoritm boʻyicha saralanadi); 
3. Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi. 
Bu eng mashhur saralash algoritmlaridan biri boʻlib, rekursiv 
algoritmlarni yaratishda ishonchni rivojlantirishning ajoyib usuli 
hisoblanadi. 
“Boʻlib tashla va hukmronlik qil” strategiyasi. ―Boʻlib tashla va 
hukmronlik qil‖ strategiyasi yordamida muammoni qismiy jarayonlarga 
ajratamiz. Har bir kichik topshiriq uchun yechimga ega boʻlsak, pastki 
vazifalarni yechish uchun pastki vazifalardan olingan natijalarni 
"birlashtiramiz". 
Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p 
indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan 
kichik qismini ajratishdir. 
“Boʻlib tashlash”. Agar q qiymati p va r orasida boʻlsa, biz A 
[p..r] massivni ikkita A [p..q] va A [q + 1, r] kichik massivlarga 
boʻlishimiz mumkin. 
“Hukmronlik qilish”. ―Hukmronlik qilish‖ bosqichida biz ikkala 
A [p..q] va A [q + 1, r] kichik massivlarni saralashga harakat qilamiz. 
Agar hali ham boshlangʻich darajaga yetib bormagan boʻlsak, yana 
ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz. 


64 

Yüklə 0,64 Mb.

Dostları ilə paylaş:
  1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin