quicksort












NOMBRES DEL ALUMNO:
Martínez Zárate Isel Alejandro


CATEDRATICO:
Cabrera García Ciclalli


MATERIA:
Estructura de Datos


SEMESTRE Y GRUPO: TURNO:
3° S3A Matutino


CARRERA
Ing. en Sistemas Computacionales


REPORTE
Investigación de los siguientes conceptos:
QuickSort
Método de inserción
Shell
QuickSort
El método de ordenamientoQuickSort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición.

Es un algoritmo de ordenación  considerado entre los más rápidos y eficientes. Fue diseñado en los años 60s por  Charles Antony Richard Hoare un científico en computación. 
 















El algoritmo usa latécnica divide y vencerás que básicamente se basa en dividir un problema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solución al problema central.

El algoritmo trabaja de la siguiente forma:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a unlado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otrapor los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola endos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende delpivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.




Dado unarreglo desordenado de n elementos


Selecciona un valor v del arreglo, llamado pivote, y rearregla 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 llavesdistintas ) {
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 0 )
return k;
}
/* No hay llaves diferentes */
return -1;
}

QuickSort: Particionamiento

intparticion( 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= 0 )
{
k = particion(A, i, j, A[ind] );
quicksort( A, i, k-1 );
quicksort( A, k, j );
}
}

Ejemplo


Caso particular con algoritmo en C++
// Función para dividir el array y hacer los intercambios
int...