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

...