Algoritmos de

Ordenación

Algoritmos y
Estructura de
Datos I

1
Algoritmos de ordenación
Cotidianamente, nos encontramos con listas ordenadas, como por
ejemplo, la guía telefónica que almacenamos en nuestro celular, que se
encuentra ordenada alfabéticamente. También encontramos listas de
alumnos ordenadas de manera creciente, según el número de legajo. Este
ordenamiento no es arbitrario y persigue un objetivo: facilitar algún otro
procedimiento posterior. Así, buscar un nombre en la agenda ordenada
será mucho más rápido.

Dentro del ámbito informático, el ordenamiento es uno de los

procedimientos más comunes y de utilidad. Permiten hacer un buen
procesamiento de los datos y facilitan otros procedimientos importantes,
como la búsqueda de un elemento en un conjunto de elementos. Muchos
problemas parten de la necesidad de un conjunto ordenado de datos.

Ordenamiento

El ordenamiento es el proceso por el cual se busca reorganizar un conjunto de

elementos, en una secuencia determinada.

Así, por ejemplo, podremos ordenar numéricamente de mayor a menor

valor o alfabéticamente, en orden creciente de la A a la Z.

El proceso de ordenamiento puede categorizarse en ordenamiento interno

y externo. El primero hace referencia a que los datos se almacenan en la
memoria principal o interna y, por ende, el proceso de ordenado se realiza
la memoria principal. El segundo, en cambio, es aquel ordenamiento que
no puede llevarse a cabo en la memoria principal, por lo cual los datos
deben almacenarse en el disco y, a partir de allí, se podrá hacer el
ordenado.

El ordenamiento es de gran utilidad en el ámbito del software, debido a

que facilita la búsqueda. Pero, también, ayuda a otros procesos. Tal es el
caso de la detección de los duplicados. Si tenemos al conjunto de datos
ordenado, un elemento duplicado será adyacente a otro igual, lo que
permitirá que la identificación se realice sin tanto esfuerzo. Si hubiéramos
querido detectar un elemento duplicado en un conjunto desordenado, el
rendimiento hubiera sido muy bajo. En general, el ordenamiento de los
elementos permite que el rendimiento de muchos algoritmos crezca
significativamente.

2
Analizaremos algoritmos que, de una entrada, nos permiten entregar como
salida a la entrada ordenada. Este proceso se realizará a través de
comparaciones, de manera exclusiva. En otras palabras, no se permite otro
tipo de operaciones. A estos algoritmos se los denomina algoritmos de
ordenación basados en comparaciones.

En todos los algoritmos de ordenamiento a analizar, asumiremos que el

tamaño de la entrada es de N elementos.

Ordenación por inserción

El algoritmo de ordenación por inserción es un algoritmo que permite
realizar un ordenamiento en entradas de tamaños pequeños. Funciona
bien con pocos elementos, debido a que es un algoritmo corto y no
demanda mucho tiempo para lograr su objetivo. Sin embargo, si se quisiera
aplicar este algoritmo en una entrada de gran tamaño, tardaría mucho
tiempo, por lo que se recomienda buscar otra alternativa.

Este algoritmo está caracterizado por iniciar el proceso en un estado inicial

donde el primer elemento de la estructura se lo considera ordenado. A lo
largo del proceso, se harán las modificaciones pertinentes, que arribarán a
un estado final donde los N elementos estarán ordenados. Para esto, se
hace uso de una variable p que indicará los elementos que se van
ordenando, si se considera desde la posición 0 a la posición p. Por ende, p
podrá asumir valores desde 1 a N-1. A medida que se va iterando por la
estructura, p va incrementando su valor en una unidad.

Proceso de ordenado

El proceso consiste en ir acomodando, secuencialmente, de a un elemento,

y desplazar otros elementos, en caso de ser necesario para ubicarlo en el
orden correcto. Podremos visualizar la dinámica de trabajo de este
algoritmo, en la tabla que se presenta a continuación.

3
Figura 1: Mecanismo de funcionamiento del algoritmo

Fuente: Weiss, 2013, p. 344.

Como se puede observar, tenemos una estructura con 6 valores

desordenados, es decir, N=6.

En el estado inicial, se considera que el valor 8 está ordenado y p vale 1.

