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

28/03/2014

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
Universidad Complutense

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

Versión optimizada
Claves de ordenación
Estabilidad de la ordenación
Casos de estudio (naturalidad)
Complejidad y eficiencia

Ordenación por selección
Método de la burbuja
Versión optimizada

Búsqueda secuencial
Búsqueda binaria
Órdenes de complejidad
Inserción y eliminación en listas ordenadas
Mezcla de listas ordenadas

2
4
12
15
21
24
25
30
34
38 
40
42
51
52
57

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 1

1

28/03/2014

219.99

93.45

756.62

7

8

9

Ordenación de listas

array
125.40

76.95

328.80

0

1

2

254.62

164.29

435.00

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

316.05

3

4

5

6

array
76.95 

93.45  125.40  164.29  219.99  254.62  316.05  328.80  435.00  756.62 

6

5

4

3

2

1

0

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

Tarea muy habitual: para mostrar los datos en orden o para facilitar
las búsquedas.
Variadas formas de hacerlo (algoritmos), con mayor o menor rapidez.

9

7

8

Fundamentos de programación: Algoritmos de ordenación

Página 2

Ordenación de listas

Los datos de la lista deben poderse comparar entre sí
(admitir los operadores relacionales).
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
Estos algoritmos se basan en comparaciones e intercambios.
Hay otros algoritmos de ordenación mejores
que se estudiarán en su momento.

Fundamentos de programación: Algoritmos de ordenación

Página 3

2

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

28/03/2014

Ordenación de arrays por inserción

7
1

20
0

14
2

32
3

El array contiene inicialmente la lista desordenada:
A medida que vayamos insertando los elementos en su lugar,
una parte del array corresponderá a la lista ordenada
y el resto a los elementos que todavía quedan por procesar.
Elementos por insertar
Parte ya ordenada
Parte ya ordenada
Elementos por insertar

14
5

27
6

12
7

13
8

20
2

32
3

5
4

5
4

14
5

27
6

14
1

7
0

12
7

13
8

15
9

15
9

Siguiente elemento a insertar
Siguiente elemento a insertar

Fundamentos de programación: Algoritmos de ordenación

Página 4

Ordenación de arrays por inserción

Situación inicial: Lista ordenada con un solo elemento.
El primero del array:

7
1

5
4

20
0

14
2

32
3

14
5

27
6
Desde el segundo elemento hasta el último:
 Insertamos el elemento en la parte ordenada
 Localizamos la posición del primer elemento estrictamente mayor…

12
7

13
8

15
9

7
1

20
0

14
2

32
3

Último elemento de la parte ordenada
Último elemento de la parte ordenada

5
4

14
5

27
6

12
7

15
9

13
8

elemento
elemento

7

Fundamentos de programación: Algoritmos de ordenación

Página 5

3

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

28/03/2014

…

Ordenación de arrays por inserción

 Desplazamos una posición a la derecha todos los estrictamente

mayores.

20
0

7
1

14
2

32
3

5
4

14
5

27
6

12
7

15
9

13
8

elemento
elemento

7

 Y colocamos el elemento en curso en la posición que queda libre.

7
0

20
1

14
2

32
3

5
4

14
5

27
6

12
7

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

15
9

13
8

elemento
elemento

7

Fundamentos de programación: Algoritmos de ordenación

Página 6

Ordenación de arrays por inserción

const int N = 10;
typedef double tLista[N];
tLista lista;
double elemento;
...
for (int i = 1; i < N; i++) {
// Desde el segundo elemento hasta el último

elemento = lista[i];
int pos = 0;
bool enc= false;
//búsqueda asimétrica
while ((pos < i) && !enc){

if(lista[pos] > elemento) enc= true;
else pos++;

}
if(enc){ // pos ‐‐> primer elemento mayor

for (int j = i; j > pos; j‐‐) lista[j] = lista[j‐1];
lista[pos] = elemento;

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

}

}

Fundamentos de programación: Algoritmos de ordenación

Página 7

4

28/03/2014

Ordenación de arrays por inserción

20
0

20
0

0


7
0

7
1

7
1

20
1

20
1

14
2

32
3

14
2

14
2

14
2

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

elemento
elemento

7

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de programación: Algoritmos de ordenación

Página 8

Ordenación de arrays por inserción

7
0

7
0

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

elemento
elemento

5

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de programación: Algoritmos de ordenación

Página 9

5

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

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

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

13
8

elemento
elemento

15
9

