Algoritmos de ordenamiento

“Inserción – Burbuja”

I. INTRODUCCIÓN utilizará para ordenar. Dicho campo se suele denominar “clave”. Los
numerosos algoritmos de ordenación se pueden clasificar atendiendo
La ordenación es una operación básica en la vida diaria. El que uno a distintos criterios.
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 Una clasificación comúnmente aceptada distingue entre algoritmos
o menos ordenadas. La razón es obvia: es más sencillo buscar algo de ordenación externa e interna. Los primeros se deben emplear
cuando los objetos están ordenados. Quién no ha pensado “Tendría cuando no es posible almacenar todos los datos a ordenar en un
que ordenar los discos…” al buscar un disco de música en la vector dentro de la memoria principal del ordenador, siendo
estantería o, “Nunca recuerdo si está por su nombre, su apellido, o necesario emplear durante la ordenación un dispositivo de
por su nombre…” al tratar de encontrar el teléfono de un amigo en almacenamiento externo como una cinta o un disco (de ahí su
nuestro celular. Es muy fácil recordar otras fuentes de pequeños nombre).
problemas organizativos en la vida cotidiana (mesita de noche,
Los algoritmos de ordenación interna están pensados para cuando no
escritorio, caja de herramientas, botiquín, etc.)
existe dificultad en el acceso a los datos ya que se tienen
Por tanto, parece evidente que las operaciones de ordenación y almacenados en memoria RAM como un vector de elementos. En
búsqueda son importantes y están estrechamente relacionadas. Algo este artículo nos vamos a centrar en este tipo de algoritmos por ser
similar ocurre en computación: La ordenación es seguramente la los más empleados en la práctica.
operación elemental más importante y, por tanto, mejor estudiada.
Además, existe un criterio adicional de economía de memoria RAM
No en vano utilizamos el término “ordenador “para referirnos a lo
(es lo que se denomina ordenación in situ). En este artículo nos
que otros llaman “computadora”.
limitaremos a describir algoritmos de este tipo.
Además, se puede afirmar con bastante seguridad que la gran
La decisión del algoritmo a emplear debe de tener en cuenta al
mayoría de los datos generados por un programa están ordenados de menos las siguientes consideraciones:
alguna manera y que la gran mayoría de los programas de un cierto • El número de objetos a ordenar
tamaño necesitan realizar en algún momento una ordenación. • El tamaño de dichos objetos (cuánto cuesta moverlos)
• El nivel de desorden que aparece en el conjunto a ordenar
II. ORDENACION

La ordenación o clasificación de datos (sort, en inglés) es una

operación consistente en disponer un conjunto —estructura— de
datos en algún determinado orden con respecto a uno de los campos
de los elementos del conjunto. Por ejemplo, cada elemento del
conjunto de datos de una guía telefónica tiene un campo nombre, un
campo dirección y un campo número de teléfono; la guía telefónica
está dispuesta en orden alfabético de nombres. Los elementos La selección del algoritmo de ordenación implica una decisión multi-
numéricos se pueden ordenar en orden creciente o decreciente de atributo
acuerdo al valor numérico del elemento. En terminología de
ALGORTIMOS SIMPLES Y SOFISTICADOS
ordenación, el elemento por el cual está ordenado un conjunto de
datos (o se está buscando) se denomina clave. Atendiendo al número de objetos a ordenar se puede distinguir entre
algoritmos “simples” y algoritmos “sofisticados”. Los algoritmos
simples (también denominados directos) son una buena solución
cuando son pocos los elementos a ordenar.
Cuando tenemos “bastantes” datos es muy conveniente optar por un
algoritmo sofisticado.
Ahora bien, el problema es saber qué significa “pocos” o “bastantes”
datos. Lamentablemente no existe un umbral claro que permita saber
cuándo no compensa emplear un algoritmo sofisticado ya que el
valor óptimo dependería del ordenador y del código máquina que
implemente el algoritmo. Un umbral razonable puede ser 10
elementos. Este dilema es similar al que aparece cuando tenemos
que realizar una operación numérica.
La Ordenación es una operación básica en la vida humana Si es sencilla lo lógico es emplear una calculadora. Encender el
III. ALGORTIMOS DE ORDENAMIENTO ordenador seguramente es demasiado costoso para luego
simplemente multiplicar 75 por 342. Sin embargo, puede compensar
Los distintos algoritmos de ordenación existentes describen de arrancar el
forma precisa como ordenar de forma creciente un conjunto de ordenador si tenemos que realizar muchas operaciones.
datos. Normalmente los elementos a ordenar están almacenados en
un vector(array). Dado que un elemento puede estar caracterizado
por diversos atributos o campos, es necesario indicar el que se
 for (int i= 0; i < n; i++) {
for (int j= 0; j < n; j++) {
O (1) }
}

