Сортировка турниров
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июль 2012 г. ) |
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | О( п журнал п ) |
| Средняя производительность | О( п журнал п ) |
Турнирная сортировка — это алгоритм сортировки . Он совершенствует наивную сортировку выбором , используя очередь приоритетов для поиска следующего элемента в сортировке. При простой сортировке выбором требуется O ( n ) операций, чтобы выбрать следующий элемент из n элементов; при сортировке турнира требуется O(log n ) операций (после построения исходного турнира за O( n )). Турнирная сортировка — это разновидность пирамидальной сортировки .
Общее приложение
[ редактировать ]Сортировки выбора замены турнира используются для сбора начальных прогонов для внешних алгоритмов сортировки. Концептуально внешний файл считывается, и его элементы помещаются в приоритетную очередь до тех пор, пока очередь не заполнится. Затем минимальный элемент извлекается из очереди и записывается как часть первого запуска. Следующий входной элемент считывается и помещается в очередь, а min выбирается снова и добавляется в прогон. Есть небольшая хитрость: если новый элемент, помещаемый в очередь, меньше, чем последний элемент, добавленный в запуск, значение сортировки элемента увеличивается, поэтому он будет частью следующего запуска. В среднем время выполнения будет на 100 % дольше, чем емкость приоритетной очереди. [1]
Турнирные сортировки также могут использоваться при N-путевых слияниях.
Этимология
[ редактировать ]Название происходит от его сходства с турниром на выбывание , в котором множество игроков (или команд) играют в двусторонних матчах. В каждом матче сравниваются игроки, и победивший игрок получает право сыграть матч на следующем уровне. Иерархия продолжается до тех пор, пока финальный матч не определит окончательного победителя. Турнир определяет лучшего игрока, но игрок, проигравший в финальном матче, не может быть вторым по силе – он может уступать другим игрокам, которых победил победитель.
Схема сортировки
[ редактировать ]Sort numbers 72356014 (count = 8)
7_ __ __
\2_ \__ \__ 7_ 7_ __
2_/ \ __/ \ __/ \ \ \ \
3_ 2- __ 2- __ 2- __ 3- 5- 5- 7-
\3_/ \ \__/ \ \__/ \ \3_/ \ 5_/ \ __/ \ \
5_/ \ __/ \ __/ \ __/ \ \ \ \
\_0 \_1 \_2 \_3 \_4 \_5 \_67
6_ / / / / / / /
\0_ / 6_ / 6_ / __ / __ / / /
0_/ \ / \ / \ / \ / \ / / /
1_ 0- __ 1- 4- 4- 4- 6- 6-
\1_/ \1_/ 4_/ __/ __/
4_/ __/
Compares: 7 + 2 + 2 + 2 + 2 + 1 + 1 = 17
На
[ редактировать ]Onminmax(n log n) = (ln(n) / ln(2) - 1) * n + 1 On = (n - 1) + (n / 2) * (n / 4) + (n / (2 * 2) ) * (n / ( 4 * 2 )) + (n / (2 * 2 * 2) ) * (n / ( 4 * 2 * 2 )) + ... O8 = (8 - 1) + (8 / 2) * (8 / 4) + (8 / (2 * 2) ) * (8 / ( 4 * 2 )) O8 = 7 + 4 * 2 + 2 * 1 = 7 + 8 + 2 = 17
Реализации
[ редактировать ]Хаскелл
[ редактировать ]Ниже приведена реализация турнирной сортировки в Haskell , основанная на коде Scheme Степанова и Кершенбаума. [2]
import Data.Tree
-- | Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report.
tournamentSort :: Ord t
=> [t] -- ^ Input: an unsorted list
-> [t] -- ^ Result: sorted version of the input
tournamentSort alist
= go (pure<$>alist) -- first, wrap each element as a single-tree forest
where go [] = []
go trees = (rootLabel winner) : (go (subForest winner))
where winner = playTournament trees
-- | Adapted from `TOURNAMENT!` in the Stepanov and Kershenbaum report
playTournament :: Ord t
=> Forest t -- ^ Input forest
-> Tree t -- ^ The last promoted tree in the input
playTournament [tree] = tree
playTournament trees = playTournament (playRound trees [])
-- | Adapted from `TOURNAMENT-ROUND!` in the Stepanov and Kershenbaum report
playRound :: Ord t
=> Forest t -- ^ A forest of trees that have not yet competed in round
-> Forest t -- ^ A forest of trees that have won in round
-> Forest t -- ^ Output: a forest containing promoted versions
-- of the trees that won their games
playRound [] done = done
playRound [tree] done = tree:done
playRound (tree0:tree1:trees) done = playRound trees (winner:done)
where winner = playGame tree0 tree1
-- | Adapted from `TOURNAMENT-PLAY!` in the Stepanov and Kershenbaum report
playGame :: Ord t
=> Tree t -- ^ Input: ...
-> Tree t -- ^ ... two trees
-> Tree t -- ^ Result: `promote winner loser`, where `winner` is
-- the tree with the *lesser* root of the two inputs
playGame tree1 tree2
| rootLabel tree1 <= rootLabel tree2 = promote tree1 tree2
| otherwise = promote tree2 tree1
-- | Adapted from `GRAB!` in the Stepanov and Kershenbaum report
promote :: Tree t -- ^ The `winner`
-> Tree t -- ^ The `loser`
-> Tree t -- ^ Result: a tree whose root is the root of `winner`
-- and whose children are:
-- * `loser`,
-- * all the children of `winner`
promote winner loser = Node {
rootLabel = rootLabel winner,
subForest = loser : subForest winner}
main :: IO ()
main = print $ tournamentSort testList
where testList = [0, 1, 2, 3, 4, 5]
Javascript
[ редактировать ]// build first pyramid of minimal values
function pyramid_part1_buildPyramid(list, i_start, i_end, size, cmp, swap)
{
var i,j,k, k_end, lvl, lvlp1;
var pyramid = [];
i = i_start;
j = i_start+1;
k = 0;
lvl = 0;
pyramid[lvl] = [];
while (j<i_end)
{
if (cmp(list[i], list[j]))
{swap(list, i, j);}
pyramid[lvl][k] = i; i+=2; j+=2; k++;
}
if (i<i_end) // pokud je size liche cislo, pak pridej posledni prvek a preswapuj to
// (toho vyuziji pozdeji v part2)
{
if (cmp(list[i-2], list[i]))
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = list[i-2];
list[i-2] = tmp; movesAdd(4);
pyramid[lvl][k] = i;
}
else {if (cmp(list[i-1], list[i]))
{
tmp = list[i];
list[i ] = list[i-1];
list[i-1] = tmp; movesAdd(3);
}}
}
i_end = k;
lvlp1 = lvl + 1;
while (i_end>1)
{
pyramid[lvlp1] = [];
k = 0;
i = 0;
j = 1; // =i+1
while (j<i_end)
{
if (cmp(list[ pyramid[lvl][i] ], list[ pyramid[lvl][j] ]))
{pyramid[lvlp1][k] = pyramid[lvl][j]; i+=2; j+=2; k++; continue;}
else {pyramid[lvlp1][k] = pyramid[lvl][i]; i+=2; j+=2; k++; continue;}
}
if (i<i_end) {pyramid[lvlp1][k] = pyramid[lvl][i]; k++;}
lvl++;
lvlp1++;
i_end = k;
}
return [pyramid, lvl, pyramid[lvl][0], (size>>1)<<1 != size];
// return pyramid, last lvl, last index, boolean for odd-size)
}
function pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos)
{
var lvl, val2, empty = -1, a, b;
val2 = pyramid[0][pos];
for (lvl=0; lvl<lvl_end; lvl++)
{
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2;
continue;
}
b = pyramid[lvl][pos+1];
a = pyramid[lvl][pos];
pos = pos>>1;
if (b==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a; val2 = a;
}
}
return [pyramid, lvl_end, pyramid[lvl_end][0], bool];
}
// rebuild pyramid, rewrite branch by new value
function pyramid_part2_rebuildPyramid(pyramid, lvl_end, bool, list, cmp, i_end, i_endm3)
{
var cycles = 0;
var lvl, pos, val, val2, a, b, empty=-1;
val = pyramid[lvl_end][0];
pos = val>>1; // pozice zleva
if (bool==true && ((pos<<1)==i_endm3) && ((val & 0x01) == 0) )
// kdyz je size liche cislo a dojde k eliminaci n-2, tak posun posledni 2 cisla
{
bool = false;
list[val] = list[val+1];
list[val+1] = list[val+2]; movesAdd(2);
// je sude, pak vymen za liche a prepocitej porovnani
// (prepocitej vsechna nutna porovnani)
pyramid[0][pos] = val;
// pozn.: tento kod je prepsany na funkci, protoze by byl duplicitne
return
pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos);
}
else {if ((val & 0x01) == 0) // je sude, pak vymen za liche a prepocitej porovnani
{
pyramid[0][pos] = val + 1;
return pyramid_part3_rebuildPyramidEven(pyramid, lvl_end, bool, list, cmp, i_end, pos);
}
else { // je liche, pak odstran a prepocitej porovnani
val2 = empty;
pyramid[0][pos] = val2;
for (lvl=0; lvl<lvl_end; lvl++)
{
if ((pos & 0x01) == 0)
{
if (pos==pyramid[lvl].length-1)
{
pos = pos>>1;
pyramid[lvl+1][pos] = val2; //val2 = val2
continue;
}
a = pyramid[lvl][pos];
b = pyramid[lvl][pos+1];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (b!==empty)
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
pyramid[lvl+1][pos] = a;
val2 = a;
}
else {
a = pyramid[lvl][pos-1];
b = pyramid[lvl][pos];
pos = pos>>1;
if (a!==empty && b!==empty)
{
if (cmp(list[a], list[b]))
{pyramid[lvl+1][pos] = b; val2 = b; continue;}
else {pyramid[lvl+1][pos] = a; val2 = a; continue;}
}
if (a!==empty)
{pyramid[lvl+1][pos] = a; val2 = a; continue;}
pyramid[lvl+1][pos] = b;
val2 = b;
}
}
}}
return [pyramid, lvl_end, pyramid[lvl_end][0], bool];
}
// princip: vyber minimum z kazdeho paru, pak porovnej minima, minima minim ... az ziskas nejmensi cislo
// pak vyrad nejmensi cislo z pyramidy a propocitej celou vetev, opet ziskej minimum
function PyramidSelectSort(list, start, end, cmp)
{
var pyramid_data, i, x, y, endm3 = end-3, size = end - start;
x = list;
y = [];
pyramid_data = pyramid_part1_buildPyramid(x, start, end, size, cmp, swap);
// create pyramid of index from minimal values of pair
i = start;
y[i] = x[pyramid_data[2]]; movesAdd(1);
i++;
while (i<end)
{
pyramid_data = pyramid_part2_rebuildPyramid(
pyramid_data[0], pyramid_data[1], pyramid_data[3], x, cmp, end, endm3);
y[i] = x[pyramid_data[2]]; movesAdd(1);
i++;
}
return y;
}
// list = PyramidSelectSort(list, start, end, cmp);
// ---
// only for statistic info about moves, cycles, compares
function movesAdd(a) {glob.moves += a;};
function cyclesAdd() {glob.cycles++;};
function comparesAdd() {glob.cmps++;};
function cmp(a, b) {comparesAdd(); return a>b;}
// ---
list = [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4];
var glob = {time: 0, cmps: 0, cycles: 0, moves: 0, swaps: 0, start: 0, end: list.length, size: 0};
glob.size = glob.end - glob.start;
list = PyramidSelectSort(list, glob.start, glob.end, cmp);
/*
stable
fast
need list.size memory for state (true/false)
need list.size memory for new array
*/
Ссылки
[ редактировать ]- ^ Дональд Кнут , Искусство компьютерного программирования , Сортировка и поиск, Том 3, 1973. Аргумент «снегоочистителя». п. 254
- ^ Степанов, Александр; Кершенбаум, Аарон (1986). Использование деревьев турниров для сортировки (PDF) (технический отчет). Бруклин: Центр передовых технологий в области телекоммуникаций, Политехнический университет. Технический отчет CATT 86-13.
В эту статью включен текст , доступный по лицензии CC BY-SA 4.0 . - Кершенбаум и др. 1988, «Императивное программирование высшего порядка».
