16-ma’ruza. Sodda parallel algoritmlar

16.3. Parallel saralash usullari 
Saralash ma’lumotlarni qayta ishlashning odatiy muammolaridan biri 
boʻlib, odatda tartibsiz qiymatlar toʻplamining elementlarini tartibga 
solish muammosi sifatida tushuniladi. 
𝑆 = 𝑎
1
, 𝑎
2
, … , 𝑎
𝑛
monotonik ortish yoki kamayish tartibida 
𝑆~𝑆` = (𝑎`
1
, 𝑎`
2
, … , 𝑎
𝑛
`): 𝑎`
1
≤ 𝑎`
2
≤ ⋯ ≤ 𝑎`
𝑛
(bundan keyin qisqalik uchun barcha tushuntirishlar faqat oʻsish tartibida 
ma’lumotlarni tartiblash misolida beriladi). 
Saralash berish jarayonining hisoblash murakkabligi ancha yuqori. 
Shunday qilib, bir qator mashhur oddiy usullar uchun (pufakchali 
tartiblash va boshqalar) talab qilinadigan amallar soni tartiblangan 
ma’lumotlar soniga kvadratik bogʻliqlik bilan aniqlanadi. 
Samaraliroq algoritmlar uchun (Birlashtirib tartiblash, Shell saralash, 
QuickSort tartiblash) murakkablik qiymat bilan belgilanadi.
𝑇~𝑛log
2
𝑛
Bu ifoda, shuningdek, n ta qiymatlar toʻplamini saralash uchun zarur 
boʻlgan operatsiyalar sonining pastki chegarasini beradi; kamroq mehnat 
talab qiladigan algoritmlarni faqat muammoning alohida variantlari 
uchun olish mumkin. 

---

Saralash tezlashishi bir nechta (p>1) protsessorlar yordamida 
ta’minlanishi mumkin. Bu holda asl saralash toʻplami protsessorlar 
oʻrtasida taqsimlanadi; saralash jarayonida ma’lumotlar protsessorlar 
oʻrtasida uzatiladi va bir-biri bilan taqqoslanadi. Olingan (tartib qilingan) 
toʻplam odatda protsessorlar oʻrtasida ham taqsimlanadi; Bundan 
tashqari, protsessorlar uchun bunday boʻlinishni tizimlashtirish uchun u 
yoki bu ketma-ket raqamlash tizimi joriy etiladi va odatda tartiblash 
tugagach, pastroq raqamlarga ega boʻlgan protsessorlarda joylashgan 
qiymatlar qiymatlardan oshmasligi talab qilinadi.
Saralash muammosining batafsil tahlilini alohida koʻrib chiqish 
uchun qoldirib, bu yerda biz ichki tartiblashning ayrim mashhur usullarini 
parallel bajarish usullarini oʻrganishga toʻxtalamiz, bunda tartiblangan 
barcha 
ma’lumotlar 
kompyuterning operativ xotirasiga toʻliq 
joylashtirilishi mumkin.