PDF de programación - 7A. Más sobre ordenación

Fundamentos de la programación

7A

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

Ordenación por intercambio
Mezcla de dos listas ordenadas

744
747

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

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

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 (Anexo)

Página 744

Algoritmo de ordenación por intercambio

Variación del método de selección directa
Se intercambia el elemento de la posición que se trata en cada
momento siempre que se encuentra uno que es menor:

14
0

7
0

5
0

7
1

14
1

14
1

12
2

12
2

12
2

32
3

32
3

32
3

20
4

20
4

20
4

14
5

14
5

14
5

27
6

27
6

27
6

5
7

5
7

7
7

13
8

13
8

13
8

15
9

15
9

15
9

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 745

intercambio.cpp
intercambio.cpp

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

for (int j = i + 1; j < N; j++) {
// Desde i+1 hasta el final

if (lista[j] < lista[i]) {

int tmp;
tmp = lista[i];
lista[i] = lista[j];
lista[j] = tmp;

}

}

}Igual número de comparaciones, muchos más intercambios
No es estable

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 746

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 747

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

Mezcla de dos listas ordenadas en arrays

const int N = 100;
typedef struct {

int elementos[N];
int cont;

Un índice para cada lista, inicializados a 0 (principio de las listas)

} tLista;

Mientras que no lleguemos al final de alguna de las dos listas:

Elegimos el elemento menor de los que tienen los índices
Lo copiamos en la lista resultado y avanzamos su índice una posición

Copiamos en la lista resultado los que queden en la lista no acabada

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 748

void mezcla(tLista lista1, tLista lista2, tLista &listaM) {

int pos1 = 0, pos2 = 0;
listaM.cont = 0;

while ((pos1 < lista1.cont) && (pos2 < lista2.cont)

&& (listaM.cont < N)) {

if (lista1.elementos[pos1] < lista2.elementos[pos2]) {

listaM.elementos[listaM.cont] = lista1.elementos[pos1];
pos1++;

listaM.elementos[listaM.cont] = lista2.elementos[pos2];
pos2++;

}
else {

}
listaM.cont++;

}
...

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 749

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

mezcla1.cpp
mezcla1.cpp

// Pueden quedar datos en alguna de las listas
if (pos1 < lista1.cont) {

while ((pos1 < lista1.cont) && (listaM.cont < N)) {

listaM.elementos[listaM.cont] = lista1.elementos[pos1];
pos1++;
listaM.cont++;

}

}
else { // pos2 < lista2.cont

while ((pos2 < lista2.cont) && (listaM.cont < N)) {

listaM.elementos[listaM.cont] = lista2.elementos[pos2];
pos2++;
listaM.cont++;

}

}

}

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 750

Mezcla de dos listas ordenadas en archivos

void mezcla(string nombre1, string nombre2, string nombreM) {
// Mezcla las secuencias en los archivos nombnre1 y nombre2
// generando la secuencia mezclada en el archivo nombreM

ifstream archivo1, archivo2;
ofstream mezcla;
int dato1, dato2;

// Los archivos existen y son correctos
archivo1.open(nombre1.c_str());
archivo2.open(nombre2.c_str());
mezcla.open(nombreM.c_str());
archivo1 >> dato1;
archivo2 >> dato2;
while ((dato1 != ‐1) && (dato2 != ‐1)) {
// Mientras quede algo en ambos archivos

...

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 751

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

if (dato1 < dato2) {

mezcla << dato1 << endl;
archivo1 >> dato1;

} else {

mezcla << dato2 << endl;
archivo2 >> dato2;

} // Uno de los dos archivos se ha acabado
if (dato1 != ‐1) { // Quedan en el primer archivo

while (dato1 != ‐1) {

mezcla << dato1 << endl;
archivo1 >> dato1;

}

}

}

}
...

}
else { // Quedan en el segundo archivo

while (dato2 != ‐1) {

mezcla << dato2 << endl;
archivo2 >> dato2;

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 752

mezcla2.cpp
mezcla2.cpp

archivo2.close();
archivo1.close();
mezcla << ‐1 << endl;
mezcla.close();

}

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 753

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

Licencia CC (Creative Commons)

Este tipo de licencias ofrecen algunos derechos a terceras personas
bajo ciertas condiciones.
Este documento tiene establecidas las siguientes:
Reconocimiento (Attribution):
En cualquier explotación de la obra autorizada por la licencia
hará falta reconocer la autoría.
No comercial (Non commercial):
La explotación de la obra queda limitada a usos no comerciales.
Compartir igual (Share alike):
La explotación autorizada incluye la creación de obras derivadas
siempre que mantengan la misma licencia al ser divulgadas.
Pulsa en la imagen de arriba a la derecha para saber más.

Fundamentos de la programación: Algoritmos de ordenación (Anexo)

Página 754

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