Сортирање "пар-непар"
 | ||||||
|
У информатици, пар-непар сортирање (енгл. 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)
- Алгоритми и структуре података - Мило Томашевић
- Увод у програмирање - Милан Шкарић