Metodos De Ordenamiento

Algoritmos de Ordenación

En este documento veremos:
Recordatorio de los Algoritmos O(n2)
Algoritmos O(n log n)
Una cota inferior de la ordenación por comparación de elementos

1. AlgoritmosO(n2)
Algoritmo de ordenación BURBUJA

void BURBUJA(int[] A)
{
for (int j = A.Length - 1; j >= 1; j--)
for (int i = 0; i < j; i++)
if (A[i] > A[i + 1])Swap(A, i, i + 1);
}

Propiedades:
Realiza intercambio de elementos consecutivos
Notar que siempre intercambia elementos de una posición i con su posición adyacente i + 1.
Es estable
Determinadopor la propiedad anterior. Vea 1.1.
Es (n2) y por tanto (n2)
Esto es porque independientemente de la cantidad de intercambios que haga, siempre se ejecutarán íntegramente los dos ciclos que sonlos que aportan n(n - 1)/2 operaciones determinando su orden cuadrático
Si el arreglo ya está ordenado no realiza ningún intercambio
Esto es evidente, nunca se cumpliría la condición A[i] > A[i + 1]Realiza ordenación en el lugar (sobre el mismo arreglo)

Mejora de este algoritmo:

Su mejora radica en que si en una pasada del ciclo más interno no se realiza intercambios terminar. Esto esdebido a que si no se realiza intercambio es porque la parte que queda por ordenar ya lo está y por tanto no es necesario continuar.

void BURBUJA_MEJORADO(int[] A)
{
for (int j = A.Length - 1;j >= 1; j--)
{
bool hubo_cambio = false;

for (int i = 0; i < j; i++)
if (A[i] > A[i + 1])
{
Swap(A, i, i + 1);hubo_cambio = true;
}

if (!hubo_cambio) break;
}
}



Algoritmo de Ordenación MINIMOS_SUCESIVOS

void MINIMOS_SUCESIVOS(int[] A)
{
for (int i = 0; i {
int pos_min = i;

for (int j = i + 1; j < A.Length; j++)
if (A[j] < A[pos_min])
pos_min = j;

if (pos_min != i)...

Leer documento completo

Regístrate para leer el documento completo.