PDF de programación - Programación II - Tema 7. Ordenación

1



Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos

Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás

Tema 7. Ordenación

Tema 8. Programación dinámica
Tema 9. Vuelta atrás
Tema 10.Ramificación y poda
Tema 11.Introducción a los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

Introducción

Tema 7. Ordenación
7.1.
7.2. Ordenación por burbuja (Bubble sort)
7.3. Ordenación por selección (Selection sort)
7.4. Ordenación por inserción (Insertion sort)
7.5. Comparación: algoritmos O(n2)
7.6. Ordenación rápida (Quicksort)
7.7. Ordenación por fusión (Mergesort)
7.8. Ordenación por montículo (Heapsort)
7.9. Comparación: algoritmos O(n log n)
7.10. Ordenación por cajas (Bin sort)
7.11. Ordenación por base (Radix sort)
7.12. Comparación: algoritmos O(n)
7.13. Algoritmos de ordenación externos
7.14. Resumen
7.15. Bibliografía

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

2

7.1 Introducción

7.1 Introducción
Uno de los problemas fundamentales de la ciencia de la
computación consiste en ordenar una lista de elementos
Existen infinidad de algoritmos de ordenación

• algunos son simples e intuitivos (e ineficientes)
• otros son más complejos (pero también más eficientes)

Según donde se realice la ordenación estos algoritmos se pueden
dividir en:

• Algoritmos de ordenación interna: la ordenación se realiza en la

memoria del ordenador

• Algoritmos de ordenación externa: la ordenación se realiza en

memoria secundaria (disco duro)

Programación II

© Mario Aldea Rivas

14/04/11

3

Tema 7. Ordenación

7.1 Introducción
Introducción (cont.)

También pueden clasificarse en base a su estabilidad:

• un algoritmo de ordenación es estable si mantiene el orden
relativo que tenían originalmente los elementos con claves
iguales

Cuando se dispone de varios algoritmos para un mismo propósito,
como es el caso de los algoritmos de ordenación, la elección del
más apropiado se realizará comparando:
• Complejidad computacional (en notación O(n), Θ(n) o Ω(n))
- los algoritmos de ordenación más simples son O(n²)
- los algoritmos de ordenación más eficientes son O(n log n)
- existen algoritmos de ordenación O(n) pero sólo pueden
aplicarse a determinados tipos de problemas
• Uso de memoria (también se usa la notación O(n))
• Facilidad de implementación (menos importante)

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

4

7.2 Ordenación por burbuja (Bubble sort)

7.2 Ordenación por burbuja (Bubble sort)
Algoritmo de ordenación sencillo, antiguo (1956) e ineficiente [5]
Recorre la tabla comparando parejas de elementos consecutivos

• intercambia sus posiciones si no están en el orden correcto
• Ejemplo de ejecución: ordenación del array {9,21,4,40,10,35}

Primera pasada:
{9,21,4,40,10,35} --> {9,21,4,40,10,35} (no se realiza intercambio)
{9,21,4,40,10,35} --> {9,4,21,40,10,35} (intercambio entre el 21 y el 4)
{9,4,21,40,10,35} --> {9,4,21,40,10,35} (no se realiza intercambio)
{9,4,21,40,10,35} --> {9,4,21,10,40,35} (intercambio entre el 40 y el 10)
{9,4,21,10,40,35} --> {9,4,21,10,35,40} (intercambio entre el 40 y el 35)
Segunda pasada:
{9,4,21,10,35,40} --> {4,9,21,10,35,40} (intercambio entre el 9 y el 4)
{4,9,21,10,35,40} --> {4,9,21,10,35,40} (no se realiza intercambio)
{4,9,21,10,35,40} --> {4,9,10,21,35,40} (intercambio entre el 21 y el 10)
{4,9,10,21,35,40} --> {4,9,10,21,35,40} (no se realiza intercambio)
{4,9,21,10,35,40} --> {4,9,10,21,35,40} (no se realiza intercambio)


Aunque el array ya está ordenado se harían otras 3 pasadas más
© Mario Aldea Rivas

14/04/11

Programación II

Tema 7. Ordenación

7.2 Ordenación por burbuja (Bubble sort)

Implementación
public void bubble(int [] a) {
int i, j, temp;
// recorre el array n-1 veces
for (i=1; i<a.length; i++) {
// recorre todos los elementos
for(j=0; j<a.length-1; j++) {
// compara cada par de elementos consecutivos
if (a[j] > a[j+1]) {
// si están desordenados los intercambia
temp = a[j];
a[j]= a[j+1];
a[j+1]= temp;
}
} // for j
} // for i
}

Programación II

© Mario Aldea Rivas

14/04/11

5

6

Tema 7. Ordenación

7.2 Ordenación por burbuja (Bubble sort)

Prestaciones
Los dos bucles se realizan n-1 veces
• su eficiencia es O(n2)
• el número de intercambios también es O(n2)
Una posible mejora consiste en añadir una bandera que indique si
se ha producido algún intercambio durante el recorrido del array

• en caso de que no se haya producido ninguno el array se
encuentra ordenado y se puede abandonar el método
• con esta mejora su tiempo de ejecución sigue siendo O(n2)
Es un algoritmo estable
Veremos otros métodos de ordenación simples de tiempo O(n2)
• ordenación por selección y por inserción
• ambos métodos son mejores que este

© Mario Aldea Rivas

14/04/11

7

Programación II

Tema 7. Ordenación

7.3 Ordenación por selección (Selection sort)

7.3 Ordenación por selección (Selection sort)

