1
\$\begingroup\$

Background

I am re-writing a series of algorithms together with a colleague that we are going to later on publish in a packet for the community.

To start, I picked the typical bubble sort algorithm.

Objectives

  1. The function must be pure
  2. It must be efficient
  3. It must obey the complexities listed in https://en.wikipedia.org/wiki/Bubble_sort

Please note that by "being pure" it doesn't mean that it's inside code cannot have impurity. It merely means that the PUBLIC API of the function must be pure and it must not affect anything outside of its scope.

Code

//PS: NOT really using lodash. Just copy pasted this one function xD
const isFunction = require("lodash.isfunction");
const defaultCompare = require("./defaultCompare");

const bubble = ( array, fnCompare = defaultCompare ) => {

    if( !isFunction(fnCompare) )
        throw new Error("fnCompare must be a function");

    if(!Array.isArray(array))
        throw new Error("array must be an Array");

    if (array.length === 0)
        return [];

    //shallow copy
    const clonedArray = array.slice();

    //Optimized bubble sort: https://en.wikipedia.org/wiki/Bubble_sort
    let size = clonedArray.length;
    do{
        let newSize = 0;
        for( let i = 1; i < size; i++){
            if( fnCompare( clonedArray[i - 1], clonedArray[i] ) > 0 ){
                swap( clonedArray, i - 1, i );
                newSize = i;
            }
        }
        size = newSize;
    }while( size !== 0);

    return clonedArray;
};

const swap = (array, index1, index2) => {
    const temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
};

module.exports = bubble;

What do I want?

I am looking for any flaws in the code that could compromise objectives 1 and 3.

If you have an idea on how to improve object 2 (efficiency), I am all ears as well!

\$\endgroup\$
  • \$\begingroup\$ I wonder if you really need/want to clonedeep your array, as you will never modify your items anyway. const clonedArray = [...array]; seems enough ? You then let your user chose what to do with these items \$\endgroup\$ – Logar Nov 17 '17 at 13:32
  • \$\begingroup\$ also I think the swapping part would be more efficient if done this way : [array[i], array[i + 1]] = [array[i + 1], array[i]]; \$\endgroup\$ – Logar Nov 17 '17 at 13:42
  • \$\begingroup\$ I am working now on following your cloning suggestion. I will also remove recursivity. Keep on with the ideas ! \$\endgroup\$ – Flame_Phoenix Nov 17 '17 at 14:41
  • \$\begingroup\$ Not really pure when you throw to an unknown outside handler, if any, so basically terminating the execution of the calling context. \$\endgroup\$ – Blindman67 Nov 17 '17 at 16:00
  • \$\begingroup\$ Also you can not call your code pure if any dependencies are not pure. \$\endgroup\$ – Blindman67 Nov 17 '17 at 16:16
0
\$\begingroup\$

With the given feedback I was able to remove the deepclone and to remove recursivity, which resulted in speed gains and simplicity gains.

The final version of the algorithm is now in the question ( I updated it ) and I will now mark this thread as solved.

| improve this answer | |
\$\endgroup\$

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.