Sortering jämnt-udda
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 2 november 2018; kontroller kräver
10 redigeringar .
Designad för användning på parallella processorer, är denna relativt enkla sorteringsalgoritm en modifiering av bubbelsortering . Kärnan i modifieringen är att jämföra arrayelement under jämna och udda index med efterföljande element oberoende. Algoritmen introducerades först av N. Haberman 1972.
Beskrivning av algoritmen
En flagga sätts för att indikera om arrayen är sorterad. I början av iterationen sätts den till "sant" tillstånd, sedan kontrolleras varje udda element mot nästa, och om de är i fel ordning (det föregående är större än nästa), så är de bytt, och flaggan sätts till "falskt" tillstånd. Samma sak görs med jämna element. Algoritmen slutar inte köras förrän flaggan förblir sann.
Implementering i C++
mall < typnamn T , storlek_t N >
void oddEvenSorting ( T ( & array )[ N ]) {
för ( storlek_t i = 0 ; i < N ; i ++ ) {
// (i % 2) ? 0 : 1 returnerar 1 om i är jämnt, 0 om i inte är jämnt
för ( size_t j = ( i % 2 ) ? 0 : 1 ; j + 1 < N ; j += 2 ) {
if ( array [ j ] > array [ j + 1 ]) {
std :: swap ( array [ j ], array [ j + 1 ]);
}
}
}
}
function oddEvenSorting ( array ) {
const arrayLength = array . längd ; //arraylängd
för ( låt i = 0 ; i < arrayLength ; i ++ ) {
// (i % 2) ? 0 : 1 returnerar 0 om i är jämnt, 1 om i inte är jämnt
för ( låt j = ( i % 2 ) ? 0 : 1 ; j < arrayLength - 1 ; j += 2 ) {
if ( array [ j ] > array [ j + 1 ])
[ array [ j ], array [ j + 1 ]] = [ array [ j + 1 ], array [ j ]]; //swap
}
}
returnera array ;
}
Implementering i PHP
funktion FunctionOddEvenSort ( & $array )
{
$lengthArray = count ( $array );
$sorted = false ;
while ( ! $sorted ) {
$sorted = sant ;
for ( $i = 0 ; $i < $lengthArray - 1 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$sorted = false ;
}
}
för ( $i = 1 ; $i < $lengthArray - 2 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$sorted = false ;
}
}
}
// för ($x = 0; $x < $lengthArray; $x++) {
// if (!$sorted) {
// $sorted = sant;
// för ($i = 0; $i < $lengthArray - 1; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $sorted = false;
// }
// }
// för ($i = 1; $i < $lengthArray - 2; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $sorted = false;
// }
// }
// } else return 'Array framgångsrikt sorterad';
// }
}
Litteratur
- Knut D. Konsten att programmera. Volym 3. Sortering och sökning. - Moskva: Williams, 2000. - ISBN 978-5-8459-0082-1 .
- N. Haberman (1972) "Parallell Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (tillgänglig som teknisk rapport AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)