Сортирање "пар-непар"
У информатици, пар-непар сортирање (енгл. Odd–even sort)[1] представља релативно једноставан алгоритам за сортирање, који је првенствено развијен за употребу на паралелним процесорима са локалном повезаношћу. Он спада у групу алгоритама који сортирају поређењем и сличан је сортирању мехуром, са којим дели многе карактеристике. Идеја је да се пореде сви парови индекса (непар, пар) суседних елемената низа и, ако је тај пар у погрешном поретку (први већи од другог), елементи мењају места. У следећем кораку се поступак понавља за парове индекса (пар, непар). Кораци се смењују између те две врсте парова док се низ не сортира.
 | ||||||
|
Сортирање на паралелним процесорима
уредиКод паралелних процесора, који имају једну вредност по процесору и локалну повезаност с лева у десно, процесори истовремено извршавају упоређивање и размену са својим суседима, наизменично са паровима непар-пар и пар-непар. Овај алгоритам је представио Н. Хаберман 1972. године.[2] и показало се да је ефикасан на оваквим процесорима.
Алгоритам побољшава ефикасност у случају рада на машинама које подржавају више вредности по процесору. У тзв. алгоритму Бодет-Стевенсоновог пар-непар спајања-раздвајања (енгл. Baudet–Stevenson odd–even merge-splitting) сваки процесор сортира свој подниз, користећи било који ефикасан алгоритам за сортирање, а затим врши спајање сортираног подниза са својим суседом, који врши упаривање (наизменично узимајући једну, па другу врсту парова у сваком кораку).[3]
Бачерово пар-непар сортирање спајањем
уредиСличан, али ефикаснији алгоритам за сортирање је тзв. Бачерово пар-непар сортирање спајањем, који користи операције упореди–размени и перфектно мешање.[4] Овај метод показао се ефикасним на паралелним процесорима далеког домета конекције.[5]
Сортирање процесорских листа
уреди
На паралелним процесорима, са једним елементом по процесору и само левом-десном локалном комшиском везом, процесори истовремено раде операције упоређивања и замене, алтернирајући између непарно/парне и парне/непарне парове. Овај алгоритам је оригинално представљен, и показано је да ефикасно ради на оваквим процесорима од старане Хабермана 1972. године.
Алгоритам
уредиИспод је представљен алгоритам за једнопроцесорске машине. Попут сортирања мехуром он је једноставан али недовољно ефикасан. Подразумевамо да индексирање почиње од нуле.
/* Assumes a is an array of values to be sorted. */
var sorted = false;
while(!sorted)
{
sorted=true;
for(var i = 1; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
for(var i = 0; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
}
Имплементација
уредиПсеудо код[6]
function oddEvenSort(list) {
function swap( list, i, j ){
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
var sorted = false;
while(!sorted)
{
sorted = true;
for(var i = 1; i < list.length-1; i += 2)
{
if(list[i] > list[i+1])
{
swap(list, i, i+1);
sorted = false;
}
}
for(var i = 0; i < list.length-1; i += 2)
{
if(list[i] > list[i+1])
{
swap(list, i, i+1);
sorted = false;
}
}
}
}
Имплементација у програмском језк C++:
template <class T>
void OddEvenSort (T a[], int n)
{
for (int i = 0 ; i < n ; i++)
{
if (i & 1) // 'i' је непар
{
for (int j = 2 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
else
{
for (int j = 1 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
}
}
Иплементација у ПХП:
function oddEvenSorting(&$a) {
$n = count($a);
$sorted = false;
while (!$sorted) {
$sorted = true;
for ($i = 1; $i < ($n - 1); $i += 2) {
if ($a[$i] > $a[$i + 1]) {
list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
if ($sorted) $sorted = false;
}
}
for ($i = 0; $i < ($n - 1); $i += 2) {
if ($a[$i] > $a[$i + 1]) {
list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
if ($sorted) $sorted = false;
}
}
}
}
Имплементација у Пајтону:
def oddevenSort(x):
sorted = False
while not sorted:
sorted = True
for i in range(0, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
for i in range(1, len(x)-1, 2):
if x[i] > x[i+1]:
x[i], x[i+1] = x[i+1], x[i]
sorted = False
return x
Пример имплементације у Матлабу:
function x = oddevenSort(x)
sorted = false;
n = length(x);
while ~sorted
sorted = true;
for ii=1:2:n-1
if x(ii) > x(ii+1)
[x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
sorted = false;
end
end
for ii=2:2:n-1
if x(ii) > x(ii+1)
[x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
sorted = false;
end
end
end
Референце
уреди- ^ Пхиллипс, Малцолм. „Арраy Сортинг”. Хомепагес.ихуг.цо.нз. Архивирано из оригинала 28. 10. 2011. г. Приступљено 3. 8. 2011.
- ^ Н. Хаберман (1972) "Параллел Неигхбор Сорт (ор тхе Глорy оф тхе Индуцтион Принципле)," ЦМУ Цомпутер Сциенце Репорт (аваилабле ас Тецхницал репорт АД-759 248, Натионал Тецхницал Информатион Сервице, УС Департмент оф Цоммерце, 5285 Порт Роyал Рд Спригфиелд ВА 22151).
- ^ С. Лаксхмиварахан; С. К. Дхалл & L. L. Миллер (1984), Франз L. Алт & Марсхалл C. Yовитс, ур., „Параллел Сортинг Алгоритхмс”, Адванцес ин цомпутерс, Ацадемиц Пресс, 23: 295—351, ИСБН 978-0-12-012123-6
- ^ Роберт Седгеwицк (2003). Алгоритхмс ин Јава, Партс 1-4 (3рд изд.). Аддисон-Wеслеy Профессионал. стр. 454—464. ИСБН 978-0-201-36120-9.
- ^ Аллен Кент & Wиллиамс, Јамес Г. (1993). Енцyцлопедиа оф Цомпутер Сциенце анд Тецхнологy: Супплемент 14. ЦРЦ Пресс. стр. 33—38. ИСБН 978-0-8247-2282-1.
- ^ Шкарић, Милан. Увод у програмирање. Београд: Микро књига. „Имплементација Парног непарног сортирања у програмском језику ц”
Литература
уреди- Аллен Кент & Wиллиамс, Јамес Г. (1993). Енцyцлопедиа оф Цомпутер Сциенце анд Тецхнологy: Супплемент 14. ЦРЦ Пресс. стр. 33—38. ИСБН 978-0-8247-2282-1.
- Седгеwицк, Роберт (2003). Алгоритхмс ин Јава, Партс 1-4 (3рд изд.). Аддисон-Wеслеy Профессионал. стр. 454—464. ИСБН 978-0-201-36120-9.
- Интродуцтионс то алгоритхмс -Тхомас Х. Цормен,Цхарлес Е. Леисерсон,Роналд L. Ривест,Цлиффорд Стеин, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
- Алгоритми и структуре података - Мило Томашевић
- Увод у програмирање - Милан Шкарић