Algoritm tushunchasi

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
Birlashtirish bosqichi. Birlashtirish bosqichi asosiy pogʻonaga
yetib borganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q]
va A [q + 1, r] kichik massivlarni olsak, natijalarni A [p..r] massiviga
birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r]
massivlarning birlashmasidir
Merge Sort algoritmining ishlash prinsipi

1. 
   MergeSort(A, p, r)
   2. If p > r
   3. return;
   4. q = (p+r)/2;
   5. mergeSort(A, p, q)
   6. mergeSort(A, q+1, r)
   7. merge(A, p, q, r)
   Butun massivni saralash uchun MergeSort (A, 0, length (A) -1) ga
   murojaat qilishimiz kerak.
   

22 Quick Sort algoritmi. Algoritmning murakkabligi baholash
Tezkor saralash (Quick sort – Xoara metodi) koʻpincha qsort deb
nomlanadi (uning nomi C standart kutubxonasida) - bu ingliz kompyuter
olimi Toni Xoara tomonidan 1960-yilda Moskva davlat universitetida
ishlab yurgan paytlarida yaratilgan saralash algoritmi hisoblanadi.
Massivlarni saralash boʻyicha eng tez ma’lum boʻlgan universal
algoritmlardan biri: n elementni saralashda oʻrtacha O (nlogn)
almashinuv boʻladi. Bir qator kamchiliklar mavjudligi sababli amalda
odatda ba’zi bir oʻzgartirishlar bilan qoʻllaniladi.
QuickSort - bu toʻgʻridan-toʻgʻri almashinuvni
saralash algoritmining (Bubble Sort va Shaker Sort algoritmlari) sezilarli
darajada takomillashtirilgan variant boʻlib, u past samaradorligi bilan
ham tanilgan. Asosiy farq shundaki, birinchi navbatda, almashtirishlar
mumkin boʻlgan masofada amalga oshiriladi va har bir oʻtishdan keyin
elementlar ikkita mustaqil guruhga boʻlinadi. (Shunday qilib, eng
samarasiz toʻgʻridan-toʻgʻri saralash usulini takomillashtirish eng
samarali takomillashtirilgan usullardan birini beradi.)
Quicksort – bu ham “boʻlib
tashla va hukmronlik qil” prinsipiga asoslanuvchi algoritmdir.
Psevdokod - bu imperativ dasturlash tillarining
kalit soʻzlaridan foydalanadigan algoritmlarni tavsiflash uchun ixcham,
koʻpincha norasmiy til, ammo algoritmni tushunish uchun zarur
boʻlmagan tafsilotlar va oʻziga xos sintaksisni chiqarib tashlaydi.