O’zbekiston respublikasi oliy va orta

Tez tartiblash va birlashtirish saralash

• 
  Tez Sortlash va Merge Sort ikkisi ham bo'linish va zabt etish asosida saralash algoritmlari bir xil asosiy printsipga ega - muammoni ikki yoki undan ortiq kichik muammolarga bo'lish va keyin ularni rekursiv ravishda echish. Biroq, ular birlashtirish tartiblari va ishlash jihatidan farq qiladi. Tez tartiblash odatda boshqa algoritmlarga qaraganda yaxshiroq va tezroq bo'ladi, shu jumladan kichik ma'lumotlar to'plamiga kelsak, Sort birlashishi ma'lumotlar to'plamining turidan qat'i nazar, muvofiqlikni saqlaydi. Tez tartiblashtirish massivlar uchun, afzal bog'langan ro'yxatlar uchun birlashtirish tartibiga esa eng mos keladi.
  
• 
  "Tez tartiblash" algoritmida tartiblash rekursiv ravishda amalga oshiriladi va har bir rekursiv chaqiruv uchun stack joyi kerak. Birlashtirish uchun bitta xotira
  

maydoni bundan mustasno, birlashtirish uchun qo'shimcha joy talab qilinmaydi. Bu joyida tartiblash algoritmi bo'lganligi sababli, tartiblash uchun qo'shimcha joy talab qilinmaydi. Aslida, u massivni ajratish va birlashtirishda bir xil qatordan foydalanadi. Merge Sort-da, boshqa tomondan, faylda yoki massivda ma'lumotlarni taqdim etishning bir necha usullari mavjud, shuning uchun qo'shimcha joy talab qiladigan sub-fayllar yoki bir xil o'lchamdagi massivlar kabi ish joylari kerak.

• 
  Tez tartiblash uchun eng yomon xatti-harakatlar bo'linish muvozanatlanmagan holatlarda yuzaga keladi, bu alimentni ajratish uchun qaysi elementlardan foydalanilganiga bog'liq, bu holda algoritm asimptotik tarzda asta-sekin kiritish tartibida ishlaydi. Tez saralashning eng yomon holati O (n2) dir va mashq sifatida qoldiriladi. Biroq, to'g'ri burilishni tanlash orqali oldini olish mumkin. Boshqa tomondan, Merge Sortning eng yomon holati, u maksimal taqqoslashni amalga oshirishi kerak bo'lgan holatlarda yuzaga keladi. Birlashtirish uchun chiziqli ishlashni hisobga olsak, Birlashtirish Saralashining eng yomon holati O (n log2 n) dir.
  
• 
  Tez Sortlash va Birlashtirish Saralash algoritmlari ikkiga bo'linish va saralash usullariga asoslangan bo'lishiga qaramay, ular bo'linish va birlashtirish protseduralarini bajarish uchun ishlatiladigan usullar bilan farqlanadi. Tez tartiblash uchun asosiy ish ro'yxatni quyi ro'yxatlarni saralashdan oldin bo'lib o'tadigan ikkita quyi ro'yxatlarga bo'lishdir. Birlashtirish Saralash uchun asosiy ish quyi ro'yxatlar tartiblanganidan keyin sodir bo'ladigan ikkita pastki ro'yxatlarni birlashtirishdir. Birlashtirish Sort ikkita sub-massivni birlashtirish uchun vaqtincha qatorni talab qiladi, shu bilan Tez Saralash uchun qo'shimcha bo'sh joy talab qilinmaydi, bu esa Marge Sort-ga nisbatan ko'proq joyni tejashga yordam beradi.