PDF de programación - 7 Algoritmos de ordenación - Fundamentos de la programación

Fundamentos de la programación

7

Grado en Ingeniería Informática
Grado en Ingeniería del Software
Grado en Ingeniería de Computadores
Facultad de Informática
Luis Hernández Yáñez
Universidad Complutense

Algoritmos de ordenación
Algoritmo de ordenación por inserción
Ordenación de arrays por inserción
Algoritmo de ordenación por inserción

con intercambios
Claves de ordenación
Estabilidad de la ordenación
Complejidad y eficiencia

Ordenaciones naturales

Ordenación por selección directa
Método de la burbuja
Listas ordenadas
Búsquedas en listas ordenadas
Búsqueda binaria

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Algoritmos de ordenación

651
654
665

672
680
688
692
694
701
716
722
729
731

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Algoritmos de ordenación

Página 651

Ordenación de listas

array
125.40

0

76.95

1

328.80 254.62 435.00 164.29 316.05 219.99

93.45

756.62

6

7

8

9

2

Algoritmo de ordenación
Algoritmo de ordenación
(de menor a mayor)
(de menor a mayor)

3

4

5

array
76.95  93.45  125.40  164.29  219.99  254.62  316.05  328.80  435.00  756.62 

4

3

0

1

2
6
array[i] <= array[i + 1]
array[i] <= array[i + 1]

Mostrar los datos en orden, facilitar las búsquedas, ...
Variadas formas de hacerlo (algoritmos)

5

7

8

9

Fundamentos de la programación: Algoritmos de ordenación

Página 652

Ordenación de listas

Los datos de la lista deben poderse comparar entre sí
Sentido de la ordenación:
Ascendente (de menor a mayor)
Descendente (de mayor a menor)
Algoritmos de ordenación básicos:
Ordenación por inserción
Ordenación por selección directa
Ordenación por el método de la burbuja
Los algoritmos se basan en comparaciones e intercambios
Hay otros algoritmos de ordenación mejores

Fundamentos de la programación: Algoritmos de ordenación

Página 653

Fundamentos de la programación: Algoritmos de ordenación

Página 654

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Algoritmo de ordenación por inserción

Partimos de una lista vacía
Vamos insertando cada elemento en el lugar que le corresponda
Baraja de nueve cartas numeradas del 1 al 9
613829
Las cartas están desordenadas
Ordenaremos de menor a mayor (ascendente)
475

Fundamentos de la programación: Algoritmos de ordenación

Página 655

Algoritmo de ordenación por inserción

Colocamos el primer elemento en la lista vacía
Colocamos el primer elemento en la lista vacía
613829475 Lista ordenada:
Lista ordenada:
5

Fundamentos de la programación: Algoritmos de ordenación

Página 656

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Algoritmo de ordenación por inserción

El 7 es mayor que todos los elementos de la lista
Lo insertamos al final
Lista ordenada:
Lista ordenada:
5 7

Fundamentos de la programación: Algoritmos de ordenación

Página 657

Algoritmo de ordenación por inserción

Primer elemento (5) mayor que el nuevo (4):
Desplazamos todos una posición a la derecha
Insertamos el nuevo en la primera posición
Lista ordenada:
Lista ordenada:
5 7 754

Hemos insertado el elemento en su lugar
Hemos insertado el elemento en su lugar

Fundamentos de la programación: Algoritmos de ordenación

Página 658

61382947

6138294

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Algoritmo de ordenación por inserción

9 es mayor que todos los elementos de la lista
Lo insertamos al final
Lista ordenada:
Lista ordenada:
4 5 7

9

Fundamentos de la programación: Algoritmos de ordenación

Página 659

Algoritmo de ordenación por inserción

Primer elemento (4) mayor que el nuevo (2):
Desplazamos todos una posición a la derecha
Insertamos el nuevo en la primera posición
Lista ordenada:
Lista ordenada:
4 5 7 7542

9 9

Fundamentos de la programación: Algoritmos de ordenación

Página 660

613829

61382

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Algoritmo de ordenación por inserción

El 9 es el primer elemento mayor que el nuevo (8):
Desplazamos desde ese hacia la derecha
Insertamos donde estaba el 9
Lista ordenada:
Lista ordenada:
4 5
42

98

97

Fundamentos de la programación: Algoritmos de ordenación

Página 661

Algoritmo de ordenación por inserción

Segundo elemento (4) mayor que el nuevo (3):
Desplazamos desde ese hacia la derecha
Insertamos donde estaba el 4
Lista ordenada:
Lista ordenada:
4 5
9 987543
42

8

7

Fundamentos de la programación: Algoritmos de ordenación

Página 662

6138

613

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Algoritmo de ordenación por inserción

Primer elemento (2) mayor que el nuevo (1):
Desplazamos todos una posición a la derecha
Insertamos el nuevo en la primera posición
Lista ordenada:
Lista ordenada:
2 3
8754321

87

4 5

9 9

Fundamentos de la programación: Algoritmos de ordenación

Página 663

Algoritmo de ordenación por inserción

El 7 es el primer elemento mayor que el nuevo (6):
Desplazamos desde ese hacia la derecha
Insertamos donde estaba el 7
¡¡¡ LISTA ORDENADA !!!
¡¡¡ LISTA ORDENADA !!!
Lista ordenada:
Lista ordenada:
1
2

