Algunas notas sobre el ordenamiento por mezcla
24 de febrero de 2022
Algunas notas acerca del algoritmo de Ordenamiento por Mezcla.
Descripción
Algoritmo recursivo fundamentado en la estrategia «divide y vencerás». Dos componentes principales:
- Una función para separar listas recursivamente hasta que recibe un único elemento.
- Una función que combina dos elementos ya ordenados en una lista ordenada.
Complejidad temporal
Pseudocódigo
Input: A = [A_1, A_2, …, A_n];\\Output: B = [B_1, B_2, …, B_n];\\[10pt]function \enspace MergeSort(A)\\\quad n \leftarrow length(A);\\\quad if \space n \leqslant then:\\\quad\quad return \space A;\\\quad else:\\\quad\quad l \leftarrow [A_1, …, A_{n/2}];\\\quad\quad r \leftarrow [A_{(n/2)+1}, …, A_n];\\\quad\quad L \leftarrow MergeSort(l);\\\quad\quad R \leftarrow MergeSort(r);\\\quad\quad B \leftarrow Merge(L, R);\\\quad\quad return \space B;\\\quad end \space if;\\end \space function;\\[10pt]function Merge(L, R)\\\quad n \leftarrow length(L) + length(R);\\\quad B \leftarrow [\space];\\\quad i \leftarrow 0;\\\quad j \leftarrow 0;\\\quad for \space k \leftarrow 0 \space to \space n \space do:\\\qquad if \space i \leqslant length(L) \space and \space j \leqslant length(R) \space then:\\\qquad\quad if \space L[i] \leqslant R[j] \space then:\\\qquad\qquad B[k] \leftarrow L[i];\\\qquad\qquad i \leftarrow i + 1;\\\qquad\quad else \space if \space L[i] \text{\textgreater} R[j] \space then:\\\qquad\qquad B[k] \leftarrow R[j];\\\qquad\qquad j \leftarrow j + 1;\\\qquad\quad end \space if;\\\qquad else \space if \space i + 1 \leqslant length(L) \space then:\\\qquad\quad B[k] \leftarrow L[i];\\\qquad\quad i \leftarrow i + 1;\\\qquad else \space if \space j + 1 \leqslant length(R) \space then:\\\qquad\quad B[k] \leftarrow R[j];\\\qquad\quad j \leftarrow j + 1;\\\qquad end \space if;\\\quad end \space for;\\\quad return \space B;\\end \space function;
Implementación en Rust
pub fn merge_sorted_arrays(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
let left_length = left.len();
let right_length = right.len();
// El array resultante tendrá el tamaño de los dos arrays que se pasen
let mut sorted_items = vec![0; left_length + right_length];
let mut i = 0;
let mut j = 0;
// Iterar sobre el array que vamos a rellenarcon elementos de los arrays
// izquierdo o derecho
for k in 0..sorted_items.len() {
// Si ninguno de los punteros "i" ni "j" han llegado a su límite
if i + 1 <= left.len() && j + 1 <= right.len() {
// Decidir entre el elemento actual del array izquierdo
// y el elemento actual del array derecho cuál de los dos será
// el siguiente para el array final
if left[i] <= right[j] {
sorted_items[k] = left[i];
i = i + 1;
} else if left[i] > right[j] {
sorted_items[k] = right[j];
j = j + 1;
}
} else if i + 1 <= left.len() {
// Si sólo el puntero "i" no ha alcanzado el límite
// —y por tanto "j" lo ha hecho—
sorted_items[k] = left[i];
i = i + 1;
} else if j + 1 <= right.len() {
// Si sólo el puntero "j" no ha alcanzado el límite
// —y por tanto "i" lo ha hecho—
sorted_items[k] = right[j];
j = j + 1;
}
}
sorted_items
}
pub fn sort_array(unsorted_array: &Vec<i32>) -> Vec<i32> {
let n = unsorted_array.len();
if n <= 1 {
// Caso base: si el input es de longitud 1,
// entonces está ya ordenado: devolverlo
let sorted_array = unsorted_array.to_vec();
sorted_array
} else {
// Si el input es de longitudo dos o mayor
// 1. Separarlo
let (left, right) = unsorted_array.split_at(n / 2);
let left_vec = left.to_vec();
let right_vec = right.to_vec();
// 2. Ordenarlo recursivamente
let left_sorted = sort_array(&left_vec);
let right_sorted = sort_array(&right_vec);
let sorted_array_1 = merge_sorted_arrays(left_sorted, right_sorted);
sorted_array_1
}
}
fn main() {
let unsorted_array: Vec<i32> = vec![2, 1, 4, 3];
let sorted_array = sort_array(&unsorted_array);
println!("unsorted_array: {:?}", unsorted_array);
println!("sorted_array: {:?}", sorted_array);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn works_with_sorted_arrays() {
let unsorted_array = vec![1, 2];
let sorted_array = sort_array(&unsorted_array);
let expected_result = vec![1, 2];
assert_eq!(expected_result, sorted_array);
}
#[test]
fn works_with_simple_unsorted_array() {
let unsorted_array = vec![2, 1];
let sorted_array = sort_array(&unsorted_array);
let expected_result = vec![1, 2];
assert_eq!(expected_result, sorted_array);
}
#[test]
fn works_with_simple_uneven_lenght_arrays() {
let unsorted_array = vec![2, 1, 3];
let sorted_array = sort_array(&unsorted_array);
let expected_result = vec![1, 2, 3];
assert_eq!(expected_result, sorted_array);
}
#[test]
fn it_works_with_sorted_arrays() {
let left = vec![1, 2];
let right = vec![3, 4];
let merged = merge_sorted_arrays(left, right);
let expected_result = vec![1, 2, 3, 4];
assert_eq!(expected_result, merged);
}
#[test]
fn it_works_with_splits() {
let left = vec![3, 4];
let right = vec![1, 2];
let merged = merge_sorted_arrays(left, right);
let expected_result = vec![1, 2, 3, 4];
assert_eq!(expected_result, merged);
}
#[test]
fn it_works_with_uneven_length_lists() {
let left = vec![3, 4, 5];
let right = vec![1, 2];
let merged = merge_sorted_arrays(left, right);
let expected_result = vec![1, 2, 3, 4, 5];
assert_eq!(expected_result, merged);
}
#[test]
fn it_works_with_single_item_lists() {
let left = vec![3];
let right = vec![1];
let merged = merge_sorted_arrays(left, right);
let expected_result = vec![1, 3];
assert_eq!(expected_result, merged);
}
}