Luego, en la siguiente iteración, p vale 2 y debemos incorporar al valor 5, el
cual es menor que el valor 8. En este caso, se hace un desplazamiento del
valor 8 a la derecha y se incorpora al valor 5 en la posición antigua del valor
8. En la siguiente iteración, p vale 3 y se debe incorporar al valor 9, el cual
es mayor a todos los demás valores, por lo que se lo ubica al final. En la
siguiente iteración, p vale 4 y se debe incorporar al valor 2. Este valor es
menor a todos los demás, por lo que será ubicado en la primera posición y
serán desplazados el resto de los elementos una posición a la derecha. Este
proceso continúa hasta que p = N-1 = 6-1 = 5, lo cual indica que ya se
ordenaron todos los elementos.

Tiempo de ejecución

Para poder implementar este algoritmo se usan dos ciclos iterativos, los
cuales determinan que sea O(N2). La cota superior se alcanza cuando están
todos los elementos ordenados de manera inversa. Sin embargo, este
tiempo de ejecución se puede ver disminuido, gracias a que la entrada
haya sido ordenada previamente o si la entrada se encuentra casi
ordenada. Como conclusión, el tiempo de ejecución dependerá no solo del

4
tamaño de la entrada (lo cual ya lo sabíamos), sino que también del grado
de ordenamiento de los elementos. Por otra parte, el tiempo de ejecución
promedio que ofrece este algoritmo es (N2), igual que para otros
algoritmos de ordenamiento.

Inversión

La inversión es un concepto que refiere al grado de desorden de una

estructura.

Una inversión es un par de valores desordenados dentro de la estructura,

donde cada par (i,j) cumple que i<j y Ai>Ax.

Este valor nos informa la cantidad de inversiones o intercambios que se

deberán realizar para ordenar a la estructura.

Por ejemplo, podríamos tener una estructura con los siguientes elementos,
en el orden en que se mencionan:

{9, 5, 7, 1}

Esta estructura cuenta con las siguientes inversiones:

(9, 5), (9, 7), (9, 1), (5, 1), (7, 1)

En este ejemplo, se deberán realizar cinco intercambios, para que quede

ordenado. Cada vez que se realice un intercambio, disminuye en una
unidad la cantidad de inversiones que se deberán hacer para que la
estructura quede ordenada completamente. En este momento, dicha
estructura ya no tendrá inversiones.

Shellsort
Este algoritmo de ordenamiento fue ideado por Donald Shell. Surgió como
una alternativa más eficiente al ordenamiento por inserción y ofrece un
mejor rendimiento, pero con un algoritmo simple de implementar.

La mejora que se le introduce al algoritmo de ordenamiento por inserción

es la de evitar tantos desplazamientos de datos. Shellsort introduce
comparaciones entre elementos que están más próximos.

5
Proceso de ordenado

Se procede a subdividir la estructura en subestructuras de un tamaño

menor. Luego se arma una matriz, que ubica, en cada fila, cada
subestructura para, posteriormente, ordenar cada columna. Se vuelve a
subdividir cada subestructura en otras subestructuras y, nuevamente, se la
dispone en forma de matriz y se obtiene una nueva matriz con más filas.
Luego, se vuelve a ordenar cada columna.

Este proceso se repite hasta que la distancia elegida para armar las
subestructuras sea del tamaño 1 y llegue, en esta última instancia, a un
caso particular de ordenamiento por inserción.

Ahora bien, ¿cómo sabemos qué distancia nos conviene elegir para realizar
las subdivisiones? Donald Shell sugirió que la distancia sea de N/2
elementos, donde N es la cantidad de elementos de la estructura. Este
valor va disminuyendo en cada iteración, hasta llegar al valor 1, donde se
reduce a un caso de ordenamiento por inserción.

Analicemos un ejemplo. Supongamos que tenemos un arreglo de 11

elementos:

[20, 15, 7, 9, 8, 6, 18, 10, 5, 2, 16]

Definimos como distancia a una cantidad de N/2 = 11/2  5 elementos, que

generan las siguientes subestructuras, en forma de matriz:

20 15 7 9 8
6 18 10 5 2
20 − − − −

Ahora, debemos ordenar cada columna y obtener una nueva matriz:

