Clasificación par-impar
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la
versión revisada el 2 de noviembre de 2018; las comprobaciones requieren
10 ediciones .
Diseñado para su uso en procesadores paralelos, este algoritmo de clasificación relativamente simple es una modificación de la clasificación de burbuja . La esencia de la modificación es comparar elementos de matriz bajo índices pares e impares con elementos subsiguientes de forma independiente. El algoritmo fue introducido por primera vez por N. Haberman en 1972.
Descripción del algoritmo
Se establece una bandera para indicar si la matriz está ordenada. Al comienzo de la iteración, se establece en el estado "verdadero", luego cada elemento impar se compara con el siguiente, y si están en el orden incorrecto (el anterior es mayor que el siguiente), entonces son intercambiado, y la bandera se establece en el estado "falso". Lo mismo se hace con elementos pares. El algoritmo no deja de ejecutarse hasta que la bandera permanece verdadera.
Implementación en C++
plantilla < nombre de tipo T , tamaño_t N >
void ordenación pares impares ( T ( & matriz )[ N ]) {
para ( tamaño_t i = 0 ; i < N ; i ++ ) {
// (yo % 2) ? 0 : 1 devuelve 1 si i es par, 0 si i no es par
para ( size_t j = ( i % 2 ) ? 0 : 1 ; j + 1 < N ; j += 2 ) {
si ( matriz [ j ] > matriz [ j + 1 ]) {
std :: intercambio ( matriz [ j ], matriz [ j + 1 ]);
}
}
}
}
función ordenación pares impares ( matriz ) {
const arrayLength = matriz . longitud ; //longitud del arreglo
para ( let i = 0 ; i < arrayLength ; i ++ ) {
// (i % 2) ? 0 : 1 devuelve 0 si i es par, 1 si i no es par
para ( let j = ( i % 2 ) ? 0 : 1 ; j < arrayLength - 1 ; j += 2 ) {
if ( array [ j ] > matriz [ j + 1 ])
[ matriz [ j ], matriz [ j + 1 ]] = [ matriz [ j + 1 ], matriz [ j ]]; //intercambiar
}
}
matriz de retorno ; }
Implementación en PHP
función FunciónOddEvenSort ( & $array )
{
$longitudArray = cuenta ( $array );
$ordenado = falso ;
while ( ! $ordenado ) {
$ordenado = verdadero ;
for ( $i = 0 ; $i < $arreglolongitud - 1 ; $i += 2 ) {
if ( $matriz [ $i ] > $matriz [ $i + 1 ]) {
FunctionSwapVariables ( $matriz [ $i ], $matriz [ $i + 1 ]);
$ordenado = falso ;
}
}
for ( $i = 1 ; $i < $arreglolongitud - 2 ; $i += 2 ) {
if ( $matriz [ $i ] > $matriz [ $i + 1 ]) {
FunctionSwapVariables ( $matriz [ $i ], $matriz [ $i + 1 ]);
$ordenado = falso ;
}
}
}
// para ($x = 0; $x < $arreglolongitud; $x++) {
// si (!$ordenado) {
// $ordenado = verdadero;
// for ($i = 0; $i < $arreglolongitud - 1; $i += 2) {
// si ($matriz[$i] > $matriz[$i + 1]) {
// FunctionSwapVariables($matriz[$i], $matriz[$i + 1]);
// $ordenado = falso;
// }
// }
// para ($i = 1; $i < $longitudArray - 2; $i += 2) {
// si ($matriz[$i] > $matriz[$i + 1]) {
// FunctionSwapVariables($matriz[$i], $matriz[$i + 1]);
// $ordenado = falso;
// }
// }
// } else devuelve 'Array clasificado con éxito';
// }
}
Literatura
- Knut D. El arte de la programación. Volumen 3. Clasificación y búsqueda. - Moscú: 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 (disponible como Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151)