Método Quicksort

MTODO QUICKSORT
Quicksort es un algoritmo de ordenacin considerado entre los ms rpidos y eficientes. Fue diseado en los aos 60s por C. A. R. Hoare un cientfico en computacin. El algoritmo usa la tcnica divide y vencers que bsicamente se basa en dividir un problema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solucin al problema central.
DESCRIPCIN DE PROCESO:
El algoritmo del mtodo de ordenamiento estar formado por tres procesos: QUICKSORT, proceso que inicia el ordenamiento. ENCUENTRA PIVOTE, busca el mejor pivote a partir del primer elemento del vector. PARTICIN, va comparando por ambos extremos e intercambia en caso de ser necesario. La idea central de este algoritmo consiste en los siguientes: Se toma un elemento x de una posicin cualquiera de arreglo. Se trata de ubicar a x en la posicin correcta del arreglo, de tal forma que todos los elemento que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posicin correcta de x en el arreglo.
Ejemplo: A: 15,67,08,16,44,27,12,35 Se selecciona A[i] x=15 Primera pasada (DER-IZQ) A[8] >= x 35 >= 15 No hay intercambio A[7] >= x 12 >= 15 Si hay intercambio A: 12, 67,08,16,44,27,15,35 (IZQ-DER) A[2] < = X 67 < = 15 Si hay intercambio A:12,15,08,16,44,27,67,35 2da. A[6] A[5] A[4] A[3] Pasada (DER-IZQ) >= x 27 >= 15 No >= x 44 >= 15 No >= x 16 >= 15 No >= x 08 >= 15 Si hay hay hay hay intercambio intercambio intercambio intercambio
A: 12,08,15,16,44,27,67,35 Como el recorrido de izquierda a derecha debera iniciarse en la misma posicin donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se encuentra en la posicin correcta.
A: 12, 08, 15, 16, 44, 27, 67, 35 1er 2do Conjunto Conjunto 16, 44, 27, 67, 35 x16 (DER-IZQ) A[8]>=x No A[7]>=x No A[6]>=x No A[5]>=x No hay hay hay hay intercambio intercambio intercambio intercambio
A: 12, 08, 15, 16, 44, 27, 67, 35 x44 (DER-IZQ) A[8]>= x Si hay intercambio A: 12, 08, 15, 16, 35, 27, 67, 44 (IZQ-DER) A[6] < = x No hay intercambio A[7] < = x Si hay intercambio 12, 08, 15, 16, 35, 27, 44, 67 12, 08, 15, 16, 35, 27, 44, 67 35, 27, 44, 67 x35 (DER-IZQ) A[8] >= x No hay intercambio A[7] >= x No hay intercambio A[6] >= x Si hay intercambio 12, 08, 15, 16, 27, 35, 44, 67 12,08 x12 (DER-IZQ) A[2]>=x Si hay intercambio EL VECTOR ORDENADO: 08,12,15,16,27,35,44,67
DIAGRAMA DE FLUJO DEL MTODO DE ORDENAMIENTO DE QUICKSORT
PROGRAMACIN DEL QUICKSORT EN C++
#include<iostream.h> #include<conio.h> void quicksort (int v [],int izquierda ,int derecha ) { int i=izquierda,j=derecha ; int tmp ; int pivote=v[(izquierda+derecha)/ 2]; while(i<=j) { for(i=izquierda;v[i]<pivote;i++); for(j=derecha;v[j]>pivote;j--); if(i<=j) { tmp = v[i]; v[i]=v[j]; v[j]=tmp ; i++; j--; } } if (izquierda<j){ quicksort (v,izquierda,j);} if (i<derecha){ quicksort(v,i,derecha);} } void main() { int v[50],n; clrscr(); cout<<"cuantos elementos desea ingresar: "; cin>>n; for (int i=0;i<n; i++) { cout<<"v["<<i+1<<"]= "; cin>>v[i]; } quicksort (v, 0, n-1); cout<<"numeros ordenados son"<<endl; for (i=0; i<n; i++){ cout<<"v["<<i+1<<"]= "<<v[i]<<endl;} getch(); }
DIAGRAMA DE FLUJO DE ORDENAMIENTO POR INSERCIN
PROGRAMACIN DEL INSERCIN EN C++
#include<iostream.h> #include<conio.h> void main() {clrscr(); int i,j,v[30], aux,n; cout<<"ingrese el tamao del vector: "; cin>>n; for(i=1;i<=n;i++) {cout<<"vetor["<<(i)<<"]:"; cin>>v[i]; } for(i=1;i<n;i++) {for(j=i;j>0;j--) {if(v[j+1]<v[j]) {aux=v[j+1]; v[j+1]=v[j]; v[j]=aux; } } } cout<<"los numeros ordenados son:"<<endl; for(i=1;i<=n;i++) {cout<<"vetor["<<(i)<<"]: "<<v[i]<<endl; } getch(); }
DIAGRAMA DE FLUJO DE ORDENAMIENTO POR BURBUJA
PROGRAMACIN DE BURBUJA EN C++
#include<iostream.h> #include<conio.h> void main() {int j,i,n,aux,v[50],k=1,p,x; cout<<"ingrese numero de vectores:"; cin>>n; for(i=1;i<=n;i++) {cout<<"ingrse vector["<<(i)<<"]:"; cin>>v[i]; } {for(p=1;p<3;p++) for(i=1;i<=n-1;i++) { for(j=1;j<=n-1;j++) if(v[j]>v[j+1]) {aux=v[j]; v[j]=v[j+1]; v[j+1]=aux; }} cout<<"el numero ordenado es:\n"; for(i=1;i<=n;i++) {cout<<v[i]; } if(p==1){ cout<<"\ningrese vector a ordenar:"; cin>>x; n=n+1; v[n]=x;} cout<<"el numero ordenado es:\n"; for(i=1;i<=n;i++) {cout<<v[i]; } getch(); }}
DIAGRAMA DE FLUJO DE ORDENAMIENTO POR SELECCIN DIRECTA
PROGRAMACIN DE SELECCIN DIRECTA EN C++

