Quicksort
Quicksort es un algoritmo de ordenamiento in situ (sin necesidad de memoria adicional) que utiliza la técnica de divide y vencerás para ordenar un array de elementos comparables. El algoritmo selecciona un elemento como pivote y divide el array en dos subarrays: uno con elementos menores que el pivote y otro con elementos mayores. Luego, aplica recursivamente el mismo proceso a los subarrays hasta que cada subarray tenga un solo elemento. Finalmente, combina los subarrays ordenados junto con el pivote.
function quicksort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
}
return [...quicksort(left), pivot, ...quicksort(right)];
}
const arrayToSort = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArrayQuicksort = quicksort(arrayToSort);function quicksort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
}
return [...quicksort(left), pivot, ...quicksort(right)];
}
const arrayToSort = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArrayQuicksort = quicksort(arrayToSort);Explicación
- Selecciona un elemento como pivote (en este caso, el primer elemento).
- Divide el array en dos subarrays: uno con elementos menores que el pivote y otro con elementos mayores.
- Recursivamente, aplica el mismo proceso a los subarrays.
- Combina los subarrays ordenados junto con el pivote.
Mergesort
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
function mergesort(arr) {
if (arr.length <= 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergesort(left), mergesort(right));
}
const arrayToSortMerge = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArrayMerge = mergesort(arrayToSortMerge);function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
function mergesort(arr) {
if (arr.length <= 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergesort(left), mergesort(right));
}
const arrayToSortMerge = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
const sortedArrayMerge = mergesort(arrayToSortMerge);Explicación
- Divide el array en mitades hasta que cada subarray tenga un solo elemento.
- Combina los subarrays de dos en dos, asegurándose de que los elementos estén en orden.
Diferencias entre Quicksort y Mergesort
- Mecanismo de División: Quicksort utiliza un pivote para dividir el array en dos partes. Mergesort divide recursivamente el array por la mitad hasta que cada subarray tenga un solo elemento.
- Eficiencia en el Peor Caso: Quicksort puede degradarse a O(n^2) en el peor caso. Mergesort tiene un rendimiento más constante, O(n log n) en todos los casos.
- Espacio en Memoria: Quicksort suele ser in situ (sin necesidad de memoria adicional). Mergesort requiere espacio adicional para almacenar los subarrays temporales.