Sortering lige-ulige
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den
version , der blev gennemgået den 2. november 2018; checks kræver
10 redigeringer .
Designet til brug på parallelle processorer, er denne relativt enkle sorteringsalgoritme en modifikation af boblesortering . Essensen af modifikationen er at sammenligne array-elementer under lige og ulige indekser med efterfølgende elementer uafhængigt. Algoritmen blev først introduceret af N. Haberman i 1972.
Beskrivelse af algoritmen
Et flag er sat til at angive, om arrayet er sorteret. I begyndelsen af iterationen sættes den til "sand" tilstand, derefter kontrolleres hvert ulige element mod det næste, og hvis de er i den forkerte rækkefølge (det forrige er større end det næste), så er de byttet, og flaget er sat til "falsk" tilstand. Det samme gøres med lige elementer. Algoritmen stopper ikke med at køre, før flaget forbliver sandt.
Implementering i C++
skabelon < typenavn T , størrelse_t N >
void oddEvenSorting ( T ( & array )[ N ]) {
for ( størrelse_t i = 0 ; i < N ; i ++ ) {
// (i % 2) ? 0 : 1 returnerer 1 hvis i er lige, 0 hvis i ikke er lige
for ( 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 = matrix . længde ; //array længde
for ( lad i = 0 ; i < arrayLength ; i ++ ) {
// (i % 2) ? 0 : 1 returnerer 0 hvis i er lige, 1 hvis i ikke er lige
for ( lad 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
}
}
returner matrix ;
}
Implementering i PHP
funktion FunctionOddEvenSort ( & $array )
{
$lengthArray = count ( $array );
$sorted = falsk ;
while ( ! $sorted ) {
$sorteret = sand ;
for ( $i = 0 ; $i < $lengthArray - 1 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$sorted = falsk ;
}
}
for ( $i = 1 ; $i < $lengthArray - 2 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$sorted = falsk ;
}
}
}
// for ($x = 0; $x < $lengthArray; $x++) {
// if (!$sorted) {
// $sorteret = sand;
// for ($i = 0; $i < $lengthArray - 1; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $sorted = falsk;
// }
// }
// for ($i = 1; $i < $lengthArray - 2; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $sorted = falsk;
// }
// }
// } else return 'Array vellykket sorteret';
// }
}
Litteratur
- Knut D. Kunsten at programmere. Bind 3. Sortering og søgning. - 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 (tilgængelig som teknisk rapport AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)