Metodos De Ordenar Vectores

METODOS PARA ORDENAR VECTORES

1 ShellSort

Este método funciona de la siguiente manera:

• Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.

• Después de que los primeros K subgrupos han sido ordenados, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.

• Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.

• Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.

• Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.

• El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1. Algoritmo:

void shellSort(int a[], int h)

{

int i;

while (h > 0)

{ for (i = h-1; i<n; i++)

{

int B = a[i];

int j = i;

for (j = i; (j >= h) && (a[j - h] > B); j -= h)

{ a[j] = a[j - h];}

a[j] = B;

}

h = h / 2;

}

2 MergeSort

El algoritmo Merge divide el arreglo original en dos arreglos y los coloca en arreglos separados. Cada arreglo es recursivamente ordenado y finalmente se unen los arreglos en un arreglo ordenado. Como cualquiera de los algoritmos de ordenamiento recursivo el algoritmo Merge tiene complejidad de O(n log n). Fue desarrollado por John Von Neumann. Algoritmo.-

void ordenarMezcla(TipoEle A[], int izq, int der)

{ if ( izq < der )

{ centro = ( izq + der ) % 2;

ordenarMezcla( A, izq, centro );

ordenarMezcla( A, centro+1, der);

intercalar( A, izq, centro, der );

}

}

void intercalar(TipoEle A[], int a, int c, int b )

{ k = 0;

i = a;

j = c + 1;

n = b - a;

while ( i < c + 1 ) && ( j < b + 1 )

{ if ( A[i] < A[j] )

{ B[k] = A[i];

i = i + 1;

}

else

{ B[k] = A[j];

j = j + 1;

}

k = k + 1;

};

while ( i < c + 1 )

{ B[k] = A[i];

i++;

k++;

};

while ( j < b + 1 )

{ B[k] = A[j];

j++;

k++;

};

i = a;

for ( k = 0; k < n; i++ )

{ A[i] = B[k];

i++;

};

3 QuickSort

La ordenación rápida se basa en la idea de las particiones. El procedimiento general es seleccionar un valor llamado COMPARANDO y entonces dividir el array en dos partes. En un lado todos los elementos mayores o iguales al valor de particion y en otro todos los elementos menores que el valor. Este proceso se repite en cada parte restante hasta que el array esté ordenado. Algoritmo:

void ordenar (int vect[], int ind_izq, int ind_der)

{

int i, j; /* variables indice del vector */

int elem; /* contiene un elemento del vector */

i = ind_izq;

j = ind_der;

elem = vect[(ind_izq+ind_der)/2];

do

{while (vect[i] < elem) //recorrido del vector hacia la derecha

i++;

while (elem < vect[j]) // recorrido del vector hacia la izquierda

j--;

if (i <= j) /* intercambiar */

{ int aux; /* variable auxiliar */

...