PDF de programación - algoritmos de ordenación

Algoritmos de ordenación

Sebastián Gurin (Cancerbero)

Copyright © 2004 by Sebastián Gurin

Revision History
Revision 1 30 de noviembre de 2004 Revised by: Cancerbero

Sobre la licencia de este documento

Copyright (c) 2004 Sebastián Gurin (Cancerbero). Permission is granted to
copy, distribute and/or modify this document under the terms of the GNU
Free Documentation License, Version 1.1 or any later version published by
the Free Software Foundation; with no Invariant Sections, with no
Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is
included in the section entitled "GNU Free Documentation License

Sobre la licencia del código fuente que aparece en este
documento.

El código de los algoritmos que aparecen en este documento se deja libre al
dominio público. Esto se deja explícito en el siguiente apartado:

Algoritmos de ordenación Copyright (C) 2004 Sebastián Gurin (Cancerbero)

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your option) any
later version.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 59
Temple Place, Suite 330, Boston, MA 02111-1307 USA

1

Algoritmos de ordenación

1. Introducción

Discusión sobre varios
algoritmos de ordenación y sus
características.

En este documento se estudiará el problema de ordenar un array de elementos sobre los
cuales se puede establecer una relación de orden (i.e los operadores <, >, = tienen
sentido).

Los algoritmos de este documento serán escritos en C y serán intercambiables entre si;
es decir, todos aceptarán los mismos parámetros: un array A de datos y un entero que
representa el tamaño del array.

Si bien en todo este documento se mostrará como ordenar de forma creciente (de
menor a mayor), esperamos que el lector no tenga problemas realizar las
modificaciones pertinentes (que deberán ser obvias) en los algoritmos para poder
ordenar de forma decreciente.

El array de entrada A tendrá elementos de tipo Dato los cuales podrán ser cualquier
tipo de dato representable (una estructura, un objeto de una clase en particular, un
número, un string, etc). Dicho array será usado al estilo C, es decir los índices de los N
elementos de A serán 0, 1, 2, ..., N-1.

Se supondrá por simplicidad que los datos aceptan el uso de operadores "<" y ">". Si
bien esto no será así en la práctica, no perderemos generalidad. La estrategia para
establecer un orden entre los elementos dependerá de la tecnología que usemos para
implementar el algoritmo de ordenación. En Appendix A se discute esto con más
profundidad y para tres tecnologías de programación distintas: programación
estruturada (C), programación orientada a objetos (C++) y programación de objetos
(Smalltalk, Self, etc.)

También se utilizará el operador de asignación de manera especial en algunos casos.
Por ejemplo, en el siguiente segmento de código, en tmp se almacenará una copia del
iésimo elemento del array A de entrada.

Dato tmp;

/* ... */

tmp = A[i];

2

Algoritmos de ordenación

Junto con la descripción de cada algoritmo también se discutirá el orden de tiempo de
ejecución del mismo. Se utilizará para esto la notación de ordenes de magnitud "O
grande" ("big oh"), descripta en el documento "Análisis de Algoritmos" del mismo
autor (ver Referencias). La medición de estos tiempos ha sido hecha considerando
solamente la cantidad de comparaciones, asignaciónes, etc que impliquen elementos del
array de datos: o sea, las cotas de tiempo sólo están en función del tamaño del conjunto
de datos. Puesto que estos pueden ser arbitrariamente complejos, no se consideran los
tiempos de operaciones sobre ellos. Por ejemplo, (la velocidad de un algoritmo será
distinta para conjuntos de enteros que para conjuntos de reales, puesto que las
operaciones sobre estos últimos por lo general son más lentas que sobre los primeros).

2. Ordenación por selección

Características.

• Su tiempo de ejecución es O(N2) para el mejor, peor y caso promedio.

• Es el más fácil de codificar de los mostrados en este documento.

• Si el array de datos es A y su tamaño es N, lo que hace el algoritmo, para cada i de

[0..N-2] es intercambiar A[i] con el mínimo elemento del subarray [A[i+1], ...,
A[N]].

• Dado que es muy simple de codificar, aunque no tiene los mejores tiempos de
ejecución, es apropiado utilizarlo para arrays de datos relativamente pequeños.

void
intercambiar (Dato * A, int i, int j)
{

Dato tmp = A[i];
A[i] = A[j];
A[j] = tmp;

}

void
ordenacion_seleccion (Dato * A, int N)
{

int i, j, k;
for (i = 0; i < N - 1; i++)

{

for (k = i, j = i + 1; j < N; j++)

3

Algoritmos de ordenación

if (A[j] < A[k])

k = j;

if (k != i)

intercambiar (A, i, k);

}

}

3. Ordenación por inserción

Características.

• Es un algoritmo sencillo de entender y de codificar.

• Si el tamaño de la entrada es N, entonces el orden del tiempo de ejecución, para el

peor caso es O(N2);

