16-ma’ruza. Sodda parallel algoritmlar

Pufakchali saralash. 
Ketma-ket pufakchali tartiblash algoritmi 
saralanadigan ketma-ketlikdagi qoʻshni elementlarni taqqoslaydi va 
almashtiradi. Muvofiqlik uchun 
(a
1
, a
2
, ..., a
n
) 
algoritm birinchi navbatda ketma-ket elementlar juftligi uchun n-1 asosiy 
“taqqoslash-almashtirish” amallarini bajaradi. 
(a
1
, a
2
), (a
2
, a
3
), ..., (a
n-1
, a
n
). 
Natijada, algoritmning birinchi iteratsiyasidan soʻng, eng katta 
element ketma-ketlikning oxiriga ("suzuvchi") koʻchiriladi. Bundan 
tashqari, oʻzgartirilgan ketma-ketlikdagi oxirgi elementni koʻrib 
chiqishdan chiqarib tashlash mumkin va yuqorida tavsiflangan tartib 
ketma-ketlikning qolgan qismiga nisbatan qoʻllaniladi. 
(a’
1
, a’
2
, ..., a’
n-1
). 
Koʻrib turganingizdek, ketma-ketlik n-1 iteratsiyadan keyin 
tartiblanadi. Agar turning har qanday iteratsiyasi davomida tartiblangan 
ma’lumotlar ketma-ketligida hech qanday oʻzgarish boʻlmasa, qabariqli 
saralash samaradorligini algoritmni tugatish orqali oshirish mumkin. 
// Ketma-ket pufakchali tartiblash algoritmi