tendremos n * n * O (1) = O (n2).

for (int i= 0; i < n; i++) {

for (int j= 0; j < i; j++) {
O (1) }
}
En este caso el bucle exterior se realiza n veces, mientras que el
interior se realiza 1, 2, 3, ..., n veces respectivamente. En total 1 + 2
+ 3 + ... + n = n*(1+n)/2 = O(n2).

A veces aparecen bucles multiplicativos, donde la evolución de la

variable de control no es lineal (como en los casos anteriores)

c= 1; while (c < n) {
O (1)
c= 2*c; }
Algoritmos de ordenación simples y sofisticados
El valor incial de "c" es 1, siendo 2k al cabo de k iteraciones. El
IV. COMPLEJIDAD COMPUTACIONAL DE LAS número de iteraciones es tal que 2k >= n -> k= log2 (n) (el entero
ESTRUCTURAS BÁSICAS DE PROGRAMACIÓN inmediato superior) y, por tanto, la complejidad del bucle es O (log
n).
a. Sentencias sencillas Nos referimos a las sentencias de
asignación, comparación, operaciones lógicas y matemáticas. c= n; while (c > 1) {
Este tipo de sentencias tiene un tiempo de ejecución constante O (1)
que no depende del tamaño del conjunto de datos de entrada, c= c / 2;
siendo su complejidad O (1). }
Razonando de un modo similar al caso anterior, obtenemos un orden
b. Secuencia de sentencias La complejidad de una serie de O (log n).
elementos de un programa es del orden de la suma de las
complejidades individuales; el caso de una secuencia de for (int i= 0; i < n; i++) {
sentencias sencillas la complejidad será: c= i; while (c > 0) {
O (1)+ O (1)+...+ O (1)= k* O (1)= O (1) O (1)
c= c/2; }
c. Selección La evaluación de la condición suele ser de O (1), }
complejidad a sumar con la mayor complejidad computacional En este caso tenemos un bucle interno de orden O (log n) que se
posible de las distintas ramas de ejecución, bien en la rama IF, ejecuta n veces, luego el conjunto es de orden O (n log n).
o bien en la rama ELSE. En decisiones múltiples (ELSE IF,
SWITCH CASE), se tomará la rama cuya complejidad
V. MÉTODO DE LA BURBUJA
computacional es superior.
Se basa en recorrer el array ("realizar una pasada") un cierto número
d. Bucles Los bucles son la estructura de control de flujo que
de veces, comparando pares de valores que ocupan posiciones
suele determinar la complejidad computacional del algoritmo,
adyacentes (0-1,1-2, ...). Si ambos datos no están ordenados, se
ya que en ellos se realiza un mayor número de operaciones. En
intercambian. Esta operación se repite n-1 veces, siendo n el tamaño
los bucles con contador podemos distinguir dos casos: que el
del conjunto de datos de entrada. Al final de la última pasada el
tamaño del conjunto de datos n forme parte de los límites del
elemento mayor estará en la última posición; en la segunda, el
bucle o que no. Si la condición de salida del bucle es
segundo elemento llegará a la penúltima, y así sucesivamente.
independiente de n entonces la repetición sólo introduce una
Su nombre se debe a que el elemento cuyo valor es mayor sube a la
constante multiplicativa:
posición final del array, al igual que las burbujas de aire en un
depósito suben a la parte superior. Para ello debe realizar un
for (int i= 0; i < K; i++) { O (1)}
recorrido paso a paso desde su posición inicial hasta la posición final
la complejidad será K*O(1) = O(1). del array.

Cuando el número de iteraciones a realizar depende del tamaño public static int[] ordenacionBurbuja(int vec[]){
de datos a procesar la complejidad computacional del bucle final int N=[Link];
incrementará con el tamaño de los datos de entrada: for(int i=N-1;i>0;i--){
for(int j=0;j<i;j++){
for (int i= 0; i < n; i++) { O (1)} if(vec[j]>vec[j+1]){
int temp=vec[j];
la complejidad será n* O (1)= O (n). vec[j]=vec[j+1];
vec[j+1]=temp;
 } búsqueda secuencial desde el principio del conjunto hasta encontrar
} un elemento mayor que el dado. Para hacer el hueco hay que
} desplazar los elementos pertinentes una posición a la derecha.
return vec;
} public static int[] ordenacionInsercion(int vec[]){
final int N=[Link];
Implementación en Java algoritmo de ordenación de la burbuja for(int i=1;i<N;i++){
int j=i;
Como se puede observar, es apenas eficiente, sus distintas while(j>0&&vec[j]<vec[j-1]){
complejidades en notacion son las siguientes: int temp=vec[j];
Mejor caso: O(n2) vec[j]=vec[j-1];
Peor caso: O(n2) vec[j-1]=temp;
Caso medio: O(n2) j--;
}
EJEMPLO }
return vec;
}