14

13
8

13
8

13
8

15
9

15
9

15
9

12
7

12
7

12
7

12
7

Fundamentos de programación: Algoritmos de ordenación

Página 10

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

Ordenación de arrays por inserción (versión optimizada)

La inserción de cada elemento en su posición adecuada se puede llevar
a cabo mediante una serie de comparaciones e intercambios:

Desde el segundo elemento hasta el último:
 Obtener el elemento
 Buscamos el primer dato menor o igual, explorando la zona ya
ordenada de derecha a izquierda, abriendo hueco al mismo tiempo

5
0

5
0

5
0

7
1

7
1

7
1

14
2

14
2

14
2

20
3

20
3

20
3

32
4

32
4

20
4

15
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

elemento
elemento

15

Fundamentos de programación: Algoritmos de ordenación

Página 11

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

28/03/2014

6

28/03/2014

Ordenación de arrays por inserción (versión optimizada)

const int N = 10;
typedef double tLista[N];
tLista lista;
...
for (int i = 1; i < N; i++) {
// Desde el segundo elemento hasta el último
double elemento = lista[i];
int pos = i‐1; //i>=1
bool enc = lista[pos] <= elemento;
//esquema simétrico 2
while ((pos > 0) && !enc) {
lista[pos+1] = lista[pos];
pos‐‐;
enc = lista[pos] <= elemento;

}
if (enc) lista[pos+1] = elemento;
else {  

lista[1] = lista[0]; //desplazamos lista[0]
lista[0] = elemento;

Invariante:
Hemos desplazado lista[pos+1..i‐1]

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

}

}    

Fundamentos de programación: Algoritmos de ordenación

Página 12

Ordenación de arrays por inserción

#include <iostream>
#include <fstream>
using namespace std;
const int N = 10;
typedef double tLista[N];

void ordenarInsercion(tLista& lista);
void mostrar(const tLista lista);
bool cargar(tLista& lista);

cout << "Error de archivo: inexistente o con demasiados datos"

int main() {

tLista lista;
if (!cargar(lista))

<< endl;

else {

cout << "Antes de ordenar:" << endl;
mostrar(lista);
...

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

Fundamentos de programación: Algoritmos de ordenación

Página 13

7

28/03/2014

...
ordenarInsercion(lista); 
cout << "Después de ordenar:" << endl;
mostrar(lista);
cin.get();

}
return 0;

}

void ordenarInsercion(tLista& lista){

int i, pos; double elemento; bool enc;
for (i = 1; i < N; i++) {

elemento = lista[i];
pos = 0;
enc= false;
//búsqueda asimétrica
while ((pos < i) && !enc){

if(lista[pos] > elemento) enc= true;
else pos++;

}
if(enc){ // pos ‐‐> primer elemento mayor

for (int j = i; j > pos; j‐‐) lista[j] = lista[j‐1];
lista[pos] = elemento;

}

}

}

Fundamentos de programación: Algoritmos de ordenación

Página 14

A menudo las listas que hay que ordenar no son simplemente arrays
de datos simples, sino arrays de estructuras.

Claves de ordenación

const int N = 100;
typedef struct {
int codigo;
string nombre;
double sueldo;

tDato elemento;

} tDato;
typedef tDato tLista[N];
tLista lista;

Clave de ordenación: Campo en el que se basan las comparaciones.
En el método de inserción “estándar”
En el método de inserción optimizado

if(lista[pos].nombre > elemento.nombre) enc= true;
else pos++;

enc = lista[pos].nombre <= elemento.nombre; 

Fundamentos de programación: Algoritmos de ordenación

Página 15

8

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

Claves de ordenación

}

return opIzq.nombre > opDer.nombre;

bool operator>(tDato opIzq, tDato opDer) {

Podemos crear una función para el operador relacional:
En el método de inserción “estándar”
En el método de inserción optimizado

if(lista[pos] > elemento) enc= true;
else pos++;

tDato elemento;

enc = !(lista[pos] > elemento); //a≤b ↔ !(a>b)

Fundamentos de programación: Algoritmos de ordenación

Página 16

Claves de ordenación

e
e

l
l
l
l

a
a
C
C
a
a

 
 

l
l
 
 

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

 
 

e
e
d
d
n
n
í
í
t
t
r
r
a
a
M
M

 
 
.
.
J
J
 
 
o
o
r
r
d
d
e
e
P
P

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#include <iomanip>
const int N = 100;
typedef struct