logo

MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI

Загружено в:

15.08.2023

Скачано:

0

Размер:

777.8544921875 KB
“ MA’LUMOTLARNI SARALASH. SARALASHNI 
BIRLASHTIRISH(SILYANIE)USULI  ”
Reja:
1.   Birlashtirib saralash (Merge sort)
2. Dastur kodi
3. Birlashtirish algoritmi qay tarzda ishlashi haqida  • Algoritm  nima   degan  
savolga,  u  asosiy  tushuncha  
sifatida  qabul qilinganligidan, 
uning faqat tavsifi beriladi, 
ya’ni biror maqsadga 
erishishga yoki qandaydir  
masalani  yechishga  qaratilgan 
 ko’rsatmalarning  
(buyruqlarning)  aniq, 
tushunarli, chekli hamda to’liq 
tizimi tushuniladi.  Birlashtirib saralash (Merge sort)  
• 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 
y echimlari  birlashtirilib,  asl  muammoning  echimi 
olinadi.    • “ 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.  FUNKTSIYANI BOSQICHMA-BOSQICH BIRLASHTIRISH  • Biz  yuqorida  keltirilgan  qadamlardan  funksiyani  bosqichma -
bosqich  birlashtirishni  ko ’ rib  chiqishimiz  mumkin :  avvalo  saralash 
pastki  qatorlarining  dublikat  nusxalarini  yaratib  oldik 
kkeyingqadamimizda kichik va joriy massiv indeksini aniqlab oldik .
• Birinchi  qadamda  for  sikl  operatori  va  massivdan  foydalangan 
bo’lsak.  Keyingi  qadamda  bir  nuqta  tanlanib  olinib  boshiga 
tenglashtiriladi ya’ni [p..r] oraliqda bo’lishi mumkin biz bunda while 
oparatoriga  masofa  belgilab  olamiz  i  va  j  lar  orqali  va  yana  shart 
oparatoriga  murojat  qilamiz  va  so’nggi  qadamda  elementlardan 
birortasi qolmasa [p..r]ga joylashtirishimiz mumkin.  BIRLASHTIRISH FUNKTSIYASI QUYIDAGICHA ISHLAYDI:  ETIBORINGIZ 
UCHUN RAHMAT.

“ MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI ” Reja: 1. Birlashtirib saralash (Merge sort) 2. Dastur kodi 3. Birlashtirish algoritmi qay tarzda ishlashi haqida

• Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi.

Birlashtirib saralash (Merge sort) • 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 y echimlari birlashtirilib, asl muammoning echimi olinadi.

• “ 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.