Quick Sort: ordenación por partición

ORDENACIÓN POR PARTICIÓN (QUICK SORT)

Partiendo del siguiente array de elementos enteros, especificaremos por encima en que se basa este método:

44 55 12 42 94 6 18 67

18 55 12 42 94 6 44 67

18 6 12 42 94 55 44 67

* Coger un número que este más o menos en el centro.

* Elementos que por su valor deben cambiar de posición.

Tal y como se observa, el array no está ordenado, por lo tanto deberemos aplicar un método recursivo a la derecha del valor coloreado de verde y a su izquierda.

Se puede observar que a la derecha del elemento coloreado de verde se encuentran valores enteros que cumplen la siguiente condición: y a la izquierda los elementos que cumplen la siguiente condición: .

A continuación introduciremos un array de 5000 elementos enteros para proceder a su ordenación por el método Quick Sort.

PROGRAMA:

program quick_so;

uses crt,dos;

const

lim=5000;

type

lista=array [1..lim] of integer;

var

l:lista;

h,m,s,c,h1,m1,s1,c1:word;

i,inicio,fin:integer;

procedure quicksort (var l:lista;inicio,fin:integer);

var

i,j,x,tmp:integer;

begin

x:=l[(inicio+fin) div 2];

i:=inicio;

j:=fin;

repeat

while (l[i]<x) do

i:=i+1;

while (x<l[j]) do

j:=j-1;

if (i<=j) then

begin

tmp:=l[i];

l[i]:=l[j];

l[j]:=tmp;

i:=i+1;

j:=j-1;

end;

until (i>j);

if (inicio<j) then

quicksort (l,inicio,j);

if (i<fin) then

quicksort (l,i,fin);

end;

begin

randomize;

for i:=1 to lim do

l[i]:=random (lim);

gettime (h,m,s,c);

quicksort (l,1,lim);

gettime (h1,m1,s1,c1);

for i:=1 to lim do

writeln (l[i]);

writeln ('Ha tardado: ',h1-h,':',m1-m,':',s1-s,':',c1-c,' tiempo');

end.

Utilizando el método Quick Sort el tiempo empleado para realizar la ordenación de estos 5000 elementos ha sido: 0h:0m:0s:0c

VALORACIÓN DE LOS RESULTADOS OBTENIDOS CON DISTINTOS MÉTODOS:

En nuestra opinión según hemos ido realizando los diferentes métodos, la complejidad de los mismos han aumentado considerablemente, siendo más complejo realizar sus funciones.

Si nos basamos en los tiempos obtenidos, aunque su complejidad a la hora de programarlos sea mayor, se puede deducir que los programas han ido aumentando la calidad, posiblemente siendo la más completa el método Quick Sort.

1

7