Rendezés páros-páratlan
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. november 2-án felülvizsgált
verziótól ; az ellenőrzésekhez
10 szerkesztés szükséges .
Ez a párhuzamos processzorokon való használatra tervezett viszonylag egyszerű rendezési algoritmus a buborékos rendezés egy módosítása . A módosítás lényege, hogy a páros és páratlan indexek alatti tömbelemeket egymástól függetlenül összehasonlítjuk a következő elemekkel. Az algoritmust először N. Haberman vezette be 1972-ben.
Az algoritmus leírása
Egy zászló van beállítva, amely jelzi, hogy a tömb rendezve van-e. Az iteráció elején „igaz” állapotba állítjuk, majd minden páratlan elemet a következőhöz viszonyítunk, és ha rossz sorrendben vannak (az előző nagyobb, mint a következő), akkor felcserélik, és a zászló "hamis" állapotba kerül. Ugyanez történik páros elemekkel. Az algoritmus futása addig nem áll le, amíg a zászló igaz marad.
sablon < típusnév T , méret_t N >
void oddEvenSorting ( T ( & array )[ N ]) {
for ( méret_t i = 0 ; i < N ; i ++ ) {
// (i % 2) ? 0 : 1 1 értéket ad vissza, ha i páros, 0 értéket, ha i nem páros
for ( size_t j = ( i % 2 ) ? 0 : 1 ; j + 1 < N ; j += 2 ) {
if ( array [ j ] > array [ j + 1 ]) {
std :: csere ( tömb [ j ], tömb [ j + 1 ]);
}
}
}
}
function oddEvenSorting ( array ) {
const arrayLength = array . hossza ; //tömb hossza
for ( legyen i = 0 ; i < arrayLength ; i ++ ) {
// (i % 2) ? 0 : 1 0 értéket ad vissza, ha i páros, 1 értéket, ha i nem páros
for ( legyen j = ( i % 2 ) ? 0 : 1 ; j < arrayLength - 1 ; j += 2 ) {
if ( tömb [ j ] > tömb [ j + 1 ])
[ tömb [ j ], tömb [ j + 1 ]] = [ tömb [ j + 1 ], tömb [ j ]]; //csere
}
}
return array ;
}
Megvalósítás PHP-ben
függvény FunctionOddEvenSort ( & $array )
{
$lengthArray = count ( $tömb );
$rendezett = false ;
while ( ! $sorted ) {
$rendezett = igaz ;
for ( $i = 0 ; $i < $lengthArray - 1 ; $i += 2 ) {
if ( $tömb [ $i ] > $tömb [ $i + 1 ]) {
FunctionSwapVariables ( $tömb [ $i ], $tömb [ $i + 1 ]);
$rendezett = false ;
}
}
for ( $i = 1 ; $i < $lengthArray - 2 ; $i += 2 ) {
if ( $tömb [ $i ] > $tömb [ $i + 1 ]) {
FunctionSwapVariables ( $tömb [ $i ], $tömb [ $i + 1 ]);
$rendezett = false ;
}
}
}
// for ($x = 0; $x < $lengthArray; $x++) {
// if (!$sorted) {
// $rendezett = igaz;
// for ($i = 0; $i < $lengthArray - 1; $i += 2) {
// if ($tömb[$i] > $tömb[$i + 1]) {
// FunctionSwapVariables($tömb[$i], $tömb[$i + 1]);
// $sorted = false;
// }
// }
// for ($i = 1; $i < $lengthArray - 2; $i += 2) {
// if ($tömb[$i] > $tömb[$i + 1]) {
// FunctionSwapVariables($tömb[$i], $tömb[$i + 1]);
// $sorted = false;
// }
// }
// } else return 'A tömb sikeresen rendezve';
// }
}
Irodalom
- Knut D. A programozás művészete. 3. kötet. Rendezés és keresés. - Moszkva: 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 (Ad-759 248 Technical Report, National Technical Information Service, US Commerce, 5285 Port Royal Rd Sprigfield) VA 22151)