Reja: kirish I. Bob. Saralash algoritimi haqida tushuncha

Tezkor saralash(Quick Sort) algoritmi.
1964 yilda Charlz Hoar tamonidan taklif qilingan.
Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi
sohasida yetuk mutaxassis. Uning “Tezkor saralash” algorit-
mi saralash bo’yicha eng ommobop algoritm.
Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.
T tipidagi a [l… r] massivi har bir a [l… q] elementi yoki a [q] ga teng, bu esa o'z navbatida a [q + 1… r] pastki qatorning biron bir elementidan oshmaydi. Bo'linish protsedurasi davomida indeks hisoblanadi.
A [l… q] va [q + 1… r] kichik massivlari quicksort protsedurasiga rekursiv chaqiruv yordamida saralanadi.
Ichki massivlar joyida tartiblanganligi sababli ularni birlashtirish uchun hech qanday harakat talab qilinmaydi: butun [l… r] qatori saralangan.
void quicksort(a: T[n], int l, int r)
if l < r
int q = partition(a, l, r)
quicksort(a, l, q)
quicksort(a, q + 1, r)
Butun qatorni saralash uchun siz tezkor (a, 0, uzunlik [a] -1) bajarishingiz kerak.

Massivni ajratish

Tartiblash algoritmining asosiy bosqichi - bu T tipidagi [l… r] massivi elementlarini qayta tartibga soluvchi, ajratish protsedurasi. Bo'linish quyidagi strategiya yordamida amalga oshiriladi. Avvalo, ajratuvchi element sifatida a [(l + r) / 2] element ixtiyoriy ravishda tanlanadi. Keyinchalik, skanerlash massivning chap uchidan boshlanadi, u qiymat ajratuvchi elementdan oshib ketadigan element topilguncha davom etadi, so'ngra skanerlash massivning o'ng uchidan boshlab amalga oshiriladi va u element topilguncha davom etadi. bo'linishni kamaytiradigan qiymat bo'yicha. Ko'rinish to'xtatilgan ikkala element ham, shubhasiz, bo'lingan massivda joyida emas va shuning uchun ular almashtirilgan. Shunday qilib, chap ko'rsatkichning chap tomonida ajratuvchi qiymati bo'yicha kattaroq bitta element qolmaganiga va o'ng ko'rsatkichning o'ng tomonida birdan kam bo'ladigan bitta element qolmaganligiga ishonch hosil qilguncha davom etamiz. ajratuvchining qiymati.

V o'zgaruvchisi ajratuvchi elementning qiymatini saqlaydi a [(l + r) / 2], a i va j navbati bilan chap va o'ng ko'rish ko'rsatkichlari. Bo'linish tsikli i qiymatini oshiradi va j qiymatini 1 ga kamaytiradi va i ning chap qismidagi hech bir element v dan katta va j ning o'ng tomonidagi element v dan kam bo'lmasligi sharti buzilmaydi. Ko'rsatkichlarning qiymatlari kesishishi bilan bo'linish protsedurasi tugaydi.