Metodos De Ordenamiento

Método de Burbuja

void Burbuja( int A[], int n)
{
int i,j;
for( i=0; i < n-1; i++ )
for( j=n-1; j > i; j--)
if( A[j] < A[j-1] )
Intercambia( &A[j], &A[j-1] );
}

Método de Selección
El ordenamiento por selección (Selection Sort en inglés)  que requiere O(n2) operaciones para ordenaruna lista de n elementos.    La idea básica de este algoritmo consiste en buscar el menor elemento en el arreglo y colocarlo en primera posición. Luego se busca el segundo elemento más pequeño del arreglo y se lo coloca en segunda posición. El proceso continua hasta que todos los elementos del arreglo hayan sido ordenados.

void Selección( int A[], int n )
{
int i, j, imin;
for( i=0; i <n-1; i++ ) {
imin = i;
for( j = i+1; j > n; j++ )
if( A[j] < A[imin] )
imin = j;
intercambia( &A[i], &A[imin] );
}
}

Método de Inserción
La Inserción, es un método de clasificación que busca el ordenamiento de elementos no ordenados en memoria, en la posición corespondiente dentro delconjunto de elementos ya ordenados.
La Insercion Directa se basa en tomar el primer elemento de la  parte desordenada, y buscar la posición que le corresponde dentro de la sección ordenada

void Inserción( int A[], int n )
{
int i,j;
for( i=1; i < n; i++ ) {
j:= i;
while( j > 0 && A[j] < A[j-1] ) {
Intercambia( &A[j], &A[j-1] );
j--
}
}
}

QuickSort

Dadoun arreglo desordenado de n elementos

Selecciona un valor v del arreglo, llamado pivote, y re-arregla los elementos del arreglo de manera que todos los elementos menores que v queden colocados antes que v y todos los elementos mayores o iguales que v queden colocados después que v.

void quicksort( int A[], int i, int j )
{
if( desde A[i] hasta A[j] existen al
menos dos llaves distintas ) {Seleccionar un pivote, v
Permutar A[i], ...,A[j], tal que,
para algún k entre i+1 y j,
A[i], ..., A[k-1] < v y
A[k], . . . , A[j] ³ v
quicksort( A, i, k-1 );
quicksort( A, k, j );
}
}

QuickSort: Pivote

int pivote( int A[],int i,int j )
{
int k, r;
for( k = i+1; k <= j; k++ ) {
/* Compara dos elementos */
r = comp( A[k], A[i] );
if( r < 0 )
return i;
else if( r >0 )
return k;
}
/* No hay llaves diferentes */
return -1;
}

QuickSort: Particionamiento

int particion( int A[],int i, int j,
int v )
..
{
int l,r;
l=i; r=j;
do {
Intercambia( A[l], A[r] )
while( comp( A[l], v ) < 0 )
l++;
while( comp( A[r], v ) >= 0 )
r--;
} while ( l<r );
return l;
}
nota: El tiempo de ejecución de
partición es O(j-i+1)

QuickSort: EjemploQuickSort: Peor Caso

Un ejemplo del peor caso se puede mostrar en la figura siguiente:

El tiempo tomado por quicksort para este caso es la suma sobre todos los elementos del número de veces que el elemento forma parte de un sub-arreglo en el cual se hace un llamado a quicksort.
En el árbol anterior, se representa por la profundidad de cada elemento
del arreglo.
• La profundidad de ri esn-i+2, 2 £ i £ n,
• la profundidad de r1 es n.

Por lo tanto, en el peor caso quicksort toma un tiempo O(n2).

QuickSort: Caso Promedio
No existen elementos con llaves iguales; todos los elementos tienen llaves diferentes.
Cuando se llama a quicksort( A, l, m ) todos los órdenes (permutaciones) de A[l], ...,A[m] son igualmente probables.
Si el ordenamiento inicial es r1, r2, ..., rn porel método de elección del pivote, éste puede ser ó r1 ó r2.
Suponga que existen i elementos más pequeños que el pivote.
Si el pivote, v, es r1, uno de los i elementos más pequeños que el pivote está en la segunda posición.
Similarmente, si el pivote es r2, uno de los i elementos más pequeños que el pivote está en la primera posición.
El pivote debe ser el (i+1)-ésimo elemento más pequeño,...