3 4 5 7 8

876

9 9

Fundamentos de la programación: Algoritmos de ordenación

Página 664

61

6

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

14
2

32
3

14
5

Ordenación de arrays por inserción

El array contiene inicialmente la lista desordenada:
A medida que insertamos: dos zonas en el array
Parte ya ordenada y elementos por procesar
Parte ya ordenada
Parte ya ordenada
Elementos por insertar
Elementos por insertar
Siguiente elemento a insertar en la parte ya ordenada
Siguiente elemento a insertar en la parte ya ordenada

13
8

13
8

32
3

14
5

27
6

12
7

20
2

14
1

5
4

5
4

27
6

12
7

20
0

7
1

7
0

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 665

Ordenación de arrays por inserción

Situación inicial: Lista ordenada con un solo elemento (primero)

20
0

7
1

14
2

32
3

5
4

14
5

27
6

12
7

13
8

15
9

Desde el segundo elemento del array hasta el último:

Localizar el primer elemento mayor en lo ya ordenado

7
1

14
2

20
0

32
3

Primer elemento mayor o igual: índice 0
Primer elemento mayor o igual: índice 0

14
5

5
4

27
6

12
7

15
9

13
8

nuevo
nuevo

7

Fundamentos de la programación: Algoritmos de ordenación

Página 666

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Ordenación de arrays por inserción

. . .

Desplazar a la derecha los ordenados desde ese lugar
Insertar el nuevo en la posición que queda libre

20
0

7
1

7
0

20
1

14
2

14
2

32
3

32
3

5
4

5
4

14
5

14
5

27
6

27
6

12
7

12
7

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

13
8

13
8

15
9

15
9

nuevo
nuevo
nuevo
nuevo

7

7

Fundamentos de la programación: Algoritmos de ordenación

Página 667

Implementación

const int N = 15;
typedef int tLista[N];
tLista lista;

...
int nuevo, pos;
// Desde el segundo elemento hasta el último...
for (int i = 1; i < N; i++) {

nuevo = lista[i];
pos = 0;
while ((pos < i) && !(lista[pos] > nuevo)) {

pos++;

}
// pos: índice del primer mayor; i si no lo hay
for (int j = i; j > pos; j‐‐) {

lista[j] = lista[j ‐ 1];

}
lista[pos] = nuevo;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Fundamentos de la programación: Algoritmos de ordenación

Página 668

20
0

20
0

20
0


7
0

7
1

7
1

20
1

20
1

14
2

14
2

14
2

14
2

32
3

32
3

32
3

32
3

5
4

5
4

5
4

5
4

14
5

1ii

27
6

pospos

14
5

14
5

14
5

27
6

27
6

27
6

12
7

0

12
7

12
7

12
7

15
9

13
8

nuevo
nuevo

7

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 669

7
0

7
0

7
0

5
0

14
1

14
1

7
1

7
1

20
2

20
2

14
2

14
2

32
3

32
3

20
3

20
3

5
4

5
4

32
4

32
4

14
5

4ii

27
6

pospos

14
5

14
5

14
5

27
6

27
6

27
6

12
7

0

12
7

12
7

12
7

15
9

13
8

nuevo
nuevo

5

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 670

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

5
0

5
0

5
0

5
0

7
1

7
1

7
1

7
1

14
2

14
2

14
2

14
2

20
3

20
3

20
3



14
3

32
4

32
4

20
4

20
4

14
5

5ii

27
6

pospos

3

14
5

32
5

32
5

27
6

27
6

27
6

12
7

12
7

12
7

12
7

13
8

nuevo
nuevo

15
9

14

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 671

Fundamentos de la programación: Algoritmos de ordenación

Página 672

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

La inserción de cada elemento se puede realizar
con comparaciones e intercambios

Desde el segundo elemento hasta el último:

Desde la posición del nuevo elemento a insertar:
Mientras el anterior sea mayor, intercambiar

5
0

5
0

5
0

7
1

7
1

7
1

14
2

14
2

14
2

20
3

20
3



14
3

32
4

14
4

20
4

14
5

32
5

32
5

27
6

27
6

27
6

12
7

12
7

12
7

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 673

7
0

7
0

7
0

7
0


5
0

14
1

14
1

14
1

5
1

7
1

20
2

20
2

5
2

14
2

14
2

32
3

5
3

20
3

20
3

20
3

5
4

32
4

32
4

32
4

32
4

14
5

14
5

14
5

14
5

14
5

27
6

27
6

27
6

27
6

27
6

12
7

12
7

12
7

12
7

12
7

13
8

13
8

13
8

13
8

13
8

15
9

15
9

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación

Página 674

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

const int N = 15;
typedef int tLista[N];
tLista lista;

...
int tmp, pos;
// Desde el segundo elemento hasta el último...
for (int i = 1; i < N; i++) {

pos = i;
// Mientras no al principio y anterior mayor...
while ((pos > 0) && (lista[pos ‐ 1] > lista[pos])) {

// Intercambiar...
tmp = lista[pos];
lista[pos] = lista[pos ‐ 1];
lista[pos ‐ 1] = tmp;
pos‐‐; // Posición anterior

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}