El método de ordenamiento Quick Sort 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, en el mundo de habla hispana.
Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:
- Se toma un elemento x de una posición cualquiera del arreglo.
- Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos 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 posición 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. Pasada (DER-IZQ)
A[6] >= x 27 >= 15 No hay intercambio
A[5] >= x 44 >= 15 No hay intercambio
A[4] >= x 16 >= 15 No hay intercambio
A[3] >= x 08 >= 15 Si hay intercambio
A: 12,08,15,16,44,27,67,35
Como el recorrido de izquierda a derecha debería iniciarse en la misma posición donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se encuentra en la posición correcta.
A: 12, 08, 15, 16, 44, 27, 67, 35
1er 2do Conjunto
16, 44, 27, 67, 35
x16
(DER-IZQ)
A[8]>=x No hay intercambio
A[7]>=x No hay intercambio
A[6]>=x No hay intercambio
A[5]>=x No hay intercambio
A: 12, 08, 15, 16, 44, 27, 67, 35
xß44
(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
xß35
(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
xß12
(DER-IZQ)
A[2]>=x Si hay intercambio
EL VECTOR ORDENADO:
08,12,15,16,27,35,44,67
Ejemplo del Método de Ordenamiento Quick Sort en C#
using
System;
using
System.Collections.Generic;
using System.Linq;
using System.Text;
namespace quicksort
{
class Class
{
static void Main()
{
int n;
Console.WriteLine("Metodo de Quick Sort");
Console.Write("Cuantos longitud del vector: ");
n = Int32.Parse(Console.ReadLine());
llenar b = new llenar(n);
}
}
class llenar
{
int h;
int[] vector;
public llenar(int n)
{
h = n;
vector = new int[h];
for (int i = 0; i < h; i++)
{
Console.Write("ingrese valor {0}: ", i + 1);
vector[i] = Int32.Parse(Console.ReadLine());
}
quicksort(vector, 0, h - 1);
mostrar();
}
private void quicksort(int[] vector, int primero, int ultimo)
{
int i, j, central;
double pivote;
central = (primero + ultimo) / 2;
pivote = vector[central];
i = primero;
j = ultimo;
do
{
while (vector[i] < pivote) i++;
while (vector[j] > pivote) j--;
if (i <= j)
{
int temp;
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
i++;
j--;
}
} while (i <= j);
if (primero < j)
{
quicksort(vector, primero, j);
}
if (i < ultimo)
{
quicksort(vector, i, ultimo);
}
}
private void mostrar()
{
Console.WriteLine("Vector ordenados en forma ascendente");
for (int i = 0; i < h; i++)
{
Console.Write("{0} ", vector[i]);
}
Console.ReadLine();
}
}
}
muy buen código, gracias!
ResponderEliminarme gustaria saber como se pasa este codigo a windows form
ResponderEliminarMorirás esperando una respuesta
EliminarConcuerdo con este comentario jejejeje
EliminarYo lo ocuparía para ordenar por ejemplo una lista de nombres o números. Los números deberías darlos de alta en un LISTBOX y despues pasar dicha información a un array para usar el método que aqui se presenta. Al finalizar se puede volver a imprimir el array al LISTBOX para mirarlos ordenados.
Quedando asi:
https://upavprogramacionii.blogspot.com/2019/10/quicksort-en-windows-form-c.html
Abra forma de que a este metodo se le agregue la opcion de busqueda, es decir despues de haber ordenado la numeración pedir buscar el numero y dependiendo si esta que nos diga que si y en que posición se encuentre o que no.
ResponderEliminarHe llegado 6 meses tarde pero implementar una busqueda binaria con el arreglo ordenado es lo mejor para optimizar tu búsqueda
Eliminarwey pana necesito en window form :(
ResponderEliminar