6 15 7 5 2
16 18 10 9 8
20 − − − −

Si transformamos esta matriz nuevamente en un arreglo, obtenemos un

arreglo más ordenado que el original:

[6, 15, 7, 5, 2, 16, 18, 10, 9, 8, 20]

Volvemos a subdividir cada fila en nuevas subestructuras y seleccionamos

como distancia una cantidad de 2 elementos:

6
 6 15
7 5
2 16
18 10
9 8
20 −

Se vuelven a ordenar las columnas:

2 5
6 8
7 10
9 15
18 16
20 −

Obtenemos el siguiente arreglo:

[2, 5, 6, 8, 7, 10, 9, 15, 18, 16, 20]

Nuevamente, volvemos a subdividir cada fila. En este caso, la distancia será

de 1 elemento. Obtendremos una sola columna, lo cual corresponde al
mismo arreglo. En este caso, se procede a ordenar como se realiza en el
ordenamiento por inserción y se obtiene, finalmente, el arreglo ordenado:

[2, 5, 6, 7, 8, 9, 10, 15, 16, 18, 20]

Tiempo de ejecución

El tiempo de ejecución de este algoritmo depende, en gran medida, de las

secuencias de incrementos usadas. El caso promedio no está definido aún.
Pero, el peor caso es O(N2). Esto ocurre cuando la estructura tiene una
cantidad de elementos que es potencia de 2, cuando los elementos de
mayor valor se encuentran en un índice par y cuando los menores se
encuentran en un índice impar. Sucede que, al estar dispuestos de esta
manera, los elementos más grandes seguirán ubicándose en los índices par
y los menores en los impares.

Pero, si hacemos un cambio en la secuencia de los incrementos, podemos

evitar que se produzca el peor de los casos. Si al hacer la división entre 2
obtenemos un valor par, se le puede sumar 1 para que se obtenga un valor
impar y, así, obtener un rendimiento mejor, en el peor de los casos de
O(N3/2). El caso promedio no está definido aún, pero se cree que es O(N5/4),
en función de unas simulaciones que se realizaron.

7
Existen otras formas para mejorar el rendimiento. Si la estructura tiene una
cantidad de elementos N, donde N es potencia exacta de 2, se demostró
que el peor de los casos es O(N3/2). También, se propuso que, en vez de
dividir por 2 la secuencia, se la divida por 2,2 obteniendo un rendimiento
promedio de O(N5/4) (Weiss, 2013).

Mergesort
Si hacemos uso de la recursión, podemos construir algoritmos
subcuadráticos.

Específicamente, un algoritmo de tipo divide y vencerás en

el que se resuelven recursivamente dos problemas de
tamaño mitad con un coste adicional O(N), da como
resultado un algoritmo O(N*Log(N)). Uno de esos algoritmos
es la ordenación por mezcla (mergesort). Ofrece una cota
mejor, al menos teóricamente, que la de la ordenación Shell.
(Weiss, 2013, p. 350).

Proceso de ordenado

Primeramente, se deben tomar dos mitades, A y B, de la estructura. A

ambas mitades se las debe ordenar por separado. Luego, continúa un
algoritmo de mezclado y se obtiene, finalmente, el total de los elementos
ordenados.

Este algoritmo toma de entrada dos estructuras A y B y genera una salida C,

de un tamaño igual a la suma de los tamaños de A y B. A través de tres
punteros, se tendrá acceso a los índices de las estructuras A, B y C.
Inicialmente, los punteros referenciarán a la primera posición.

El proceso de mezclado consiste en comparar el valor contenido en la

posición del puntero de A y B, se selecciona el menor valor y se lo
almacena en el índice al cual apunta el puntero de C. Posteriormente, el
puntero del menor valor elegido entre A o B se incrementa en un valor,
para que apunte a la siguiente posición. Se podrá notar que solo se
incrementa dicho puntero, pero no se desplaza el puntero del elemento
que resultó ser mayor. Luego, se vuelve a elegir el menor valor entre los
valores a los que referencian los punteros de A y B. Este proceso continúa
hasta que no queden más valores para ser comparados.

8
Puede suceder que A o B se agoten y ya no tenga más elementos para ser
comparados. En ese caso, se copian el resto de los valores en C.

