Ordenamiento quick sort
Enviado por • 3 de Noviembre de 2013 • Tutoriales • 1.874 Palabras (8 Páginas) • 236 Visitas
ORDENAMIENTO QUICK SORT.
El ordenamiento rápido (quick sort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
El algoritmo fundamental es el siguiente:
• 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 un lado queden todos los menores que él, y al otro los mayores. 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 otra por 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 en dos 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 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).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.
Pseudocódigo
inicio
variables A: arreglo[1..100] entero
variables i,j,central:entero
variables primero, ultimo: entero
para i = 1 hasta 100
leer(A[i])
Fin para
primero = 1
ultimo = 100
qsort(A[],100)
Fin
Funcion qsort(primero, ultimo:entero)
i = primero
j = ultimo
central = A[(primero,ultimo) div 2]
repetir
mientras A[i]central
j = j - 1
fin mientras
si i < = j
aux = A[i]
A[j] = A[i]
A[i] = aux
i = i + 1
j = j - 1
fin si
hasta que i > j
si primero < j
partir(primero,j)
fin si
si i < ultimo
partir(i, ultimo)
fin si
fin funcion qsort
Diagrama de flujo Ordenamiento rápido
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Qsort
{
class Program
{
static void Main(string[] args)
{
int longitud, d = 1;
Console.Write("Cuantos datos va a ingresar: ");
longitud = int.Parse(Console.ReadLine());
int[] Arreglo= new int [longitud];
for (int r = 0; r < longitud; r++)
{
Console.Write("Dame el numero {0}: ", d);
Arreglo[r] = int.Parse(Console.ReadLine());
d++;
}
Console.WriteLine("DATOS ORDENADOS");
for (int r = 0; r < longitud ;r++)
Console.WriteLine("{0}", Arreglo[r]);
Console.ReadKey();
int primero = 0;
int ultimo = longitud-1;
dividir(Arreglo[],primero,longitud);
}
static void dividir(int[] Arreglo,int primero, int ultimo)
{
int P = primero;
int u = ultimo;
int pivote = Arreglo[(primero+ ultimo)/2];
do
{
while (Arreglo[P] < pivote) ;
P++;
while (Arreglo[u] < pivote) ;
u--;
if (P <= u)
{
int aux = Arreglo[P];
Arreglo[u] = Arreglo[P];
Arreglo[P] = aux;
P = P + 1;
u = u - 1;
}
} while (P <= u);
if (primero < u)
{
dividir(Arreglo, primero, u);
}
if (ultimo > P)
{
dividir(Arreglo, P, ultimo);
}
}
}
}
Método de Ordenamiento QuickSort (Rápido)
Uno de los problemas más frecuentes con los que se enfrentan los diseñadores de software es la ordenación de una lista de elementos. Ya sea que estés lidiando con una base de datos de direcciones Web, una lista de clientes o el listín telefónico de tu ciudad, seguramente necesitarás ordenarlos de alguna forma para que esos datos te sean útiles. Quicksort es el algoritmo de ordenamiento más rápido del mundo, y hoy te contamos como funciona.
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
El algoritmo fundamental es el siguiente:
• 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 un lado queden todos los menores que él, y al otro los mayores. 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 otra por 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 en dos 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 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).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.
Bueno Aquí esta el código.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class Program
{
static void Main(string[] args)
{
int n;
Console.WriteLine("Ingrese Tamaño del arreglo a ordenar: ");
n = Int32.Parse(Console.ReadLine());
Metodo_QuickSort MQS = new Metodo_QuickSort(n);
Console.ReadKey();
}
}
class Metodo_QuickSort
{
int nElem;
int[] QuickSort;
public Metodo_QuickSort(int n)
{
nElem = n;
QuickSort = new int[nElem];
Random Datos = new Random();
Console.WriteLine("");
for (int i = 0; i < QuickSort.Length; i++)
{
QuickSort[i] = Datos.Next(n);
}
Console.WriteLine("Lista en desorden");
Console.WriteLine();
Mostrar();
Console.WriteLine();
MetodoQuickSort(QuickSort, 0, nElem - 1);
Console.WriteLine("Lista en orden");
Console.WriteLine();
Mostrar();
}
private void MetodoQuickSort(int[] QuickSort, int Primero, int Ultimo)
{
int Menor, Mayor, Central;
double Pivote;
Central = (Primero + Ultimo) / 2;
Pivote = QuickSort[Central];
Menor = Primero;
Mayor = Ultimo;
do
{
while (QuickSort[Menor] < Pivote) Menor++;
while (QuickSort[Mayor] > Pivote) Mayor--;
if (Menor <= Mayor)
{
int temp;
temp = QuickSort[Menor];
QuickSort[Menor] = QuickSort[Mayor];
QuickSort[Mayor] = temp;
Menor++;
Mayor--;
}
} while (Menor <= Mayor);
if (Primero < Mayor)
{
MetodoQuickSort(QuickSort, Primero, Mayor);
}
if (Menor < Ultimo)
{
MetodoQuickSort(QuickSort, Menor, Ultimo);
}
}
private void Mostrar()
{
for (int i = 0; i < nElem; i++)
{
Console.WriteLine(QuickSort[i]);
}
}
}
}
No olvides dejar tu comentario¡¡
using System;
namespace quicksort
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
static void Main()
{
int n;
Console.WriteLine("ingrese longuitud del arreglo n: ");
n = Int32.Parse(Console.ReadLine());
Cllenar b = new Cllenar (n);
}
}
class Cllenar
{
int h;
int[] vector;
public Cllenar (int n)
{
h = n;
vector = new int [h];
for (int i = 0; i < h; i ++)
{
Console.WriteLine("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()
{
for (int i = 0; i < h; i ++)
{
Console.Write("{0} ", vector[i]);
}
Console.ReadLine();
}
}
}
...