El algoritmo de ordenación por selección consiste en:

• seleccionar el mínimo elemento de la tabla e intercambiarlo con

el primero

• seleccionar el mínimo en el resto de la tabla e intercambiarlo

con el segundo

• y así sucesivamente...

• Ejemplo de ejecución: ordenación del array {40,21,4,9,10,35}

{40,21,4,9,10,35}
{4,21,40,9,10,35} <-- se selecciona el 4 y se cambia con el 40
{4,9,40,21,10,35} <-- se selecciona el 9 y se cambia con el 21
{4,9,10,21,40,35} <-- se selecciona el 10 y se cambia con el 40
{4,9,10,21,40,35} <-- se selecciona el 21 y se cambia con el 21
{4,9,10,21,35,40} <-- se selecciona el 35 y se cambia con el 40

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

7.3 Ordenación por selección (Selection sort)

Implementación
void ordenaPorSelección (int[] a) {
int min,i,j,aux;
// para todos los elementos menos el último
for (i=0; i<a.length-1; i++) {
min:=i;
// busca el mínimo entre todos los elementos
// después de la posición i
for(j=i+1; j<a.length; j++)
if (a[min] > a[j])
min:=j; // encontrado nuevo mínimo
// intercambia elemento en la posición i con el
// elemento seleccionado (el mínimo encontrado)
aux=a[min];
a[min]=a[i];
a[i]=aux;
} // for i
}

Programación II

© Mario Aldea Rivas

14/04/11

8

9

Tema 7. Ordenación

7.3 Ordenación por selección (Selection sort)

Prestaciones
El bucle externo se realiza n-1 veces
• en cada iteración el bucle interno se realiza n-i-1 veces

n
2–
∑
0=

i

)

) n
1–(
1+
--------------------------
2

n2
-----
2

n
---–
2

)

(

n

=

=

i–

1–

n
1–(
• luego su eficiencia es O(n2)
• es mejor que el método de la burbuja en su constante oculta
El número de intercambios es O(n)
• sólo se realiza un intercambio por cada iteración del bucle

externo

• el número de intercambios cobra más importancia cuanto

mayores son los elementos a intercambiar

Posible problema para algunas aplicaciones: es inestable

© Mario Aldea Rivas

14/04/11

10

Programación II

Tema 7. Ordenación

7.4 Ordenación por inserción (Insertion sort)

7.4 Ordenación por inserción (Insertion sort)

Este algoritmo divide la tabla en una parte ordenada y otra no
• la parte ordenada comienza estando formada por un único

elemento (el que ocupa la primera posición de la tabla)

• los elementos son insertados uno a uno desde la parte no

ordenada a la ordenada

• finalmente la parte ordenada acaba abarcando toda la tabla
• Ejemplo de ejecución: ordenación del array {40,21,4,9,10,35}
{40, 21, 4, 9, 10, 35}
{21, 40, 4, 9, 10, 35} <- el 21 ocupa su lugar en la parte ordenada
{ 4, 21, 40, 9, 10, 35} <- el 4 ocupa su lugar en la parte ordenada
{ 4, 9, 21, 40, 10, 35} <- el 9 ocupa su lugar en la parte ordenada
{ 4, 9, 10, 21, 40, 35} <- el 10 ocupa su lugar en la parte ordenada
{ 4, 9, 10, 21, 35, 40} <- el 35 ocupa su lugar en la parte ordenada

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

11

7.4 Ordenación por inserción (Insertion sort)

Implementación
public void ordenaPorInserción(int[] a) {
int ele, j;
// introduce cada elemento en la parte ordenada
for(int i=1; i<a.length; i++){
ele = a[i]; // elemento a ordenar
j = i-1; // comienzo de la parte ordenada
// recorre la parte ordenada desplazando una
// posición a la derecha los elementos mayores
// que ele
while(j>=0 && a[j]>ele) {
a[j+1] = a[j];
j = j - 1;
}
// pone ele en su posición en la parte ordenada
a[j+1] = ele;
}
}

Programación II

© Mario Aldea Rivas

14/04/11

12

Tema 7. Ordenación

7.4 Ordenación por inserción (Insertion sort)

Prestaciones
El peor caso se da cuando la tabla se encuentra inicialmente
ordenada en orden decreciente
• el bucle externo se realiza n-1 veces
• en cada iteración el bucle interno se realiza i veces

n
1–
∑
1=

i

i

=

n
1–(

)1
n
1–(
)
--------------------------
2
• luego su eficiencia es O(n2)
• su constante oculta es mejor que la del método de la burbuja y

n
---–
2

+

=

n2
-----
2

que la del método de selección

Es mejor para tablas casi ordenadas
• cuando la tabla está ordenada su tiempo de ejecución es O(n)
Es un algoritmo estable

Programación II

© Mario Aldea Rivas

14/04/11

13

Tema 7. Ordenación

7.5 Comparación: algoritmos O(n2)

7.5 Comparación: algoritmos O(n2)

Poca utilidad: sólo para tablas pequeñas
(pocas decenas de elementos)
Burbuja: no usar nunca
Selección:
• ventaja: pocos intercambios (O(n))
• desventaja: no es estable

Inserción:

Tiempo

400

200

burbuja

selección

inserción

0

5000

10000

n

• en general es mejor que selección
• en tablas casi ordenadas su tiempo de ejecución tiende a O(n)
• es estable

Programación II

Tema 7. Ordenación

© Mario Aldea Rivas

14/04/11

14

7.6 Ordenación ráp