• Si la entrada esta "casi ordenada", el algoritmo se ejecuta mucho más rápidamente.
Esta velocidad tiende a un tiempo O(N), peor caso que se cumple cuando la entrada
está totalmente ordenada.

• Es por la propiedad anterior que este algoritmo, a pesar de no ser el más rápido para
entradas grandes, suele usarse de la siguiente manera: Se semi ordena la entrada con
algún otro algoritmo más rápido y más adecuado para entradas grandes. Luego,
cuando tenemos la entrada "casi ordenada" usamos este algoritmo. La velocidad de
ejecución será muy buena por dos razones: su tiempo de ejecución tiende a O(N) con
entradas "casi ordenadas" (lo cual es un tiempo excelente), y la simpleza de su
implementación hará que se ejecute más rápido que otros algoritmos más complejos.
Esto se implementará en Section 8.

Explicación del algoritmo. Sea A el array a ordenar con N elementos. El algoritmo
consiste en recorrer todo el array A comenzando desde la posición p=2 y terminando en
p=N. Para cada p, se trata de ubicar en el lugar correcto el elemento A[p] en entre los
elementos anteriores: A[p-1], A[p-2], ..., A[0].

Dada la posición actual p, el algoritmo se basa en que los elementos A[0], A[1], ...,
A[p-1] ya están ordenados.

void
ordenacion_insercion (Dato * A, int N)
{

int p, j;

4

Algoritmos de ordenación

Dato tmp;
for (p = 1; p < N; p++)

{

tmp = A[p];
j = p - 1;
while ((j >= 0) && (tmp < A[j]))

{

}

A[j + 1] = A[j];
j--;

A[j + 1] = tmp;

}

}

Establezcamos la siguiente definición para poder discutir sobre el orden del tiempo de
ejecución del algoritmo y algunas de sus características.

Inversión. Si hablamos de orden creciente, decimos que en un array A de n datos, la
pareja (A[i],A[j]) es una inversión si se cumple que i<j y A[i]>A[j]. (en orden
decreciente sería el caso contrario).

Es decir, una inversión es aquella pareja (A[i],A[j]) que rompe con el orden de una
secuencia de datos. Dada una secuencia A, si pudiéramos detectar todas sus inversiones
e intercambiar los valores de las mismas obtendríamos la secuencia ordenada. Por
ejemplo, considérese la secuencia (5 3 9 7). Las inversiones de esta secuencia son
(5,3) y (9,7). Intercambiando el 5 por el 3 y el 9 por el 7 obtenemos la secuencia
ordenada (3 5 7 9).

El algoritmo de ordenación por inserción lo que hace es recorrer todo el array
detectando inversiones (la segunda condición del while()) y corrigiéndolas (una por
una en cada iteracción del while()). Dado que existe esta relación entre el algoritmo
de ordenación y el número de inversiones, calculando el número medio de inversiones
en la secuencia de datos se pueden obtener cotas precisas sobre el tiempo de ejecución
del algoritmo.

Puede demostrarse fácilmente que le número medio de inversiones en un array de n
elementos es n(n-1)/4 = O(n2).

Podemos decir entonces que el algoritmo de ordenación por inserción (y en realidad
cualquier algoritmo de ordenación que intercambie sólo elementos adyacentes),
requiere un tiempo de hasta orden n2 en promedio.

5

Algoritmos de ordenación
4. Ordenación de Shell (ShellSort)1

Características.

• A diferencia del algoritmo de ordenación por inserción, este algoritmo intercambia
elementos distantes. Es por esto que puede deshacer más de una inversión en cada
intercambio, hecho del cual nos aprovechamos para ganar velocidad.

• La velocidad del algoritmo dependerá de una secuencia de valores (llamados

incrementos, de los cuales hablaremos más abajo) con los cuales trabaja
utilizándolos como distancias entre elementos a intercambiar. Veremos que con
algunas secuencias podremos obtener ordenes de tiempo de ejecución en el peor caso
de O(n2), O(n^(3/2)) y O(n^(4/3)).

• Se considera la ordenación de Shell como el algoritmo más adecuado para ordenar

entradas de datos moderadamente grandes (decenas de millares de elementos) ya que
su velocidad, si bien no es la mejor de todos los algoritmos, es aceptable en la
práctica y su implementación (código) es relativamente sencillo.

Antes que nada definiremos el concepto de k-ordenación.

Secuencia k-ordenada. Decimos que una secuencia A de n elementos está k-ordenada
(siendo k un natural) si, para todo i de [0,n] se cumple que los elementos A[i + hk]
están ordenados, siendo h un entero y siempre que el índice i+hk esté en [0,n].

El algoritmo de ordenación de Shell lo que hace en realidad es tomar una secuencia de
incrementos h1, h2, ..., hp y en la etapa k-esima realizar una hk-ordenación de los datos.
La única condición que debe respetar la secuencia de incrementos es hp=1 de modo tal
que en la última etapa se hace una 1-ordenación (o sea una ordenación normal).

¿Cómo hacemos para k-ordenar u