PDF de programación - Algoritmia de la ordenación eficiente

ALGORITMIA DE LA ORDENACIÓN EFICIENTE

Necesidad de Ordenar Eficientemente

Análisis Algorítmico



Asignatura: Algoritmos y Estructuras de Datos II
Profesor: Mgter. Oscar Adolfo Vallejos.
Alumno: Arduino Guillermo Andrés



FACENA-UNNE

2011



15º Concurso de Trabajos Estudiantiles, EST 201241 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 569 ABSTRACT



Es sabido que los métodos de ordenación, son materia de estudio en las universidades,
ya que permiten la comprensión de la lógica de programación, como así también el
análisis de la complejidad y eficiencia de los mismos. Por ello este trabajo fue
desarrollado en el marco del cursado de la Asignatura “Algoritmos y Estructuras de
Datos II” en el segundo cuatrimestre de la carrera de Licenciatura en Sistemas de la
Información de la Facultad de Ciencias Exactas y Naturales de la Universidad
Nacional del Nordeste.
Este trabajo está orientado a lograr, el estudio de los algoritmos de ordenamiento, y
los grados de eficiencia de cada uno de los algoritmos tratados.
A los fines indicados se tratará de conocer los métodos desde el más simple hasta el
más complejo, que se han incluido en esta investigación, para ello se describirá cada
método investigado y se analizará tanto su complejidad algorítmica vista desde un
punto de vista teórico, como también en las comparaciones de tiempo de ejecución,
requisitos para ejecutarlos, funcionalidades y alcance.
Arribando a conclusiones, basándose en la ejecución de una aplicación, codificada en
Lenguaje Pascal y que permita medir el tiempo de los métodos de ordenamiento
tratados en este trabajo.



INTRODUCCIÓN


En este Trabajo de Investigación se verán diferentes métodos de ordenamiento,
codificados en Lenguaje Pascal. La importancia del Ordenamiento de datos, en el
contexto del cursado de la asignatura Algoritmos y Estructuras de Datos II, reside
básicamente en la compresión del mismo para analizar los algoritmos a observarse,
con el fin de entender la eficiencia y optimización en su uso real.
Este informe permitirá conocer más a fondo cada método distinto de ordenamiento,
desde uno simple hasta el más complejo dentro del contexto pedido en la Asignatura.
Se realizaran comparaciones en tiempo de ejecución, pre-requisitos de cada
algoritmo, funcionalidad y alcance.
Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En
este caso, nos servirán para ordenar vectores o matrices con valores asignados
aleatoriamente. Haciendo foco en los métodos más populares, analizando el tiempo
que demora y revisando el código, escrito en Pascal, de cada algoritmo
Entonces habiendo definido que es la ordenación, restaría definir entonces a que se
considera eficiencia y optimización en el ordenamiento de los datos.
La optimización de un algoritmo se obtiene cuando se hace la elección correcta de
algoritmo y estructura de datos, esto hace referencia al análisis cuidadoso de su
desempeño para analizar las fallas y concebir mejoras antes de llevarlos a la ejecución
de los mismos en una computadora.
Es así, en el caso de vectores pequeños (valor de N muy chico), los métodos directos
se muestran eficientes, sobre todo porque los algoritmos son sencillos; su uso es muy

15º Concurso de Trabajos Estudiantiles, EST 201241 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 570 frecuente. Sin embargo, en vectores grandes (valor de N considerable) estos métodos
se muestran ineficaces y es preciso recurrir a los métodos avanzados.
Aunque es evidente ver que tanto el tipo y tamaño de los elementos como el
dispositivo en donde se encuentran almacenados pueden influir en el método que
utilicemos para ordenarlos, en este tema se soluciona el caso en que los elementos son
números enteros y se encuentran almacenados en un vector, como se ha explicado
anteriormente.
A continuación se detallan cada uno de los métodos realizados en este trabajo.

MÉTODO DE LA BURBUJA
Procedure OrdenarBurbuja;
Begin
clrscr;
For i:=1 to va_n - 1 do Recorre el vector
Begin
For j:=1 to va_n - 1 do Recorre el vector ordenando
Begin
If ( vv_vector[j] > vv_vector[j+1] ) Then  Pregunta para ordenar de
menor a mayor
Begin
va_aux:=vv_vector[j];
vv_vector[j]:=vv_vector[j+1];
vv_vector[j+1]:=va_aux;
End;
End;
End;

MÉTODO DE SELECCIÓN
Procedure OrdenarSeleccion;
Begin
clrscr;
For i:=1 to va_n - 1 do Recorre n-1 pasadas el vector
Begin
va_menor:=vv_vector[i];
k:=i;
For j:=i+1 to va_n do Recorre el vector ordenando
Begin
If (vv_vector[j] < va_menor ) Then
Begin
va_menor:=vv_vector[j];  Obtiene el menor valor
k:=j;
End;
End;
vv_vector[k]:=vv_vector[i];
vv_vector[i]:=va_menor;  Sitúa el elemento más pequeño en vv_vector[i]
End;



