Programación 2
Grado en Estadística Aplicada
Curso 2012-2013
Ordenación.
Jesús Correas –
[email protected]
Departamento de Sistemas Informáticos y Computación
Universidad Complutense de Madrid
Jesús Correas (DSIC - UCM)
1 / 11
Ordenación
La ordenación de datos es una parte importante de la programación,
especialmente en aplicaciones estadísticas
Por ejemplo, es necesario para calcular percentiles o la mediana de una
muestra de datos.
Existen diversos algoritmos de ordenación, que dependen de diversos
factores:
Si el volumen de datos es muy grande y no cabe en la memoria del
ordenador se utiliza la ordenación externa (sobre disco o,
antiguamente, en cintas magnéticas), con técnicas específicas.
Nosotros veremos la ordenación interna, sobre la propia memoria del
ordenador. Los datos a ordenar están almacenados en un array.
Vamos a ver tres técnicas para ordenar un array de números:
utilizando el método de la burbuja.
utilizando el método de inserción.
utilizando la técnica recursiva mergesort.
Existen muchas otras técnicas, con distinta eficiencia.
Los programas que vamos a ver se pueden modificar fácilmente para
ordenar arrays con otros tipos de datos.
Jesús Correas (DSIC - UCM)
2 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
27
10
12
20
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
27
12
20
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
27
12
20
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
27
20
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
27
20
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
27
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
27
25
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
25
27
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
25
27
13
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
25
13
27
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
25
13
27
15
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
está inmediatamente después.
Si el primer elemento es mayor al segundo, se intercambian.
A continuación se compara el segundo elemento con el que aparece a
continuación y se realiza el mismo proceso.
Los elementos con mayor valor se van desplazando hacia la derecha
como si fueran una burbuja.
Este proceso se debe repetir tantas veces como sea necesario, pues con
un solo recorrido los elemento no quedan ordenados.
10
12
20
25
13
15
27
22
¿Cómo podemos hacer esto en C++?
Jesús Correas (DSIC - UCM)
3 / 11
El método de la burbuja
Esta técnica consiste en lo siguiente:
Se recorre el array comparando cada elemento con el siguiente que
est´
Comentarios de: Grado en Estadística Aplicada - Programación 2 (0)
No hay comentarios