Lajittelu parillinen-pariton
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. marraskuuta 2018 tarkistetusta
versiosta . tarkastukset vaativat
10 muokkausta .
Tämä suhteellisen yksinkertainen lajittelualgoritmi, joka on suunniteltu käytettäväksi rinnakkaisissa prosessoreissa, on muunnelma kuplalajittelusta . Muokkauksen ydin on verrata taulukon elementtejä parillisten ja parittomien indeksien alla seuraaviin elementteihin itsenäisesti. Algoritmin esitteli ensimmäisen kerran N. Haberman vuonna 1972.
Algoritmin kuvaus
Lippu on asetettu osoittamaan, onko taulukko lajiteltu. Iteroinnin alussa se asetetaan "true"-tilaan, sitten jokainen pariton elementti tarkistetaan seuraavaan, ja jos ne ovat väärässä järjestyksessä (edellinen on suurempi kuin seuraava), ne ovat vaihdetaan, ja lippu asetetaan "false"-tilaan. Sama tehdään tasaisilla elementeillä. Algoritmi ei pysähdy ennen kuin lippu pysyy tosi.
malli < tyyppinimi T , koko_t N >
void oddEvenSorting ( T ( & array )[ N ]) {
for ( koko_t i = 0 ; i < N ; i ++ ) {
// (i % 2) ? 0 : 1 palauttaa arvon 1, jos i on parillinen, 0, jos i ei ole parillinen
arvolle ( koko_t j = ( i % 2 ) ? 0 : 1 ; j + 1 < N ; j += 2 ) {
if ( array [ j ] > array [ j + 1 ]) {
std :: swap ( taulukko [ j ], taulukko [ j + 1 ]);
}
}
}
}
function oddEvenSorting ( array ) {
const arrayLength = array . pituus ; //taulukon pituus
for ( olkoon i = 0 ; i < arrayLength ; i ++ ) {
// (i % 2) ? 0 : 1 palauttaa arvon 0, jos i on parillinen, 1 jos i ei ole parillinen
for ( olkoon j = ( i % 2 ) ? 0 : 1 ; j < arrayLength - 1 ; j += 2 ) {
if ( array [ j ] > taulukko [ j + 1 ])
[ taulukko [ j ], taulukko [ j + 1 ]] = [ taulukko [ j + 1 ], taulukko [ j ]]; //swap
}
}
return array ;
}
Toteutus PHP:ssä
funktio FunctionOddEvenSort ( & $array )
{
$lengthArray = count ( $array );
$lajiteltu = false ;
while ( ! $lajiteltu ) {
$lajiteltu = tosi ;
for ( $i = 0 ; $i < $lengthArray - 1 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$lajiteltu = false ;
}
}
for ( $i = 1 ; $i < $lengthArray - 2 ; $i += 2 ) {
if ( $array [ $i ] > $array [ $i + 1 ]) {
FunctionSwapVariables ( $array [ $i ], $array [ $i + 1 ]);
$lajiteltu = false ;
}
}
}
// for ($x = 0; $x < $lengthArray; $x++) {
// if (!$lajiteltu) {
// $lajiteltu = tosi;
// for ($i = 0; $i < $lengthArray - 1; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $lajiteltu = false;
//}
//}
// for ($i = 1; $i < $lengthArray - 2; $i += 2) {
// if ($array[$i] > $array[$i + 1]) {
// FunctionSwapVariables($array[$i], $array[$i + 1]);
// $lajiteltu = false;
//}
//}
// } else return 'Matriisi onnistuneesti lajiteltu';
//}
}
Kirjallisuus
- Knut D. Ohjelmoinnin taito. Volume 3. Lajittelu ja haku. - Moskova: 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 (saatavilla Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)