roll

Algoritmos
de ordenación (I)
Todos sabemos que los ordenadores, entre otras
cosas, sirven para ordenar. Pero ¿Cómo lo hacen?
¿Existen distintos modos de hacerlo? ¿Depende de
lo que tengamos que ordenar? ¿Es tan crítico elegir
correctamente el método de ordenación?
En este artículo divulgativo se pretende dar
respuesta a estas y a otras preguntas, mostrando
como funcionan los algoritmosde ordenación más
importantes y discutiendo las claves a tener en
cuenta para seleccionar el algoritmo más
apropiado para un problema concreto.

Introducción
a ordenación es una operación básica en la vida diaria.
El que uno sea más o menos hábil realizando pequeñas tareas
cotidianas está directamente relacionado con el que las cosas
implicadas estén más o menos
ordenadas. La razón esobvia: es
más sencillo buscar algo cuando
los objetos están ordenados.

L

Quién no ha pensado “Tendría que ordenar los discos…” al
buscar un disco de música en la
estantería o, “Nunca recuerdo
si está por su nombre, su apellido, o por su nombre de pila…”
al tratar de encontrar el teléfono de un amigo en nuestra
agenda. Encontrar una lata de
pimientos en la despensa también puede ser todoun reto. Es
muy fácil recordar otras fuentes
de pequeños problemas organizativos en la vida cotidiana (mesilla de noche, despacho, caja de
herramientas, botiquín, trastero, etc.)
Por tanto, parece evidente
que las operaciones de ordenación y búsqueda son importantes y están estrechamente relacionadas.

Eugenio Francisco Sánchez Úbeda
Doctor Ingeniero del ICAI
Instituto de InvestigaciónTecnológica y Departamento de Sistemas
Informáticos de la Universidad Pontificia Comillas de Madrid,
donde es coordinador del Área de Sistemas Inteligentes (ASI)
E-mail: Eugenio.Sanchez@iit.upco.es

a

28 anales y electricidad
de mecánica

Algo similar ocurre en computación: La ordenación es seguramente la operación elemental más importante y por
tanto, mejor estudiada. No en
vanoutilizamos el término “ordenador” para referirnos a lo
que otros llaman “computador” o “computer”. Además,
se puede afirmar con bastante
seguridad que la gran mayoría
de los datos generados por un

ALGORITMOS

programa están ordenados de
alguna manera y que la gran
mayoría de los programas de
un cierto tamaño necesitan realizar en algún momento una
ordenación.

FIGURA 1. LA

DEORDENACIÓN

(I)

ORDENACIÓN ES UNA OPERACIÓN BÁSICA EN LA VIDA DIARIA

¿Por qué hay distintos
algoritmos?
asi todos nosotros hemos
aprendido, de forma más o
menos inconsciente y a partir de
la experiencia, varias maneras
distintas de ordenar.

C

Imaginemos, por ejemplo,
que tenemos que ordenar una
mano de cartas en una partida
de mus o de poker. Seguramente la estrategia queseguiremos
es muy diferente de la empleada
cuando uno tiene que colocar
por orden las 200 hojas de un informe desordenado que acaba
de recoger del suelo. Además,
posiblemente emplearemos una
estrategia distinta si sabemos (o
intuimos) que las hojas no están
muy desordenadas.
Si la mayoría de nosotros
empleamos distintas estrategias
de ordenación, no es de extrañar que existan algoritmos deordenación distintos.

¿Qué algoritmo
emplear?
l decidir qué algoritmo de
ordenación es el mejor para nuestro problema no es una
labor sencilla. Dicha decisión se

E

debe basar en varios criterios
que normalmente son difíciles
de evaluar con exactitud.
Volvamos al ejemplo del informe desordenado. Es después de recoger las hojas del
suelo (y comprobar que están
numeradas) cuando unodecide
como ordenará el informe.
Normalmente dicha decisión
se realiza de forma inconsciente y tiene en cuenta ciertos
criterios “borrosos” basados en
el número de hojas a ordenar o
en cómo de ordenadas estén
las hojas. No es lo mismo ordenar 10 que 1000 hojas, como
tampoco lo es ordenar algo
que está totalmente desordenado que algo que está prácticamente ordenado.
La decisión del...