#include<iostream.h> #include<conio.h> void main() {clrscr(); int i,j,a[30], aux,menor,n; cout<<"ingrese el tamao del vetor: "; cin>>n; for(i=1;i<=n;i++) { cout<<"vetor["<<(i)<<"]:"; cin>>a[i]; } for(i=1;i<n;i++) { menor=i; for(j=i+1;j<=n;j++) { if (a[j]<a[menor]) { menor=j; } } aux =a[i]; a[i]=a[menor]; a[menor]=aux; } cout<<"el orden es:"<<endl; for(i=1;i<=n;i++) { cout<< a[i]; } getch(); }
MTODO MERGESORT
Este algoritmo fue desarrollado por el matemtico hngaro John Von Neumann en 1945. Consiste en dividir en dos partes iguales el vector a ordenar, ordenar por separado cada una de las partes, y luego mezclar ambas partes, manteniendo el orden, en un solo vector ordenado. El algoritmo MergeSort (u Ordenamiento por mezcla) es un algoritmo que sirve para ordenar secuencias de datos. DESCRIPCIN DE PROCESO:
Utiliza los siguientes tres pasos: DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2 elementos cada una. VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT. COMBINAR: combina las dos subsecuencias ordenadas para generar la solucin.
PROCEDIMIENTO MERGESORT
/*recibe el arreglo a ordenar un ndice l que indica el lmite inferior del arreglo a ordenar y un ndice r que indica el lmite superior*/
void mergesort(int a[], int l, int r) { int i,j,k,m,b[MAX]; if (r > l) { m = (r+l) /2; mergesort(a, l, m); mergesort(a, m+1, r); for (i= m+1; i > l;i--) b[i-1] = a[i-1]; for (j= m; j < r;j++) b[r+m-j] = a[j+1]; for (k=l ; k <=r; k++) if(b[i] < b[j]) a[k] = b[i++]; else a[k] = b[j--]; } } a = {a,s,o,r,t,i,n,g,e,x,a,m,p,l,e} {a,s, o,r, a,o,r,s, i,t, g,n, g,i,n,t, a,g,i,n,o,r,s,t, e,x, a,m, a,e,m,x, l,p, e,l,p} a,e,e,l,m,p,x} a = {a,a,e,e,g,i,l,m,n,o,p,r,s,t,x}
REFERENCIAS BIBLIOGRFICAS
http://ronnyml.wordpress.com/2009/07/19/quicksort-en-c/ 21/04/2013 04:41 http://www.angelfire.com/wy2/est_info/quicksort.html 21/04/2013 05:09 http://www.slideshare.net/djmada/quick-sort-estructura-de-datos 21/04/2013 05:09 http://diagramadeflujodeordenamiento.blogspot.com/ 21/04/2013 05:21 http://aprende-sistemasarreglos.blogspot.com/2009/03/mergesort.html 21/04/2013 05:42 http://wernesystem.blogspot.com/ 21/04/2013 05:42 http://ict.udlap.mx/people/ingrid/Clases/IS211/Ordenar.html 21/04/2013 05:42

Método Quicksort

Cargado por

Copyright:

Formatos disponibles

Método Quicksort

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Método Quicksort

Cargado por

Copyright:

Formatos disponibles

MTODO QUICKSORT

DIAGRAMA DE FLUJO DEL MTODO DE ORDENAMIENTO DE QUICKSORT

PROGRAMACIN DEL QUICKSORT EN C++

DIAGRAMA DE FLUJO DE ORDENAMIENTO POR INSERCIN

PROGRAMACIN DEL INSERCIN EN C++

DIAGRAMA DE FLUJO DE ORDENAMIENTO POR BURBUJA

PROGRAMACIN DE BURBUJA EN C++

DIAGRAMA DE FLUJO DE ORDENAMIENTO POR SELECCIN DIRECTA

PROGRAMACIN DE SELECCIN DIRECTA EN C++

También podría gustarte