es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Este algoritmo de ordenamiento quicksort del libro Grokking algorithm es correcto?

31 Jul, 2023 Programación

Vi en otros artículos que quicksort debería ser un algoritmo “in place”, ¿así que esta implementación es correcta? Aquí, el autor está creando nuevos arreglos en cada paso de recursión.

    function quickSort(arr) {
    if (arr.length < 2) {
        return arr
    } else {
        let pivotIdx = getRandom(arr.length)
        let pivot = arr[pivotIdx]
        let [leftArr, rightArr] = partition(pivotIdx, arr)

        return [...(quickSort(leftArr)) , ...[pivot] , ...(quickSort(rightArr))]
    }
}

function getRandom(maxInt) {
    return Math.floor(Math.random() * maxInt)
}

function partition(pivotIdx, arr) {
    let leftArr = []
    let rightArr = []
    let pivot = arr[pivotIdx];

    for (let i=0; i< arr.length; i++) {
        if (i === pivotIdx) continue;

        if (pivot > arr[i]) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }

    return [leftArr, rightArr]
}

quicksort([44,1,2,3])
Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Como experto en tecnología de la información especializado en algoritmos y estructuras de datos, diría que la implementación del algoritmo de ordenamiento quicksort en el código proporcionado no es un algoritmo in situ. En QuickSort, un algoritmo de ordenamiento in situ significa que no requiere espacio adicional en la memoria para almacenar matrices intermedias. Sin embargo, en el código proporcionado, los autores están creando dos matrices nuevas en cada paso de recursión, es decir, la matriz izquierda y la matriz derecha. Por lo tanto, esta implementación no es eficiente y no cumple con los criterios de un algoritmo in situ.

    Para convertir quicksort en un algoritmo in situ, necesitamos modificar la función de partición para reorganizar los elementos dentro de la matriz en lugar de crear nuevas matrices. Un algoritmo in situ para quicksort se vería algo así:

    function quickSort(arr, low, high) {
    if (low < high) {
        let pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    let pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    let temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

const arr = [44, 1, 2, 3];
const sortedArr = quickSort(arr, 0, arr.length - 1);
console.log(sortedArr);

    En esta implementación, estamos modificando la matriz original en lugar de crear nuevas. Por lo tanto, es un algoritmo Quicksort in situ.

Comments are closed.