quick sort using filter in JavaScript

Question

I am working on quick sort using recursion and filter, but the recursion is not working correctly. It returns to the first half of the list sorted + extra (pivot and second half of the list from the last recursion), but second half of the list disappears. Here is my code.

const {
  List
} = require('immutable')
const quicksort = function(list) {
  if (list.size <= 1) {
    return list;
  }

  pivot = list.last();
  part1 = list.pop().filter((x) => x <= pivot);
  part2 = list.pop().filter((x) => x > pivot);

  return quicksort(part1).concat(list.last(), quicksort(part2));
};

console.log("quicksort: " + quicksort(List([4, 7, 3, 6, 8, 7, 1, 2, 2, 1, 5])));

and it prints out

quicksort: List [ 1, 1, 2, 3, 3, 3, 5 ]

The first time quicksort is called,

part1 is [ 4, 3, 1, 2, 2, 1 ]

pivot is 5

part2 is [ 7, 6, 8, 7 ]

and basically, [ 7, 6, 8, 7 ] just disappears.

I appreciate any insight and advice. Thank you!

ibrahim mahrir · Accepted Answer · 2017-02-02 04:25:32Z

3

var, let or const declaration is missing. Without those, pivot, part1 and part2 are global variables. After sorting part1, part2 has been overwritten to an empty list (because that was the terminating circumstance of the previous branch of the recursion). Just let your vars be properly local :p. Like this:

let pivot = list.last();
let part1 = list.pop().filter((x) => x <= pivot);
let part2 = list.pop().filter((x) => x > pivot);

Lesson: "use strict";

edited Feb 2, 2017 at 4:25

ibrahim mahrir

31.8k5 gold badges50 silver badges78 bronze badges

answered Feb 2, 2017 at 4:22

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

neko_studies_prog Over a year ago

I see. That explains it a lot. It works now!! Thank you so much!

Collectives™ on Stack Overflow

quick sort using filter in JavaScript

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related