Teórica09

Vista previa del material en texto

Algoritmos de ordenamiento sobre secuencias
Algoritmos y Estructuras de Datos I
1
Motivación
4 5 1 2 3 6 7
↓
1 2 3 4 5 6 7
2
Ordenamiento de secuencias
I proc ordenar(inout s : seq〈Z〉){
Pre {s = S0}
Post {mismos(s, S0) ∧ ordenado(s)}
}
I pred mismos(s, t : seq〈Z〉){
(∀e : Z)(#apariciones(s, e) = #apariciones(t, e))
}
I aux #apariciones(s : seq〈T 〉, e : T ) : Z =∑|s|−1
i=0 (if s[i ] = e then 1 else 0 fi)
I pred ordenado(s : seq〈Z〉){
(∀i : Z)(0 ≤ i < |s| − 1→L s[i ] ≤ s[i + 1])
}
3
Ordenamiento de secuencias
I Modificamos la secuencia solamente a través de intercambios
de elementos.
proc swap(inout s : seq〈Z〉, in i , j : Z){
Pre {0 ≤ i , j < |s| ∧ s = S0}
Post {s[i ] = S0[j ] ∧ s[j ] = S0[i ] ∧
(∀k : Z)(0 ≤ k < |s| ∧ i 6= k ∧ j 6= k →L s[k] = S0[k])}
}
I Propiedad 1:
s = S0 → mismos(s, S0)
I Propiedad 2:
{mismos(s, S0)}
swap(s,i,j)
{mismos(s, S0)}
I De esta forma, nos aseguramos que mismos(s,S0) a lo largo
de la ejecución del algoritmo.
4
Ordenamiento por selección (Selection Sort)
I Idea: Seleccionar el ḿınimo elemento e intercambiarlo con la
primera posición de la secuencia. Repetir con el segundo, etc.
4 5 1 2 3 6 7
5
Ordenamiento por selección (Selection Sort)
I Idea: Seleccionar el ḿınimo elemento e intercambiarlo con la
primera posición de la secuencia. Repetir con el segundo, etc.
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
// indice del minimo elemento de s entre i y s.size()
int minPos = ...
swap(s, i, minPos);
}
}
6
Ordenamiento por selección (Selection Sort)
I Podemos refinar un poco el código:
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size()-1; i++) {
int minPos= findMinPosition(s, i, s.size());
swap(s, i, minPos);
}
}
I Entonces surge la necesidad de especificar el problema auxiliar
de buscar el ḿınimo entre i y s.size():
proc findMinPosition(in s : seq〈Z〉, in d , h : Z, out min : Z){
Pre {0 ≤ d < h ≤ |s|}
Post {d ≤ min < h
∧L (∀i : Z)(d ≤ i < h→L s[min] ≤ s[i ])}
}
7
Buscar el Ḿınimo Elemento
dmin min h
↓ ↓ ↓
4 5 1 2 3 6 7
↑ ↑ ↑ ↑ ↑ ↑
i i i i i i
I ¿Qué invariante de ciclo podemos proponer?
d ≤ min < i ≤ h ∧L
(∀j : Z)(d ≤ j < i →L s[min] ≤ s[j ])
I ¿Qué función variante podemos usar?
fv = h − i
8
Buscar el Ḿınimo Elemento
I Invariante:
d ≤ min < i ≤ h ∧L (∀j : Z)(d ≤ j < i →L s[min] ≤ s[j ])
I Función variante
fv = h − i
I ¿Cómo lo implementamos?
int findMinPosition(vector<int> &s, int d, int h) {
int min = d;
for(int i = d + 1; i < h; i++) {
if (s[i] < s[min]) {
min = i;
}
}
return min;
}
9
Recap: Teorema de corrección de un ciclo
I Teorema. Sean un predicado I y una función fv : V→ Z
(donde V es el producto cartesiano de los dominios de las
variables del programa), y supongamos que I ⇒ def(B). Si
1. PC ⇒ I ,
2. {I ∧ B} S {I},
3. I ∧ ¬B ⇒ QC ,
4. {I ∧ B ∧ V0 = fv} S {fv < V0},
5. I ∧ fv ≤ 0⇒ ¬B,
... entonces la siguiente tripla de Hoare es válida:
{PC} while B do S endwhile {QC}
10
Buscar el Ḿınimo Elemento
I PC ≡ 0 ≤ d < h ≤ |s| ∧min = d ∧ i = d + 1
I QC ≡ d ≤ min < h
∧L(∀i : Z)(d ≤ i < h→L s[min] ≤ s[i ])
I B ≡ i < h
I I ≡ d ≤ min < i ≤ h
∧L (∀j : Z)(d ≤ j < i →L s[min] ≤ s[j ])
I fv = h − i
int findMinPosition(vector<int> &s, int d, int h) {
int min = d;
for(int i=d+1; i<h; i++) {
if (s[i] < s[min]) {
min = i;
}
}
return min;
}
11
Corrección: Buscar el Ḿınimo Elemento
I PC ≡ 0 ≤ d < h ≤ |s| ∧min = d ∧ i = d + 1
I QC ≡ d ≤ min < h
∧L(∀i : Z)(d ≤ i < h→L s[min] ≤ s[i ])
I B ≡ i < h
I I ≡ d ≤ min < i ≤ h
∧L (∀j : Z)(d ≤ j < i →L s[min] ≤ s[j ])
I fv = h − i
I ¿I es se cumple al principio del ciclo (punto 1.)? X
I ¿Se cumple la postcondición del ciclo a la salida del ciclo
(punto 3.)? X
I ¿Si la función variante alcanza la cota inferior la guarda se
deja de cumplir (punto 5.)? X
12
Corrección: Buscar el Ḿınimo Elemento
I I ≡ d ≤ min < i ≤ h
∧L (∀j : Z)(d ≤ j < i →L s[min] ≤ s[j ])
I fv = h − i
int findMinPosition(vector<int> &s, int d, int h) {
int min = d;
for(int i=d+1; i<h; i++) {
if (s[i] < s[min]) {
min = i;
}
}
return min;
}
I ¿I se preserva en cada iteración (punto 2.)? X
I ¿La función variante es estrictamente decreciente (punto
4.)?X
13
Ordenamiento por selección (Selection Sort)
I Volvamos ahora al programa de ordenamiento por selección:
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
int minPos = findMinPosition(s, i, s.size());
swap(s, i, minPos);
}
}
I PC ≡ i = 0 ∧ s = S0
I QC ≡ mismos(s, S0) ∧ ordenado(s)
I B ≡ i < |s|
I I ≡ ?
I ¡Luego de la i-ésima iteración, subseq(s, 0, i) contiene los i
primeros elementos ordenados! ¿Tenemos entonces el
invariante del ciclo?
I I ≡ mismos(s,S0)∧ ((0 ≤ i ≤ |s|)∧L ordenado(subseq(s, 0, i)))
I fv = |s| − i
14
Ordenamiento por selección (Selection Sort)
I I ≡ mismos(s, S0)∧((0 ≤ i ≤ |s|)∧Lordenado(subseq(s, 0, i)))
I fv = |s| − i
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
int minPos = findMinPosition(s, i, s.size());
swap(s, i, minPos);
}
}
I ¿I se preserva en cada iteración (punto 2.)? 7
I Contraejemplo:
I Si arrancamos la iteración con i = 1 y s = 〈100, 2, 1〉
I Terminamos con i = 2 y s = 〈100, 1, 2〉 que no satisface I
Debemos reforzar el invariante para probar la corrección:
I ≡ mismos(s, S0) ∧ ((0 ≤ i ≤ |s|) ∧L
(
ordenado(subseq(s, 0, i)))∧
(∀j , k : Z)((0 ≤ j < i ∧ i ≤ k < |s|)→L s[j ] ≤ s[k]))
15
Corrección: Ordenamiento por selección (Selection Sort)
I ≡ mismos(s,S0) ∧ ((0 ≤ i ≤ |s|) ∧L
(
ordenado(subseq(s, 0, i))) ∧
(∀j , k : Z)((0 ≤ j < i ∧ i ≤ k < |s|)→L s[j ] ≤ s[k]))
Gráficamente:
x ∈ subseq(s, 0, i) y ∈ subseq(s, i + 1, |s|)
≤ y ≥ x
ordenado ?
16
Corrección: Ordenamiento por selección (Selection Sort)
I PC ≡ i = 0 ∧ s = S0
I QC ≡ mismos(s, S0) ∧ ordenado(s)
I B ≡ i < |s|
I I ≡ mismos(s, S0) ∧ ((0 ≤ i ≤ |s|)∧L
(ordenado(subseq(s, 0, i))) ∧ (∀j , k : Z)((0 ≤ j < i ∧ i ≤ k <
|s|)→L s[j ] ≤ s[k]))
I fv = |s| − i
I ¿I es se cumple al principio del ciclo (punto 1.)? X
I ¿Se cumple la postcondición del ciclo a la salida del ciclo
(punto 3.)?X
I ¿Si la función variante alcanza la cota inferior la guarda se
deja de cumplir (punto 5.)?X
17
Corrección: Ordenamiento por selección (Selection Sort)
I I ≡ mismos(s, S0) ∧ ((0 ≤ i ≤ |s|)∧L
(ordenado(subseq(s, 0, i))) ∧ (∀j , k : Z)((0 ≤ j < i ∧ i ≤ k <
|s|)→L s[j ] ≤ s[k]))
I fv = |s| − i
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
int minPos = findMinPosition(s, i, s.size());
swap(s, i, minPos);
}
}
I ¿I se preserva en cada iteración (punto 2.)? X
I ¿La función variante es estrictamente decreciente (punto
4.)?X
18
Ordenamiento por selección (Selection Sort)
int findMinPosition(vector<int> &s, int d, int h) {
int min = d;
for(int i=d+1; i<h; i++) {
if (s[i] < s[min]) {
min = i;
}
}
return min;
}
void selectionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
int minPos = findMinPosition(s,i,s.size());
swap(s, i, minPos);
}
}
I ¿Cómo se comporta este algoritmo?
I Veámoslo en https://visualgo.net/es/sorting.
19
https://visualgo.net/es/sorting
Tiempo de ejecución de peor caso
findMinPosition
I Sea n = |s| ¿cuál es el tiempo de ejecución de peor caso de
findMinPosition?
int min = d; c1 1
for(int i=d+1; i<h; i++) { c2 n
if (s[i] < s[min]) { c3 n − 1
min = i; c4 n − 1
}
}
return min; c5 1
I TfindMinPosition(n) = 1∗c1+n∗c2+(n−1)∗c3+(n−1)∗c4+1∗c5
I TfindMinPosition(n) ∈ O(n)
I Decimos que findMinPosition tiene un tiempo de ejecución
de peor caso lineal en función de la longitud de la secuencia.
20
Tiempo de ejecución de peor caso
selectionSort
I Sea n = |s| ¿cuál es el tiempo de ejecución de peor caso para
el programa selectionSort?
for(int i=0; i<s.size(); i++) { c ′1 n + 1
int minPos=findMinPosition(s,i,s.size()); c ′2 ∗ n n
swap(s, i, minPos); c ′3 n
}
I TselectionSort(n) = (n + 1) ∗ c ′1 + n ∗ n ∗ c ′2 + n ∗ c ′3
I TselectionSort(n) ∈ O((n + 1) ∗ n) = O(n2 + n) = O(n2)
I Decimos que selectionSorttiene un tiempo de ejecución de
peor caso cuadrático en función de la longitud de la secuencia.
21
Ordenamiento por selección (Selection Sort)
I Variantes del algoritmo básico:
1. Cocktail sort: consiste en buscar en cada iteración el máximo y
el ḿınimo del vector por ordenar, intercambiando el ḿınimo
con i y el máximo con |s| − i − 1.
2. Bingo sort: consiste en ubicar todas las apariciones del valor
ḿınimo en el vector por ordenar, y mover todos los valores
ḿınimos al mismo tiempo (efectivo si hay muchos valores
repetidos).
I El tiempo de ejecución de peor caso de ambas variantes en
función de n = |s| es:
I TcocktailSort(n) ∈ O(n2)
I TbingoSort(n) ∈ O(n2)
I Por lo tanto, ambas variantes de selectionSort tienen el
“mismo” tiempo de ejecución de peor caso (cuadrático)
22
Ordenamiento por inserción (Insertion Sort)
I Veamos otro algoritmo de ordenamiento, pero donde el
invariante (a diferencia de selectionSort) es:
I ≡ mismos(s, S0)∧(0 ≤ i ≤ |s| ∧L ordenado(subseq(s, 0, i)))
I Esto implica que en cada iteración los primeros i elementos
están ordenados, sin ser necesariamente los i elementos más
pequeños del vector.
I La función variante de este algoritmo de ordenamiento (al
igual que selectionSort) es:
fv = |s| − i
23
Ordenamiento por inserción (Insertion Sort)
I ≡ mismos(s,S0) ∧ (0 ≤ i ≤ |s| ∧L ordenado(subseq(s, 0, i)))
void insertionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
// Tenemos que preservar el invariante...
}
}
I ¿I es se cumple al principio del ciclo (punto 1.)? X
I ¿Se cumple la postcondición del ciclo a la salida del ciclo
(punto 3.)? X
I ¿I se preserva en cada iteración (punto 2.)?
I Sabiendo que los primeros i elementos están ordenados,
tenemos que hacer que los primeros i + 1 elementos pasen a
estar ordenados!
I ¿Cómo lo podemos hacer?
24
Ordenamiento por inserción (Insertion Sort)
Necesitamos desplazar s[i ] hasta una posición donde subseq(s,0,i)
esté ordenada de vuelta. Ejemplo, ya están ordenadas las primeras
3 posiciones.
1 4 5 2 3 6 7
↑
i
1 4 5 2 3 6 7
↑
i , j
1 4 2 5 3 6 7
↑ ↑
j i
1 2 4 5 3 6 7
↑ ↑
j i
25
Ordenamiento por inserción (Insertion Sort)
I Antes de comenzar el desplazamiento, tenemos que:
ordenada
?
subseq(s, 0, i) subseq(s, i , |s|)
I Durante el desplazamiento, se cumple que que:
ordenada ordenada
x > x ?
subseq(s, 0, j) s[j ] subseq(s, j + 1, i + 1) subseq(s, i + 1, |s|)
I Al finalizar el desplazamiento, nuevamente tenemos que:
ordenada
?
subseq(s, 0, i + 1) subseq(s, i + 1, |s|)
26
Ordenamiento por inserción (Insertion Sort)
I Llamemos insert a la función auxiliar que desplaza el
elemento s[i] ¿cuál es el invariante para esta función?
I ≡ 0 ≤ j ≤ i
∧ mismos(subseq(s, 0, i + 1), subseq(S0, 0, i + 1))
∧ subseq(s, i + 1, |s|) = subseq(S0, i + 1, |s|)
∧ ordenado(subseq(s, 0, j)) ∧ ordenado(subseq(s, j , i + 1))
∧ (∀k : Z)(j < k ≤ i →L s[j ] < s[k])
I ¿Cuál es la función variante de insert?
fv = j
27
Ordenamiento por inserción (Insertion Sort)
I ¿Cuál es una posible implementación de insert?
void insert(vector<int> &s, int i) {
for(int j=i; j>0 && s[j] < s[j-1]; j--) {
swap(s, j, j-1);
}
}
I ¿Cuál es una posible implementación de insertSort?
void insertionSort(vector<int> &s) {
for(int i=0; i<s.size(); i++) {
insert(s,i);
}
}
I ¿Cómo se comporta este algoritmo de ordenamiento?
I Veámoslo en https://visualgo.net/es/sorting.
28
https://visualgo.net/es/sorting
Tiempo de ejecución de peor caso
insert
I Sea n = |s| ¿cuál es el tiempo de ejecución de peor caso de
insert?
for(int j=i; j>0 && s[j] < s[j-1]; j--) { c ′′1 n + 1
swap(s, j, j-1); c ′′2 n
}
I Tinsert(n) = c ′′1 ∗ (n + 1) + c ′′2 ∗ n
I Tinsert(n) ∈ O(n)
I insert tiene tiempo de ejecución de peor caso lineal.
29
Tiempo de ejecución de peor caso
insertSort
I Sea n = |s| ¿cuál es el tiempo de ejecución de peor caso de
insertSort?
for(int i=0; i<s.size(); i++) { c ′′′1 n + 1
insert(s, i); c ′′′2 ∗ n n
}
I TinsertSort(n) = c ′′′1 ∗ (n + 1) + c ′′′2 ∗ n ∗ n
I TinsertSort(n) ∈ O(n2)
I insertSort tiene tiempo de ejecución de peor caso
cuadrático (igual que selectionSort)
30
El problema de la bandera holandesa
Dado una secuencia que contiene colores (rojo, blanco y azul)
ordenarlos de modo que respeten el orden de la bandera holandesa
(primero rojo, luego blanco y luego azul)
Por ejemplo, si la secuencia es:
〈White,Red ,Blue,Blue,Red〉
El programa debe modificar la secuencia para que quede:
〈Red ,Red ,White,Blue,Blue〉
31
El problema de la bandera holandesa
I Si Red=1,White=2 y Blue=3, ¿Cuál seŕıa la especificación del
problema?
I proc banderaHolandesa(inout s : seq〈Z〉){
Pre {s = S0 ∧ (∀e : Z)(e ∈ s ↔ (e = 1 ∨ e = 2 ∨ e = 3))}
Post {mismos(s, S0) ∧ ordenado(s)}
}
I ¿Cómo podemos implementar una solución a este problema?
I ¿Podemos usar algún algoritmo de ordenamiento que
conozcamos? Rta: podemos usar insertionSort o
selectionSort.
I ¿Cuál es tiempo de ejecución de peor caso? Rta:
TbanderaHolandesa(n) ∈ O(|s|2)
I ¿Podemos buscar otra solución que tenga un tiempo de
ejecución de peor caso lineal?
32
Idea de solución
2 2 1 2 3 1 2
#1 = 2,#2 = 4,#3 = 1
↓
1 1 2 2 2 2 3
33
Eficiencia de los Algoritmos de ordenamiento
I Tanto selection sort como insertion sort son algoritmos
cuadráticos (iteran una cantidad cuadrática de veces)
I ¿Hay algoritmos con comportamiento más eficiente en peor
caso?
I Quicksort y BubbleSort: Peor caso: O(n2)
I Mergesort y Heapsort: Peor caso: O(n ∗ log(n))
I Counting sort (para secuencias de enteros acotados). Peor
caso: O(n)
I Radix sort (para secuencias de enteros). Peor caso:
O(232) = O(1)
O(1) < O(n) < O(n × log(n)) < O(n2)
34
Órden de los órdenes
O(1) < O(n) < O(n × log(n)) < O(n2)
n
O(n²)
O(n.log n)
O(n)
O(1)
35
Bibliograf́ıa
I Vickers et al. - Reasoned Programming
I 6.5 - Insertion Sort
I NIST- Dictionary of Algorithms and Data Structures
I Selection Sort - https://xlinux.nist.gov/dads/HTML/selectionSort.html
I Bingo Sort - https://xlinux.nist.gov/dads/HTML/bingosort.html
I Cocktail Sort - https://xlinux.nist.gov/dads/HTML/bidirectionalBubbleSort.html
I Cormen et al. - Introduction to Algorithms
I Chapter 2.1 - Insertion Sort
36