Slides TD Parcial2-31-40

Vista previa del material en texto

Quicksort � función dividir
1 int dividir(vector<int> & v, int d, int h){
2 int pivot = v[h-1];
3 int i = d;
4 for(int j = d; j < h - 1; j++){
5 if(v[j] <= pivot){
6 swapear(v, i, j);
7 i = i + 1;
8 }
9 }
10 swapear(v, i, h-1);
11 return i;
12 }
La función swapear(v,i,j) toma v por referencia e intercambia los
elementos de las posiciones i y j.
17
Quicksort � función dividir � demo
i = Primera posición luego de la primera partición
j = Próximo elemento a clasi�car
123 7 388 41 2 280 50 59 i=0, j=0
123 7 388 41 2 280 50 59 i=0, j=1
7 123 388 41 2 280 50 59 i=1, j=2
7 123 388 41 2 280 50 59 i=1, j=3
7 41 388 123 2 280 50 59 i=2, j=4
7 41 2 123 388 280 50 59 i=3, j=5
7 41 2 123 388 280 50 59 i=3, j=6
7 41 2 50 388 280 123 59 i=4, j=7
Fin del ciclo
7 41 2 50 59 280 123 388 swap(4,7)
18
Quicksort
▶ En peor caso es Θ(n2).
▶ Las particiones pueden ser desbalanceadas
▶ ¾Qué pasa si quedan todos los elementos en una sola partición?
▶ En caso promedio es Θ(n log n).
▶ Requiere asumir que todas las permutaciones del vector de entrada
son equiprobables,
▶ o requiere una implementación aleatorizada que elija el pivot de
manera aleatoria.
▶ Los factores constantes ocultos en Θ(n log n) son muy bajos y, en la
práctica puede ser mucho más e�ciente que otros algoritmos n log n.
19
Counting sort
Nos piden ordenar una secuencia de enteros que almacena edades de
personas. Sabemos que las edades nunca pueden ser mayores a 100.
Idea:
▶ Armamos un vector auxiliar c de 101 posiciones (del 0 al 100)
inicializadas con el valor 0.
▶ El elemento c[i ] queremos que sea un contador que almacene la
cantidad de veces que aparece el valor i en el vector de entrada.
▶ Recorremos el vector de entrada y llenamos los contadores de c .
▶ Recorremos el vector c y construimos el vector de salida agregando i
la cantidad de veces que indica c[i ].
20
Counting sort
1 vector<int> ordenar_edades(const vector<int> & v){
2 vector<int> contadores(101); // O(101)
3 vector<int> res; // O(1)
4
5 // Inicializo los contadores en 0;
6 for(int i = 0; i < 101; i++) // 101
7 contadores[i] = 0; // O(1)
8
9 // Recorro v y actualizo el contador correspondiente.
10 for(int i = 0; i < v.size(); i++) // O(n)
11 contadores[v[i]] = contadores[v[i]] + 1; // O(1)
12
13 // Recorro los contadores y armo el vector ordenado.
14 for(int i = 0; i < 101; i++) // Total = 101 + O(n)
15 for(int j = 0; j < contadores[i]; j++)
16 res.push_back(i);
17
18 return res;
19 } // T(n) es O(n)
22
Counting sort
1 vector<int> counting_sort(const vector<int> & v, int k){
2 vector<int> count(k);
3 vector<int> res;
4
5 for(int i = 0; i < k; i++)
6 count[i] = 0;
7 for(int i = 0; i < v.size(); i++)
8 count[v[i]] = count[v[i]] + 1;
9 for(int i = 0; i < k; i++)
10 for(int j = 0; j < count[i]; j++)
11 res.push_back(i);
12
13 return res;
14 }
▶ T (n, k) ∈ O(n + k)
▶ Si k es un valor constante, entonces T (n, k) ∈ O(n)
23
Resolviendo problemas complejos
Cuando un problema computacional crece en complejidad (de
comportamiento y de datos), es útil aplicar técnicas de abstracción.
Un primer paso para hacerlo es escribir funciones con nombres
declarativos que abstraigan operaciones complejas.
El paso siguiente es escribir nuevos tipos que encapsulen entidades,
conceptos y requerimientos que sean relevantes a nuestro dominio.
Para esto, definiremos tipos abstractos, que combinan información y
algoritmos, y abstraen las dificultades de manejar esa combinación.
3
Tipo abstracto – composición
Un tipo abstracto tiene los siguientes componentes:
Especificación:
I Interfaz: describe las operaciones que se pueden realizar sobre
una instancia del tipo abstracto.
Implementación:
I Estructura de Representación: describe cómo se implementa el
tipo abstracto en base a otros tipos.
I Algoritmos: implementan las operaciones que describe la
interfaz, operando sobre la estructura de representación
respetando y manteniendo su coherencia interna.
4
Tipos abstractos de datos en C++
Una clase de C++ describe un tipo abstracto como una combinación
de datos y de algoritmos que manipulan esos datos.
La parte pública de una clase describe su interfaz, es decir, cómo se
relaciona una instancia de la clase con su entorno.
La parte privada de una clase describe su estructura de
representación, y otros algoritmos auxiliares. Su contenido sólo es
visible al código de los métodos de la misma clase.
5
Tipo abstracto – Interfaz
La interfaz de un tipo debe describir:
I comportamiento funcional (operaciones, tipos de los parámetros
de entrada y salida, Pre y Post condiciones)
I comportamiento no funcional (complejidad temporal de las
operaciones, aliasing, manejo de memoria).
Una buena interfaz minimiza la visibilidad de las decisiones internas
que se hayan tomado para implementar el tipo abstracto.
Vamos a describir un tipo abstracto con cuatro tipos de operaciones:
I Observadores: devuelven toda la información que caracteriza a
una instancia, sin modificarla; deberían ser un conjunto minimal
I Constructores: crean nuevas instancias del tipo abstracto
I Modificadores: modifican la instancia, pueden devolver
información.
I Otras operaciones: otros observadores no esenciales
6