Parallel dasturlash

void BubbleSort(double A[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i; j++)
compare_exchange(A[j], A[j + 1]);


Toq-juft almashtirish algoritmi. Toʻgʻridan-toʻgʻri shaklda pufakchali saralash algoritmi parallellashtirish uchun ancha murakkab - tartiblangan ma’lumotlar toʻplamining juft qiymatlarini taqqoslash qat’iy ketma-ketlikda amalga oshiriladi. Shu munosabat bilan parallel qoʻllash uchun bu algoritmning oʻzi emas, balki adabiyotda toq-juft transpozitsiya usuli sifatida tanilgan uning modifikatsiyasi qoʻllaniladi. Modifikatsiyaning mohiyati shundan iboratki, tartiblash algoritmiga usul iteratsiyasini bajarishning ikki xil qoidasi kiritiladi: tartiblash iteratsiyasining juft yoki toq soniga qarab ishlov berish uchun mos ravishda juft yoki toq indeksli elementlar tanlanadi. tanlangan qiymatlar har doim oʻng qoʻshnilari bilan amalga oshiriladi. Shunday qilib, barcha juftlik:
(a₁, a₂), (a₃, a₄), ..., (a_n-1, a_n) (juft n uchun),
va hatto iteratsiyalarda elementlar qayta ishlanadi
(a2, a3), (a4, a5), ..., (an-2, an-1).
Saralash iteratsiyasi n marta takrorlangandan soʻng, dastlabki ma’lumotlar toʻplami saralanadi.


// Ketma-ket toq-juft almashtirish algoritmi
void OddEvenSort(double A[], int n) {
for (int i = 1; i < n; i++) {
if (i % 2 == 1) { // toq iteratsiya
for (int j = 0; j < n/2 - 2; j++)
compare_exchange(A[2*j + 1], A[2*j + 2]);
if (n % 2 == 1) // toq n uchun oxirgi juftlikni solishtirish
compare_exchange(A[n - 2], A[n - 1]);
}
else // juft iteratsiya
for (int j = 1; j < n/2 - 1; j++)
compare_exchange(A[2*j], A[2*j + 1]);
}
}


Shell usulida saralash. Shell turining umumiy gʻoyasi saralangan ma’lumotlar toʻplamida bir-biridan yetarlicha uzoqda joylashgan qiymatlarni saralashning dastlabki bosqichlarida solishtirishdir. Saralash usulining ushbu modifikatsiyasi uzoqdagi tartibsiz qiymat juftlarini tezda almashtirish imkonini beradi (agar siz faqat qoʻshni elementlarni taqqoslasangiz, bunday juftlarni saralash odatda koʻp miqdordagi almashtirishlarni talab qiladi).
Usulning umumiy sxemasi quyidagicha. Algoritmning birinchi bosqichida n/2 juft (a_i, a_n/2+i) elementlari uchun tartiblangan. Keyinchalik, ikkinchi bosqichda toʻrt elementning n/4 guruhidagi elementlar (a_i, a_n/4+i, a_n/2+i, a_{3n/4 + i}) uchun tartiblangan. Uchinchi bosqichda elementlar sakkizta elementdan iborat n / 8 guruhda tartiblanadi va hokazo. Oxirgi bosqichda elementlar bir vaqtning oʻzida butun massivda tartibga solinadi (a₁, a₂, ..., a_n). Har bir bosqichda elementlarni guruhlarga ajratish uchun kiritish tartiblash usuli qoʻllaniladi. Koʻrib turganingizdek, Shell algoritmini takrorlashning umumiy soni log2n ga teng.
Toʻliqroq shaklda Shell algoritmini quyidagicha koʻrsatish mumkin.