5
\$\begingroup\$

I wanted to implement a selection sort and wanted to make sure that I'm doing it correctly. I wanted to do it in a way that's efficient and use recursion. Please let me know if I am doing this correctly or if there is a better way for me to do it.

 /**
 * selectionSort
 * @param toSort
 * @param sorted
 * @returns {Array}
 */
function selectionSort(toSort, sorted=[]) {
    if (!toSort.length) {
        return sorted;
    }
    let minIndex = findMinimum(toSort);
    sorted.push(...toSort.splice(minIndex, 1))
    return selectionSort(toSort, sorted);
}

function findMinimum(arr) {
    let minIndex=0;
    arr.forEach(function (item, index) {
        if(item < arr[minIndex]) {
            minIndex = index;
        }
    })
    return minIndex;
}


const testCase = [64, 25, 12, 22, 11]
const answer = selectionSort(testCase);
\$\endgroup\$
  • \$\begingroup\$ Is this code using node.js? \$\endgroup\$ – dfhwze Sep 29 at 18:31
  • 1
    \$\begingroup\$ Why use recursion when a loop would do just fine? Recursion is just going to have a lot of stack buildup for large arrays and extra function calls. \$\endgroup\$ – jfriend00 Sep 29 at 19:18
  • \$\begingroup\$ A for loop is generally more efficient than .forEach() as there's no function call and new scope involved. Probably best to use for/of. \$\endgroup\$ – jfriend00 Sep 29 at 19:19
  • \$\begingroup\$ @jfriend00 I'm trying to familiarize myself with recursion more. I didn't know that it's better to use loops in some cases. Thanks for the tip with the for/of also \$\endgroup\$ – Christopher Chen Sep 29 at 23:48
5
\$\begingroup\$

I'd suggest the following changes:

  1. Use a loop instead of recursion
  2. Use for/of instead of .forEach()
  3. push a single value instead of using an array with one element in it
  4. cache the lowest value so far so you don't have to constantly refetch it on every comparison
  5. Use a temporary array for the sort so the function is non-destructive to the source array (consistent with most array methods)
  6. Use const where you can.

Code:

 /**
     * selectionSort
     * @param toSort (not modified)
     * @param sorted (new sorted array)
     * @returns {Array}
     */
    function selectionSort(toSort, sorted = []) {
        if (!toSort.length) {
            return sorted;
        }
        // make copy so we don't modify source
        const sortData =  toSort.slice();

        while (sortData.length) {
            const minIndex = findMinimum(sortData);
            sorted.push(sortData[minIndex]);
            // remove min item from data left to be sorted
            sortData.splice(minIndex, 1);
        }
        return sorted;
    }

    function findMinimum(arr) {
        let minIndex = 0, minValue = arr[0];
        for (const [index, item] of arr.entries()) {
            if (item < minValue) {
                minIndex = index;
                minValue = item;
            }
        }
        return minIndex;
    }


    const testCase = [64, 25, 12, 22, 11]
    const answer = selectionSort(testCase);
    console.log(answer);
\$\endgroup\$
  • \$\begingroup\$ I disagree with for...of...entries though. There is nothing wrong with using normal for when the use case is exactly what it was designed for. JS communitie's overuse of new constructs where they bring no benefit over the old ones is harmful for code readability and consistency. \$\endgroup\$ – Tomáš Zato - Reinstate Monica Sep 30 at 11:36
  • \$\begingroup\$ @TomášZato - I have no problem with a regular for loop. The OP was using .forEach() which I did not think was as good as some type of a for loop. In this case, the OP actually needs both the index and the value which for/of and .entries() hands you on a silver platter, thus why I used it. \$\endgroup\$ – jfriend00 Sep 30 at 15:23
  • \$\begingroup\$ I apologize, I read the post again and noticed that I misread arr.entries for Object.entries(arr). arr.entries is great. \$\endgroup\$ – Tomáš Zato - Reinstate Monica Sep 30 at 15:27
5
\$\begingroup\$

Review

  • findMinimum means to me that you find the minimum value in an array of items. Since your function returns the index instead, call it indexOfMinimum.
  • Prefer the use of const over let if you only assign a variable once: let minIndex = findMinimum(toSort); -> const minIndex = findMinimum(toSort);.
  • Use arrow notation to write more compact functions: function (item, index) -> (item, index) =>.
  • Your documentation seems like wasted space. If you document a public function (which is a good thing), put in some effort to write a clear description of the function, not just the name of the method copied.
  • Use whitespace to write more idiomatic javascript:
    • let minIndex=0; -> let minIndex = 0;
    • if(item < arr[minIndex]) -> if (item < arr[minIndex])

Rewritten:

function selectionSort(toSort, sorted=[]) {
    if (!toSort.length) {
        return sorted;
    }
    const minIndex = indexOfMinimum(toSort);
    sorted.push(...toSort.splice(minIndex, 1))
    return selectionSort(toSort, sorted);
}

function indexOfMinimum(arr) {
    let minIndex = 0;
    arr.forEach((item, index) => {
        if (item < arr[minIndex]) {
            minIndex = index;
        }
    })
    return minIndex;
}
\$\endgroup\$
  • \$\begingroup\$ Those are good suggestions. Thank you. What do you mean by more idiomatic javascript? \$\endgroup\$ – Christopher Chen Sep 29 at 23:51
  • 1
    \$\begingroup\$ I mean by following more standard practices, or in this case conventions and style guides. \$\endgroup\$ – dfhwze Sep 30 at 4:17
  • 1
    \$\begingroup\$ There we are. Feels good, doesn't it? :P \$\endgroup\$ – t3chb0t Oct 6 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.