# Making bubble sort pure and efficient

## 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!

• 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 Commented Nov 17, 2017 at 13:32
• also I think the swapping part would be more efficient if done this way : [array[i], array[i + 1]] = [array[i + 1], array[i]]; Commented Nov 17, 2017 at 13:42
• I am working now on following your cloning suggestion. I will also remove recursivity. Keep on with the ideas ! Commented Nov 17, 2017 at 14:41
• Not really pure when you throw to an unknown outside handler, if any, so basically terminating the execution of the calling context. Commented Nov 17, 2017 at 16:00
• Also you can not call your code pure if any dependencies are not pure. Commented Nov 17, 2017 at 16:16