Skip to content

Add in-place sort to QuickSort.js #16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 10 commits into from
May 27, 2018
Merged

Conversation

robtaussig
Copy link
Contributor

I've always been a big fan of the in-place variation of the Quicksort algorithm. Not sure if you were looking for variations on existing implementations, but I thought it was different enough to warrant a pull request if you are interested.

It was also more performant when testing on arrays of 10,000 elements for integers between 0-10,000:

/*
const testTime = (callback) => {
	let time1 = performance.now();
	callback();
	let time2 = performance.now();
	return time2 - time1;
};

const arrOne = new Array(10000).fill(null).map(el => Math.floor(Math.random() * 10000));
const arrTwo = new Array(10000).fill(null).map(el => Math.floor(Math.random() * 10000));

const inPlace = testTime(() => QuickSort.sortInPlace(arrOne));
const nonInPlace= testTime(() => QuickSort.sort(arrTwo));

console.log(inPlace);
//=>9.799999999813735

console.log(nonInPlace);
//=>50.00000004656613
*/

@albin3
Copy link

albin3 commented May 25, 2018

#19

@codecov-io
Copy link

codecov-io commented May 26, 2018

Codecov Report

Merging #16 into master will not change coverage.
The diff coverage is 100%.

Impacted file tree graph

@@          Coverage Diff          @@
##           master    #16   +/-   ##
=====================================
  Coverage     100%   100%           
=====================================
  Files          77     78    +1     
  Lines        1602   1625   +23     
  Branches      283    289    +6     
=====================================
+ Hits         1602   1625   +23
Impacted Files Coverage Δ
src/algorithms/sorting/quick-sort/QuickSort.js 100% <ø> (ø) ⬆️
.../algorithms/sorting/quick-sort/QuickSortInPlace.js 100% <100%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update f93d12d...9c62394. Read the comment docs.

@robtaussig
Copy link
Contributor Author

I was wrestling around with the lint requirements, and trying to work around the no-param-reassign rule when doing the algorithm in-place. I think the result is a bit messier than I would have liked it, but I also don't imagine you'd want to change the linting rules for this.

@chrisVillanueva
Copy link

@robtaussig

Your contribution looks good. I have a question about the swap function.
Do you think a performance gain can be made by changing this:

 const swap = (left, right) => {
    const tempVariable = array[left];
    array[left] = array[right];
    array[right] = tempVariable;
 };

to

 const swap = (left, right) => {
    [ array[left] ,  array[right]  ]= [ array[right],  array[left] ];
 };

?

@robtaussig
Copy link
Contributor Author

@chrisVillanueva I've actually never seen that implementation before; that's very cool. I don't think there is a huge performance implication either way (tests below), but I do think using a destructured approach is clearer, since it doesn't require a tempVariable.

// This needs to be installed
var now = require("performance-now");

const testArray = [1,2,3,4,5,6];

const inplaceSwap = (array, left, right) => {
  const temp = array[left];
  array[left] = array[right];
  array[right] = temp;
};

const destructuredSwap = (array, left, right) => {
  [array[left], array[right]] = [array[right], array[left]];
};

//#1
console.log(testArray);
inplaceSwap(testArray, 2, 4);
//#2
console.log(testArray);
destructuredSwap(testArray, 2, 4);
//#3
console.log(testArray);

const testPerformance = (callback, timesPerTest = 1000, numTests = 1) => {
  const times = [];
  for (let i = 0; i < numTests; i++) {
    let totalTime = 0;
    for (let j = 0; j < timesPerTest; j++) {
      const time1 = now();
      callback();
      const time2 = now();
      totalTime += (time2 - time1);
    }
    times.push(totalTime);
  }
  const averageTotalTime = times.reduce((acc, val) => {
    acc = acc + val;
    return acc;
  }, 0) / times.length;
  const minTotalTime = times.reduce((acc, val) => {
    acc = acc > val ? val : acc;
    return acc;
  }, Infinity);
  const maxTotalTime = times.reduce((acc, val) => {
    acc = acc > val ? acc : val;
    return acc;
  }, -Infinity);

  console.log('Average Time Per Test: ', averageTotalTime, 'ms');
  console.log('Best Time Per Test: ', minTotalTime, 'ms');
  console.log('Worst Time Per Test: ', maxTotalTime, 'ms');
};

//#4
console.log(testArray);

//#5
testPerformance(() => {
  destructuredSwap(testArray, 0, 1);
}, 10001, 101);

//#6
console.log(testArray);

//#7
testPerformance(() => {
  inplaceSwap(testArray, 0, 1);
}, 10001, 101);

//#8
console.log(testArray);

#outputs

//#1 -> Original array positions
[ 1, 2, 3, 4, 5, 6 ]
//#2 -> Positions after single inplace swap @ index 2, 4
[ 1, 2, 5, 4, 3, 6 ]
//#3 -> Positions after single destructured swap @ index 2, 4
[ 1, 2, 3, 4, 5, 6 ]
//#4 -> Position of testArray prior to tests
[ 1, 2, 3, 4, 5, 6 ]

//#5 -> Results of destructured swap
Average Time Per Test:  0.7825327128709996 ms
Best Time Per Test:  0.6285290000008104 ms
Worst Time Per Test:  6.650336999999553 ms

//#6 -> Array after destructured swap test (since we performed it an odd number of times, it should not be in original position)
[ 2, 1, 3, 4, 5, 6 ]

//#7 -> Results of inplace swap
Average Time Per Test:  0.645358910890673 ms
Best Time Per Test:  0.5672350000020288 ms
Worst Time Per Test:  2.109961000001647 ms

//#8 -> Array after inplace swap test(since we performed it an odd number of times, it should not be in original position)
[ 1, 2, 3, 4, 5, 6 ]

@trekhleb
Copy link
Owner

@robtaussig thank you for in-place implementation! And also thank you for tests and clean code!

@trekhleb trekhleb merged commit bf5d7b3 into trekhleb:master May 27, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

5 participants