Implementación en Java algoritmo de ordenación por inserción

Este algoritmo es más eficiente que la ordenación de la burbuja, pero

sigue siendo peor que otros algoritmos, cuando ordenan grandes
listas. Sus distintas complejidades son las siguientes:

Mejor caso: O(n2)

Peor caso: O(n2)
Caso medio: O(n2)

EJEMPLO
Tenemos el vector desordenado.

Iteración 1:
Se ordenan los primeros dos elementos.

Iteración 2:
Se ordenan los elementos 3 y 4.

Se toma el tercer elemento 23 y se ordena entre el primer elemento

y el segundo, recorriéndose el 45 a la tercera posición.

Iteración 3:

No hay cambio ya que el 67 es mayor al 45.

VI. MÉTODO DE INSERCIÓN Iteración 4:

Se utiliza un método similar al anterior, tomando un elemento de la

parte no ordenada para colocarlo en su lugar en la parte ordenada. El Se toma el número 21, y se mete en la posición correspondiente del
primer elemento del array (CB[0]) se considerado ordenado (la lista vector, recorriendo los números mayores.
inicial consta de un elemento). A continuación se inserta el segundo
elemento (CB[1]) en la posición correcta (delante o detrás de CB[0])
dependiendo de que sea menor o mayor que CB[0]. Repetimos esta Y así tenemos el vector ordenado.
operación sucesivamente de tal modo que se va colocando cada
elemento en la posición correcta. El proceso se repetirá TAM-1
veces. Para colocar el dato en su lugar, se debe encontrar la posición
que le corresponde en la parte ordenada y hacerle un hueco de forma
que se pueda insertar. Para encontrar la posición se puede hacer una VII. COMPARACIÓN INSERCIÓN – BURBUJA
BURBUJA
Ventajas:
 Fácil implementación.
 No requiere memoria adicional.

Desventajas:
 Muy lento.
 Realiza numerosas comparaciones.
 Realiza numerosos intercambios.

Análisis de eficiencia
 Hay n-1 comparaciones y pasos en este método. Por lo que el
número total de comparaciones es O(n ).
El número de intercambios depende del orden original del
archivo.
 La única característica redentora de este ordenamiento, es que
requiere de poco espacio adicional para guardar el valor
temporal para el intercambio y de algunas variables enteras
simples.
 Es O(n)2 en el caso de un arreglo ordenado en su totalidad o casi
desordenado en su totalidad.

INSERCION
Ventajas:
 Fácil implementación.
 Requerimientos mínimos de memoria.
Desventajas:
 Lento.
 Realiza numerosas comparaciones

Análisis de eficiencia VIII. CONCLUSIONES

 Aunque este algoritmo tiene un mejor orden de complejidad que Se va a resumir brevemente las conclusiones a las que se ha llegado
el de burbuja, es muy ineficiente al compararlo con otros en cada punto:
algoritmos como quicksort. Sin embargo, para listas  Los algoritmos de ordenación son importantes tanto por sí
mismos como para ser usa-dos por otros algoritmos, como
relativamente pequeñas el orden por inserción es una buena
pueden ser los de búsqueda, siendo imprescindible su
elección, no sólo porque puede ser más rápido para cantidades aprendizaje por todas aquellas personas que pretendan entrar en
pequeñas de elementos sino particularmente debido a su el mundo de la programación.
facilidad de programación.  Los algoritmos vistos en ese documento, son de poca eficiencia
 Es O(n)2 en el caso de un arreglo ordenado en su totalidad o casi a la hora de ordenar gran cantidad de elementos.
desordenado en su totalidad.  Por lo tanto, la velocidad de ejecución depende cuadráticamente
del tamaño del arreglo O(n2).
Análisis (caso práctico)
Fuente: [Link] BIBLIOGRAFIA
ordenamiento/ [1] Eugenio Francisco Sánchez Úbeda, Algoritmos de ordenación,
Se cuentan con dos máquinas corriendo la misma prueba 2001.
números aleatorios a ordenar, en intervalos inicialmente de 10 en 10, [2] CEU, Algoritmos de ordenación y búsqueda.
luego 100 en 100, luego 1.000, luego 10.000 etc, hasta [3] Luis Hernández Yáñez, Fundamentos de la programación, 2014.
[Link] de datos. [4] Iván García Pulido, herramienta para edición y visualización de
algoritmos de ordenación, 2017.
Ahora se procede a mostrar los resultados obtenidos comparando los
tiempos de respuesta de cada algoritmo en cada máquina haciendo
una gráfica de cantidad de datos a ordenar vs tiempo de ejecución.
M1 = Máquina 1 (1 núcleo, 1GB de RAM)
M2 = Máquina 2 (2 núcleos, 2GB de RAM)