Ordenamiento quick sort

Solo disponible en BuenasTareas
  • Páginas : 2 (393 palabras )
  • Descarga(s) : 0
  • Publicado : 24 de febrero de 2011
Leer documento completo
Vista previa del texto
ORDENAMIENTO QUICK SORT
El ordenamiento por partición (Quick Sort) se puede definir en una forma más
conveniente como un procedimiento recursivo.
Tiene aparentemente la propiedad de trabajarmejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.
Este tipo de algoritmos se basa enla técnica "divide y vencerás", o sea es más rápido y
fácil ordenar dos arreglos o listas de datos pequeños, que un arreglo o lista grande.
Normalmente al inicio de la ordenación se escoge unelemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo.
Se podrá garantizar quelos elementos a la izquierda de la mitad son los menores y los
elementos a la derecha son los mayores.
Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación porpartición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad.
Así se continúa hasta que el tamaño de losarreglos a ordenar es 1, es decir, todos los
elementos ya están ordenados.
En promedio para todos los elementos de entrada de tamaño n, el método hace O(n log
n) comparaciones, el cual esrelativamente eficient

CODIFICACIÓN EN C++
#include <iostream>
#define largo 100
#include"leearreglo.h"
using namespace std;
void quicksort(int A[],int izq, int der )
{int i, j, x , aux;
i =izq;
j = der;
x = A[ (izq + der) /2 ];
do{
while( (A[i] < x) && (j <= der) )
{
i++;
}while( (x < A[j]) && (j > izq) )
{
j--;
}if( i <= j )
{
aux =A[i]; A[i] = A[j]; A[j] = aux;
i++; j--;
}
}while( i <= j );
if( izq < j )
quicksort( A, izq, j );
if( i < der )
quicksort( A, i, der );
}void main ()
{
int A[largo],n;
do{...
tracking img