15º Concurso de Trabajos Estudiantiles, EST 201241 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 571 End;

MÉTODO POR INSERCIÓN
Procedure OrdenarBaraja;
Begin
clrscr;
For i:=2 to va_n do Recorre el vector
Begin
va_aux:=vv_vector[i];
j:=i-1;
While ((vv_vector[j] > va_aux) and (j>1)) do  Explora las sub-listas
Begin
vv_vector[j+1] := vv_vector[j];
j:=j-1;  Se mueve buscando la posición correcta de inserción
End;
if (vv_vector[j] > va_aux) then  Realiza el Intercambio Insertando el
elemento
Begin
vv_vector[j+1] := vv_vector[j];
vv_vector[j]:=va_aux;
End
Else
vv_vector[j+1]:=va_aux;
End;

MÉTODO SHELL
Procedure Shell;
var
va_cambios,va_aux:Integer;
i,va_salto:longint;
Begin
clrscr;
va_salto:=va_n;  La variable salto toma el valor de la longitud del vector
While not(va_salto=0) Do
Begin
va_cambios:=1;
While not(va_cambios=0) Do  Si no hay cambios
Begin
va_cambios:=0;
For i:= (va_salto+1) to va_n do  Recorre el vector
Begin
If (vv_vector[i-va_salto]>vv_vector[i]) Then Inicia el ordenamiento
Begin
va_aux:=vv_vector[i];
vv_vector[i]:=vv_vector[i-va_salto];
vv_vector[i-va_salto]:=va_aux;
inc(va_cambios);  Activa la bandera

15º Concurso de Trabajos Estudiantiles, EST 201241 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 572 While vv_vector[i]<pivot Do inc(i);  Recorre a la derecha
While vv_vector[j]>pivot Do dec(j);  Recorre a la izquierda
IF ( i <= j) THEN  Comienza a ordenar de acuerdo al pivot

End;
End;
End;
va_salto:= va_salto div 2;  Se divide el vector original en dos
va_salto:= va_salto div 2; vuelve a calcular el salto
End;
End;

MÉTODO QUICK SORT
Procedure Quick_Sort(VAR vv_vector:array of integer ; izquierda,derecha:longint);
Var
pivot,i,j :longint;
va_aux :integer;
Begin
i:=izquierda;
j:=derecha;
pivot:=vv_vector[(i+j) DIV 2];  Selecciona el Pivot
While i<=j Do
Begin



Begin
va_aux:=vv_vector[i];
vv_vector[i]:=vv_vector[j];
vv_vector[j]:=va_aux;
inc(i);
dec(j);

End;
If (derecha> i ) Then
Quick_Sort(vv_vector,i,derecha);  ordena recursivamente los elementos ubicados a
la derecha
If (izquierda < j ) Then
Quick_Sort(vv_vector,izquierda,j);  ordena recursivamente los elementos ubicados
a la Izquierda
End;
Procedure QuickS;
Begin
clrscr;
Quick_Sort(vv_vector,0,va_n-1);  Llama al procedimiento recursivamente hasta
ordenar el vector.
End;

MÉTODO COUNTING SORT
Procedure Counting_Sort (Var vv_vector: Array of Integer; min, max: longint);

End;

15º Concurso de Trabajos Estudiantiles, EST 201241 JAIIO - EST 2012 - ISSN: 1850-2946 - Página 573 Var
Contador: Array of Integer; Vector auxiliar
i, j, z : longint;
Begin
clrscr;
SetLength(Contador, max-min);  Minimo y Maximo del vector auxiliar
For i := 0 to (max-min) do
Contador[i] := 0;
For i := 0 to (va_n-1) do
Contador[ vv_vector[i] - min ] := Contador[ vv_vector[i] - min ] + 1;  Recorre el
vector y obtiene la lista en forma ordenada
z := 0;
For i := min to max do
For j := 0 to (Contador[i - min] - 1) do
Begin
vv_vector[z] := i;
z := z + 1
End;
End;



COMPLEJIDAD ALGORÍTMICA

En este apartado se intentará ver la complejidad algorítmica de cada método desde el
punto de vista teórico, no se pretende hacer un análisis exhaustivo pero si pretender
mostrar como es la complejidad en cada método anteriormente expuesto.
Método Burbuja
Al algoritmo de la burbuja, para ordenar un vector de n términos, tiene que realizar
siempre el mismo número de comparaciones:



Esto es, el número de comparaciones c(n) no depende del orden de los términos, si
no del número de términos.
Por lo tanto la cota ajustada asintótica del número de comparaciones pertenece al
orden de n cuadrado.
Cuando una lista ya está ordenada, el método de ordenación por burbuja está forzado
a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el
mejor de los casos.
Método Selección
Al algoritmo de ordenamiento por selección, para ord