<aside> 💡 Idea: Seleccionar el mínimo elemento e intercambiarlo con la primera posición de la secuencia e iterar.
</aside>
void selectionSort(vector<int> &s) {
for (int i = 0; i < s.size(); i++) {
int minPos = findMinPos(s, i s.size());
swap(s, i, minPos);
}
}
Invariante
$$ \text{mismos}(s, S_0) \land \\\bigg((0 \leq i \leq |s|) \land_L \Big(\text{ordenado}\big(\text{subseq}(s, 0, i)\big)\Big) \land (\forall j, k : \Z)\big((0 \leq j < i \land i \leq k < |s|) \Longrightarrow_L s[j] \leq s[k]\big)\bigg) $$
Precondición, postcondición y función variante
$$ P_C \equiv i = 0 \land s = S_0 \qquad Q_C \equiv \text{mismos}(s, S_0) \land \text{ordenado}(s) \qquad f_V = |s|-i $$
int findMinPos(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;
}
Invariante
$$ d \leq \min < i \leq h \land_L (\forall j : \Z)(d \leq j < i \Longrightarrow_L s[\min] \leq s[j]) $$
Precondición, postcondición y función variante
$$ \begin{aligned} P_C &\equiv 0 \leq d < h \leq |s| \land \min = d \land i = d+1 \\ Q_C &\equiv d \leq \min < h \land_L (\forall i : \Z)(d \leq i < h \Longrightarrow_L s[\min] \leq s[i])\\ f_V &= h-i \end{aligned} $$
<aside> ➕ Complejidad: $O(n^2)$
</aside>
<aside> 💡 Idea: Recorrer la lista e ir agregando cada elemento en la posición que le corresponde de la parte ya recorrida.
</aside>
void insertionSort(vector<int> &s) {
for (int i = 0; i < s.size(); i++) {
insert(s, i);
}
}
Invariante
$$ \text{mismos}(s, S_0) \land \Big(0 \leq i \leq |s| \land_L \text{ordenado}\big(\text{subseq}(s, 0, i)\big)\Big) $$
Precondición, postcondición y función variante
$$ P_C \equiv i = 0 \land s = S_0 \qquad Q_C \equiv \text{mismos}(s, S_0) \land \text{ordenado}(s) \qquad f_V = |s|-i $$
void insert(vector<int> &s, int i) {
for (int j = i; j > 0 && s[j] < s[j - 1]; j--) {
swap(s, j, j - 1);
}
}
Invariante
$$ \begin{aligned} 0 \leq j \leq i &\land \text{mismos}\big(\text{subseq}(s, 0, i+1), \text{subseq}(S_0, 0 , i+1)\big) \\ &\land \text{subseq}(s, i+1, |s|) = \text{subseq}(S_0, i+1, |s|) \\ &\land \text{ordenado}\big(\text{subseq}(s,0,j)\big) \land \text{ordenado}\big(\text{subseq}(s,j,i+1)\big) \\ &\land(\forall k : \Z)(j < k \leq i \Longrightarrow_L s[j] < s[k]) \end{aligned} $$
<aside> ➕ Complejidad: $O(n^2)$
</aside>
vector<int> bubbleSort(vector<int> lista) {
for (int i=0; i < lista.size(); i++) {
burbujeo(lista, i);
}
return lista;
}
void burbujeo(vector<int> &lista, int i) {
for (int j = lista.size() - 1; j > i; j--) {
if (lista[j] < lista[j - 1]) {
swap(lista, j, j - 1);
}
}
}
<aside> 💡 Idea: Comparar cada elemento de la lista con el siguiente intercambiándolos si están en orden equivocado.
</aside>
Invariante
<aside> ➕ Complejidad: $O(n^2)$
</aside>
vector<int> countingSort(vector<int> &lista) {
vector <int> conteo = contar(lista);
return reconstruir(lista, conteo);
}
vector<int> contar(vector<int> &lista) {
// creo un vector inicializado en 0
// cuya longitud sea igual a una cota máxima
vector <int> conteo(COTA, 0);
for (int i = 0; i < lista.size(); i++) {
conteo[lista[i]]++;
}
return conteo;
}
vector <int> reconstruir(vector <int> &lista, vector <int> conteo) {
vector <int> resultado(lista.size());
int indice_conteo = 0;
for(int i = 0; i < lista.size(); i++) {
// Ignoro valores nulos
while (conteo[indice_conteo] == 0) {
indice_conteo++;
}
resultado[i] = indice_conteo;
conteo[indice_conteo]--;
}
return resultado;
}
<aside> 💡 Idea: Asumimos que los elementos de la lista están entre $0$ y $k$ con $k$ arbitrario. El algoritmo calcula la cantidad de apariciones de cada elemento (almacena las cantidades en una lista nueva) y rearma la lista original poniendo la cantidad correspondiente de $i$-ésimos elementos de la segunda lista.
</aside>
Invariante
<aside> ➕ Complejidad: $O(n)$ → Es precondición que la lista tenga una cota máxima
</aside>