Analicemos un ejemplo. Definimos como entradas A y B a los siguientes

arreglos, con 5 valores cada uno:

A = [20, 4, 7, 9, 18]; B = [8, 15, 6, 12, 2]

Al contener 5 elementos los arreglos A y B, entonces, C tendrá 10

posiciones libres.

Comenzamos el procedimiento de manera que los punteros referenciarán

a la primera posición de los arreglos A, B y C. Nombraremos a dichos
punteros como puntA, puntB y puntC. Los punteros puntA y puntB
referencian a los valores 20 y 8, respectivamente. La comparación de ellos
nos indica que 8 es menor que 21. Por lo tanto, se almacenará el valor 21
en la primera posición de C, referenciada por puntC.

Ahora, puntB y puntC referenciarán a la segunda posición y puntA seguirá

como estaba (primera posición). Se comparan los valores arrojados por los
punteros puntA y puntB, los cuales referencian a los valores 20 y 15. Como
15 es menor que 20, se almacena el valor 15 en la segunda posición de C,
referenciada por puntC.

Tiempo de ejecución

El proceso de mezclado de A y B insume un tiempo lineal, debido al

incremento que se realiza en el puntero puntC, en cada iteración.

Como resultado, un algoritmo de tipo divide y vencerás que

utilice un procedimiento de mezcla lineal se ejecutará en un
tiempo O(N*Log(N)) de caso peor. Este tiempo de ejecución
también representa los tiempos de caso promedio y de caso
mejor, porque el paso de mezcla es siempre lineal. (Weiss,
2013, p. 352).

Quicksort
El método de ordenamiento rápido (o quicksort) es conocido como uno de
los métodos más rápidos y eficientes dentro del abanico de posibilidades

9
de ordenamiento que existen. Funciona muy bien y es relativamente fácil
de implementar.

Este algoritmo es de tipo divide y vencerás, debido a que divide la

estructura en mitades y trabaja recursivamente sobre ellas.

Es un método bastante parecido a mergesort. Sin embargo, sus diferencias

son cruciales para que este algoritmo funcione mejor, debido a que
incorpora cuidadosas modificaciones en su código, que generan una gran
mejora. Quicksort buscó la manera de cuidar el uso de la memoria y evitar
la utilización de una matriz adicional durante la partición y optimizar los
bucles internos.

Proceso de ordenado

Este algoritmo consiste en obtener un valor cualquiera del conjunto de

valores de entrada. Dicho valor servirá de pivote, con el cual se hará una
comparación con el resto de los valores. Se conformarán dos conjuntos: un
conjunto para los valores mayores al pivote y otro para los valores
menores. ¿Qué hacemos con los valores iguales? Algunas
implementaciones sugieren almacenarlo en alguno de los dos conjuntos.
Luego, se aplica quicksort para cada subconjunto de valores. Finalmente, se
unen los subconjuntos, de la siguiente manera:

valores menores + pivote + valores mayores

Podemos ver que la elección del pivote es importante para garantizar un

mejor resultado en este algoritmo. Si elegimos al azar un valor que justo es
el menor o el mayor valor de todos, ubicado en un extremo, obtendremos
un subconjunto vacío. Sin embargo, aún en estos casos, este algoritmo
funciona bastante bien. Pero, nos interesa que sea lo más eficiente posible.
Entonces, la elección del elemento pivote no debería ser arbitraria.

Una forma de elegir el elemento pivote es el cálculo de la media o el

promedio de un conjunto reducido de valores. Algunos autores
recomiendan el cálculo de la mediana: seleccionar aquel valor que es
mayor o igual a la mitad del conjunto de los valores y menor o igual a la
otra mitad. Se debería intentar garantizar que el elemento pivote que se
elija exista como un valor dentro del conjunto de los valores.

Analicemos un ejemplo. Supongamos que tenemos el siguiente conjunto

de valores:

[10, 3, 5, 8, 20, 15, 9, 7]

10
Elegimos como pivote el valor 8, por lo que tendremos dos subconjuntos,
donde, en uno de ellos, ubicaremos los valores mayores o iguales a 8 y, en
el otro, los valores menores a 8.

[3, 5, 7] 8 [10, 20, 15, 9]

