Algoritmo de Ordenación por Sacudida

Este método, también conocido como método de ordenación por vibración, es una mejora del método de la burbuja, que mezcla sus dos versiones alternativamente, realizando una pasada de izquierda a derecha y a continuación otra de derecha a izquierda, recortándose los elementos a tratar por ambos extremos del vector.
Igual que en el caso de la burbuja, se puede aumentar la efectividad del método de la sacudida deteniendo la ordenación si se comprueba que en una pasada, tanto de izquierda a derecha como de derecha a izquierda, todos los elementos están ordenados. (Ver algoritmo de ordenación por sacudida con test).
El método de la sacudida se puede modificar para descartar más posiciones en los extremos, en lugar de una sola, como ocurre en los algoritmos anteriores. Si al realizar una pasada de derecha a izquierda el último intercambio afecta a las posiciones X y X+1, significa que los valores comprendidos entre las posiciones 1 y X ya están ordenados, por lo que no será necesario evaluar dichas posiciones en la siguiente pasada. Análogamente, si al realizar una pasada de izquierda a derecha el último intercambio afecta a las posiciones X-1 y X, significa que los valores comprendidos entre las posiciones X y N ya están ordenados, por lo que no será necesario evaluar dichas posiciones en la siguiente pasada. (Ver algoritmo de ordenación por sacudida con salto).

PSEUDOCÓDIGO

Ordenación sacudida

    MÓDULO ordenacion_sacudida

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, IZQ, DER enteras
           AUX de tipo T
    INICIO
           IZQ ← 1
           DER ← N
           Mientras ( IZQ ≠ DER)  hacer
              ** pasada de izquierda a derecha
              Para I desde IZQ hasta DER-1
                 Si ( V(I) > V(I+1) ) entonces
                    AUX ← V(I)
                    V(I) ← V(I+1)
                    V(I+1) ← AUX
                 fin-si
              fin-para
                 DER ← DER-1
                 Si ( IZQ ≠ DER ) entonces
                    ** pasada de derecha a izquierda
                    Para I desde DER hasta IZQ+1 con incremento -1
                        Si ( V(I-1) > V(I) ) entonces
                           AUX ← V(I-1)
                           V(I-1) ← V(I)
                           V(I) ← AUX
                        fin-si
                    fin-para
                    IZQ ← IZQ+1
                 fin-si
           fin-mientras
    FIN

Ordenación por sacudida con test de comprobación

    MÓDULO ordenacion_sacudida_test

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, IZQ, DER, CEN enteras
           SEGUIR lógica
    INICIO
           IZQ ← 1
           DER ← N
           SEGUIR ← VERDADERO
           Mientras ( (IZQ ≠ DER)   y   (SEGUIR = VERDADERO) ) hacer
              SEGUIR ← FALSO
              Para I desde IZQ hasta DER-1
                  Si ( V(I) > V(I+1) ) entonces
                     AUX ← V(I)
                     V(I) ← V(I+1)
                     V(I+1) ← AUX
                     SEGUIR ← VERDADERO
                  fin-si
              fin-para
              DER ← DER-1
              Si ( (IZQ ≠ DER)   y   (SEGUIR =VERDADERO) ) entonces
                  SEGUIR ← FALSO
                  Para I desde DER hasta IZQ+1 con incremento -1
                      Si ( V(I-1) > V(I) ) entonces
                         AUX ← V(I-1)
                         V(I-1) ← V(I)
                         V(I) ← AUX
                         SEGUIR ← VERDADERO
                      fin-si
                  fin-para
                  IZQ ← IZQ+1
              fin-si
           fin-mientras
    FIN

