trouble implementing quickSort in javascript

Question

I used timothy roughgardens partition where he chooses the first element, but it doesn't quite work the way I want it to.

function swap(items, firstIndex, secondIndex){
  var temp = items[firstIndex];
  items[firstIndex] = items[secondIndex];
  items[secondIndex] = temp;
}


function partition(arr, left, right) {
  left = left || 0;
  right = right || arr.length - 1;
  var pivot = arr[0];
  var i = left + 1;
  for (var j = left + 1; j < right; j++) {
    if (arr[j] < pivot) { 
      swap(arr, j, i);  //need to swap with left most array entry which is currently bigger than pivot
      i++;
    }
  }
  //swap pivot with right most element smaller than the pivot (i-1)
  swap(arr, left, i-1)
  // console.log(arr);
  // return i;
  return i - 1;
}



function quickSort(arr, start, end) { 
  start = start || 0;
  end = end || arr.length - 1;

  var pivotNewIndex = partition(arr, start, end);

  if (start < end) {
    quickSort(arr, start, pivotNewIndex - 1);
    quickSort(arr, pivotNewIndex + 1, end);
  }
  return arr;
}


var arr4 = [3, 8, 2, 1, 5];


console.log(quickSort(arr4)); --- > [ 1, 2, 3, 8, 5 ];

what am I doing wrong here? I think end is getting reassigned from the original end, how do i stop that

MBo · Accepted Answer · 2015-11-01 19:55:38Z

1

You choose the first element of the whole array as pivot of working range here:
var pivot = arr[0];
But have to use the first element of current segment
var pivot = arr[left];

And check and debug your partition cycle. You must have two pointers, one walking from the left end and another from the right end of segment. But I see both walk from left to right (don't know JS enough to correct this issue)

edited Nov 1, 2015 at 19:55

answered Nov 1, 2015 at 9:11

MBo

80.7k5 gold badges61 silver badges99 bronze badges

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

2 Comments

WinchenzoMagnifico Over a year ago

I changed that and I still get [1, 2, 3, 8, 5]

MBo Over a year ago

Another thoughts added

Collectives™ on Stack Overflow

trouble implementing quickSort in javascript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related