Volvemos a aplicar quicksort a cada subconjunto. Elegimos como pivote el

valor 5, para el primer subconjunto y el valor 15, para el segundo.

[3] 5 [7] 8 [10, 9] 15 [20]

Como podemos ver, la estructura ya está casi ordenada. Elegimos como

nuevo pivote el valor 10.

3 5 7 8 [9] 10 15 20

Finalmente, obtenemos la estructura ordenada:

3 5 7 8 9 10 15 20

Tiempo de ejecución

Como vimos anteriormente, este algoritmo deja algunas cuestiones que

deben ser tenidas en cuenta para garantizar que funcione de la mejor
manera. Algunas cuestiones son cómo se realiza la elección del pivote,
dónde se ubican los valores iguales al pivote, cómo se realiza la partición,
etcétera.

El mejor caso sería que el elemento pivote elegido separe a la estructura

en dos mitades de igual tamaño y, a su vez, que esto mismo suceda en
cada una de las subparticiones. Como tendremos estas particiones con sus
correspondientes llamadas recursivas, podemos afirmar que el algoritmo
tiene un tiempo de ejecución O(N*Log(N)).

Si, en cambio, al partir la estructura obtenemos dos subconjuntos, donde

uno de ellos está vacío, es decir, se eligió de pivote al elemento más chico o
más grande de todo el conjunto de valores y esto mismo sucede en las
siguientes subestructuras, estaríamos frente al peor caso. En esta
situación, el tiempo de ejecución es O(N2).

Sin embargo, ambos casos mencionados son los extremos. El caso

promedio es O(N*Log(N)).

11
Selección rápida
Este problema no corresponde a un método de ordenamiento, sino a la
localización del k-ésimo elemento más pequeño de la estructura. Es un
algoritmo que se asemeja mucho al algoritmo quicksort. De hecho, solo se
necesitan realizar algunas modificaciones a dicho algoritmo.

Proceso

Los pasos de quickselect(S,k) son los siguientes:

1) Si el número de elementos de S es 1,
presumiblemente k será también 1, por lo que podemos
devolver el único elemento de S.
2) Seleccionar cualquier elemento v de S.
Será el pivote.
3) Particionar S-{v} en L y R, exactamente
igual que para el caso de la ordenación rápida.
4) Si k es menor o igual que el número de
elementos de L, el elemento que estamos buscando deberá
estar en L. Invocamos Quickselect(L,k) recursivamente. En
caso contrario, si k es exactamente igual a uno más que el
número de elementos de L, el pivote será el k-ésimo
elemento más pequeño y podemos devolverlo como
respuesta. En otro caso, el k-ésimo elemento más pequeño
estará en R y será el (k-|L|-1)-ésimo elemento más pequeño
de R. De nuevo, podemos hacer una llamada recursiva y
devolver el resultado. (Weiss, 2013, p. 370).

Tiempo de ejecución

El peor caso de este algoritmo coincide con el del algoritmo quicksort y

obtiene un tiempo de ejecución O(N2). Sin embargo, si se hace uso de la
mediana de tres para hacer la partición, se hace casi imposible llegar al
peor caso. El tiempo promedio insumido por este algoritmo es lineal.

Otros algoritmos de ordenación

En esta lectura, vimos los principales algoritmos de ordenación. Sin
embargo, existen otros algoritmos que son conocidos, pero exceden a los

12
que analizaremos en esta materia. Podemos mencionar algunos, como el
método de la burbuja o bubble sort, heapsort, binsort, radix sort, entre
otros. Te invito a que investigues sobre ellos.

13
Referencias
Cormen, T., Leiserson, C., Rivest, R., y Stein, C. (2009). Sorting and Order
Statistics. En Autores, Introduction to Algorithms (pp. 147-227). Massachusetts,
USA: The MIT Press.

Sznajdleder, P. A. (2012). Algoritmos de ordenación. En D. Fernandez (Ed.),

Algoritmos a fondo con implementación en C y JAVA (pp. 529-548). Buenos Aires,
AR: Alfaomega.

Weiss, M. A. (2013). Algoritmos de ordenación. En M. Martín-Romo (Ed.)

Estructuras de datos en Java (pp. 341-374). Madrid, ES: Pearson.

14