Ordenación por sacudida con salto

    MÓDULO ordenacion_sacudida_salto

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe N entera
       VARIABLES
           I, IZQ, DER, K enteras
           AUX de tipo T
    INICIO
           IZQ ← 1
           DER ← N
           K ← 1
           Mientras ( IZQ < DER ) hacer
              Para I desde IZQ hasta DER-1
                  Si ( V(I) > V(I+1) ) entonces
                      AUX ← V(I)
                      V(I) ← V(I+1)
                      V(I+1) ← AUX
                      K ← I+1
                  fin-si
              fin-para
              DER ← K-1
              Si ( IZQ < DER ) entonces
                  Para I desde DER hasta IZQ+1 con incremento -1
                      Si ( V(I-1) > V(I) ) entonces
                           AUX ← V(I-1)
                           V(I-1) ← V(I)
                           V(I) ← AUX
                           K ← I-1
                      fin-si
                  fin-para
                  IZQ ← K+1
              fin-si
           fin-mientras
    FIN

CÓDIGO C

Ordenación sacudida

sacudida(int *v, int n)
{
int izq=0, der=0, i=0, aux=0;

izq=0;
der=n-1;

	while (izq!=der){
		for(i=izq;iv[i+1]){
				aux=v[i];
				v[i]=v[i+1];
				v[i+1]=aux;
			}
		}
	der--;
		if(izq!=der){
			for(i=der;i>izq;i--){
				if(v[i-1]>v[i]){
					aux=v[i-1];
					v[i-1]=v[i];
					v[i]=aux;
				}
			}
		izq++;
		}
	}
}

Ordenación por sacudida con salto

sacudida_test(int v[], int n){
int i, izq, der, cen, aux;
int seguir;
izq=0;
der=n-1;
seguir=1;
	while((izq!=der) && (seguir==1)){

	seguir=0;
	for(i=izq;i v[i+1]){
		aux=v[i];
		v[i]=v[i+1];
		v[i+1]=aux;
		seguir=1;		
		}
	}
der--;

           
	if ((izq!=der) && (seguir==1)){
	seguir=0;
	for(i=der;i>izq;i--){
	if(v[i-1]>v[i]){
	aux=v[i-1];
	v[i-1]=v[i];
	v[i]=aux;
	seguir=1;	
	}
	}
	izq++;
	}
	}
}

Volver al índice

Volver a Búsqueda y Ordenación Interna



Comentarios

Publicar un comentario

Entradas populares de este blog

Algoritmo de ordenación por mezcla natural

El método de ordenación por mezcla natural, al igual que el de clasificación por mezcla directa, realiza sucesivas particiones y mezclas, pero intenta aprovechar el orden existente en los datos, considerando secuencias de longitud variable. En cada iteración, en primer lugar se separan los registros del fichero origen en otros dos ficheros, copiando en cada uno las secuencias de registros consecutivos que ya están ordenados entre sí en el origen. A continuación, se mezclan los dos ficheros auxiliares, obteniendo de cada dos tramos ordenados otro ordenado. El proceso de ordenación se repite hasta que se obtiene un solo tramo. PSEUDOCÓDIGO MÓDULO Clasificacion_mezcla_natural DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES L entera ** num. de subsecuencias ordenadas mez...
Leer más

Algoritmo de ordenación por mezcla directa

La ordenación por mezcla directa realiza sucesivas operaciones de partición y mezcla, que producen secuencias ordenadas de longitud cada vez mayor. La primera partición se hace en secuencias de longitud 1, y la fusión correspondiente produce sobre el archivo inicial secuencias ordenadas de longitud 2. En cada nueva partición y fusión se duplica la longitud de las secuencias ordenadas obtenidas. El proceso termina cuando la longitud de la secuencia ordenada es mayor o igual que la longitud del archivo a ordenar. PSEUDOCÓDIGO MÓDULO Ordenacion_mezcla_directa DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES NUM_ELEM entero ** num. de registros a ordenar TAM_SEC entero ** tamaño de la secuencia actual INICIO TAM_SEC ← 1 ...
Leer más

Algoritmo de Ordenación por Intercambio Directo (Burbuja)

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente. Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones. El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector: Se comparan los valores de las posicione...
Leer más