Parallel dasturlash

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.



monotonik ortish yoki kamayish tartibida

(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.

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.
Pufakchali saralash. Ketma-ket pufakchali tartiblash algoritmi saralanadigan ketma-ketlikdagi qoʻshni elementlarni taqqoslaydi va almashtiradi. Muvofiqlik uchun
(a₁, a₂, ..., a_n)
algoritm birinchi navbatda ketma-ket elementlar juftligi uchun n-1 asosiy “taqqoslash-almashtirish” amallarini bajaradi.
(a₁, a₂), (a₂, a₃), ..., (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’₁, a’₂, ..., 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