Řazení sudé-liché
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od
verze recenzované 2. listopadu 2018; kontroly vyžadují
10 úprav .
Tento relativně jednoduchý třídicí algoritmus, navržený pro použití na paralelních procesorech, je modifikací bublinového třídění . Podstatou úpravy je nezávislé porovnání prvků pole pod sudými a lichými indexy s následujícími prvky. Algoritmus poprvé představil N. Haberman v roce 1972.
Popis algoritmu
Je nastaven příznak, který označuje, zda je pole seřazeno. Na začátku iterace se nastaví do stavu „true“, pak se každý lichý prvek zkontroluje proti dalšímu, a pokud jsou ve špatném pořadí (předchozí je větší než následující), pak jsou zaměněno a příznak je nastaven na stav "false". Totéž se provádí se sudými prvky. Algoritmus se nezastaví, dokud příznak nezůstane pravdivý.
Implementace v C++
šablona < typename T , size_t N >
void oddEvenSorting ( T ( & pole )[ N ]) {
for ( size_t i = 0 ; i < N ; i ++ ) {
// (i % 2) ? 0 : 1 vrátí 1, pokud je i sudé, 0, pokud i není sudé
pro ( size_t j = ( i % 2 ) ? 0 : 1 ; j + 1 < N ; j += 2 ) {
if ( pole [ j ] > pole [ j + 1 ]) {
std :: swap ( pole [ j ], pole [ j + 1 ]);
}
}
}
}
function oddEvenSorting ( pole ) {
const poleLength = pole . délka ; //délka pole
pro ( nechť i = 0 ; i < délka pole ; i ++ ) {
// (i % 2) ? 0 : 1 vrátí 0, pokud je i sudé, 1, pokud i není sudé
pro ( nechť j = ( i % 2 ) ? 0 : 1 ; j < délka pole - 1 ; j += 2 ) {
if ( pole [ j ] > pole [ j + 1 ])
[ pole [ j ], pole [ j + 1 ]] = [ pole [ j + 1 ], pole [ j ]]; //swap
}
}
return pole ;
}
Implementace v PHP
funkce FunctionOddEvenSort ( & $array )
{
$lengthArray = count ( $pole );
$seřazeno = false ;
zatímco ( ! $sorted ) {
$seřazeno = true ;
for ( $i = 0 ; $i < $lengthArray - 1 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$seřazeno = false ;
}
}
for ( $i = 1 ; $i < $lengthArray - 2 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$seřazeno = false ;
}
}
}
// for ($x = 0; $x < $lengthArray; $x++) {
// if (!$sorted) {
// $tříděno = true;
// for ($i = 0; $i < $lengthArray - 1; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $tříděno = false;
// }
// }
// for ($i = 1; $i < $lengthArray - 2; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $tříděno = false;
// }
// }
// } else return 'Pole úspěšně seřazeno';
// }
}
Literatura
- Knut D. Umění programování. Svazek 3. Třídění a vyhledávání. - Moskva: Williams, 2000. - ISBN 978-5-8459-0082-1 .
- N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)", CMU Computer Science Report (dostupná jako technická zpráva AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)