Upload
kathery-correa-quiroz
View
3
Download
1
Embed Size (px)
DESCRIPTION
PROGRA
Citation preview
Método de ordenamiento y búsqueda “Quicksort
Definición
-El método de “ordenamiento rápido” o “Quicksort” es un método recursivo que se basa en la estrategia “divide y vencerás”, de esta manera toma una gran cantidad de información, y la divide en pequeños grupos que sean más fáciles de ordenar.
-el ordenamiento inicia escogiendo un elemento del arreglo, comúnmente llamado “pivote”, el cual es elegido de manera estratégica para hacer más simple el arreglo.
-este método es llamado recursivo, pues, luego de dividir el arreglo en 2 subconjuntos divide a estos en conjuntos aún más pequeños (en otras palabras la función ordenar es aplicada dentro de sí misma).
Funcionamiento El funcionamiento del Quicksort es el siguiente:
-Se calcula un índice a la mitad del vector a ordenar.
-Se comparan los elementos de la izquierda contra ese elemento medio hasta encontrar un elemento mayor al de la mitad.
-Se comparan los elementos de la derecha contra el mismo elemento medio citado arriba hasta encontrar un elemento menor al de la mitad.
-Cuando tenemos un mayor a la izquierda y un menor a la derecha, los intercambiamos entre sí.
-Volvemos a mirar los de la izquierda restante contra el de la mitad bajo el mismo criterio anterior, igual hacemos con los de la derecha y volvemos a intercambiar.
-Esto se repite en un ciclo hasta que el índice por izquierda supere o sea igual al índice por derecha.
-Saliendo de este ciclo el llamado se hace de nuevo recursivo, primero por izquierda considerando un subsector entre el inicio del vector y el índice por derecha.
-Luego se hace un llamado recursivo por derecha considerando un subsector desde el índice por izquierda y el límite del vector por derecha.
-Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
Comparación de tiempos con otros métodos de ordenamiento.-
Complejidad computacional
-En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sablistas 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 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
-En el caso promedio, el orden es O(n·log n).cuando el pivote no esta exactamente al medio de la lista.
Inicio Funcion qsort(arr, ultimo:entero) Definir i = izquierda ,j = derecha,temp como enteros Definir central o pivote= A[(izquierda,derecha) div 2] como entero Mientras(i<=j) mientras arr[i]<central o pivote i=i+1 mientras arr[j]< central o pivote j=j-1 fin mientras fin mientras si (i<=j) temp=arr[i] arr[i] = arr[j] arr[j] = temp
Pseudocódigo
j = j - 1
fin si
fin Mientras
si izq < j
qsort(arr,izq,j)
fin si
si i< derecha
qsort(arr,i,der)
fin si
fin funcion qsort
Inicio
Leer Esto es quicksort
Leer La lista es : 6,69,-33,7,23,5,0,100
Leer La lista se ha ordenado
Leer arreglo[10]={ {88,6,69,-33,98,7,23,5,0,100}
Qsort(arreglo,0,9)
para i=1 hasta i=10
i=i+1
Leer arreglo[i]
Fin Para
FIN
#include<iostream>
using namespace std;
void Quicksort(int arr,int izq,int der)
{
int i= izq,j=der,temp;
int p=arr[(izq+der)/2];//define quien sera el pivote//
while(i<=j)
{
while (arr[i]<p)i++; //avanza posicion de izq a dere
while(arr[j]>p)j--; //retrocede
Codigo en c++
if(i<=j)
{
temp=arr[i];
arr[i]=arr[j]; // para cambiar de lugar
arr[j]=temp;
i++,j--;
}
}
if (izq<j)
Quicksort(arr,izq,j);
if(i<der)
Quicksort(arr,i,der);
// llama funciones para las dos mitades//
int main()
{
cout<<"Metodo quicksort";
cout<<"esto es la lista";
cout<<" 6,69,-33,7,23,5,0,100"<<endl;
cout<<" la lista de abajo se ha ordenado:\n\n";
int arreglo[10]={88,6,69,-33,98,7,23,5,0,100};
Quicksort(arreglo,0,9);
for(int i=0;i<10;i++)
cout<<arreglo[i]<<""<<endl;
system("pause");
return 0;
}