quickselect into JavaScript

Question

I have scoured the internet for all the various versions of quicksort implementation to translate into JavaScript and many of them do not successfully port.

I haven't been able to figure out if this is due to me not knowing a nuance about Java or C++, or the examples that people posted are broken.

I am not optimizing for performance, but how readable and logical it is to me.

I have arrived at this implementation, but I noticed that it does not work.

Outputs are random (likely due to the Math.random()), but as I follow the algo, I get frustrated with this following test case.

Outputs range from 999, 3, 100, 2, and 1000. I cannot follow the logic and would really appreciate someone explaining what's happening to give such erratic results.

function swap(array, idxA, idxB) {
    var temp = array[idxA] 
    array[idxA] = array[idxB]
    array[idxB] = temp
}

function partitionStart(arr, left, right, pivotIdx) {
  var storeIdx = left, pivotVal = arr[pivotIdx];  
  swap(arr, pivotIdx, right)
  for (var i = left; i <right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, storeIdx, i)
      storeIdx++
    }
  }
  swap(arr, pivotIdx, right);
  return storeIdx;
}

function quickSelectLoop(arr, k) {
  var pivotIndex, pivotNewIdx, pivotDist, 
  left = 0, right = arr.length-1 

  while(true) {
    pivotIndex = Math.floor(Math.random()*arr.length)
    pivotNewIdx = partitionStart(arr, left, right, pivotIndex)
    pivotDist = pivotNewIdx - left

    if (pivotDist === k) {
      return arr[pivotNewIdx-1]
    } else if (k < pivotDist) {
      right = pivotNewIdx -1
    } else {
      k -= pivotDist+1
      left = pivotNewIdx + 1
    }
  }  
}

var test2 = [1000,999,1,2,3,100,105]
console.log(quickSelectLoop(test2, 4))

expected output from quickSelect(test2, 4) => 100 since 100 is the 4th smallest element in the collection

What is your desired/expected output for that particular input? — nnnnnn
– nnnnnn, Commented Aug 17, 2016 at 5:04
The below console log should output 100, the 4th smallest element in the test2 array — Anthony Chung
– Anthony Chung, Commented Aug 17, 2016 at 5:06
And the swap() implementation that you don't show just swaps the values between two array indices? — nnnnnn
– nnnnnn, Commented Aug 17, 2016 at 5:08
yes. I found it to be very straightforward using a temp variable, but can add. check the top. — Anthony Chung
– Anthony Chung, Commented Aug 17, 2016 at 5:08

user3707125 · Accepted Answer · 2016-08-17 06:48:05Z

4

Your current implementation has multiple flaws. I don't really understand what is the idea of your current code, so I'll try to explain how I understood your code, and then provide a corrected one.

partitionStart - partitions part of array from left to right indices using item at pivotIdx as parts separator. Returns index of separation sepIdx, such that every item before sepIdx is less than pivot item, and every item after it is greater or equal to it.

quickSelectLoop - selects k-th smallest item from the given array. Function relies on invariant that all items between left and right, while being in arbitrary order, are array's left..right smallest items, e.g.

if left = 0, right = 2, initial array = {0,1,2,3,4}, then arr = [A,B,C,x,x], where {A,B,C} = {0,1,2}, so arr = [2,1,0,4,3] and arr = [0,1,2,3,4] are both correct.

Corrected code with commentaries:

function partitionStart(arr, left, right) {  
  // You were passing pivotIdx here, I think that selecting pivotIdx 
  // should be this method's responsibility, so I moved the code here
  // Also you were taking pivotIdx ignoring left and right - fixed that
  var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left;
  var storeIdx = left, pivotVal = arr[pivotIdx]
  // You had a swap of pivot with the right here, 
  // which allowed you to traverse 1 item less in a cycle, 
  // but with the cost of one line of code - removed that
  for (var i = left; i <= right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, storeIdx, i)
      storeIdx++
    }
  }  
  // Here was a strange swap of pivot back from right to its position,
  // now it is not needed.
  return storeIdx;
}

function quickSelectLoop(arr, k) {  
  var pivotDist;   
  var left = 0, right = arr.length - 1;       
  while(right !== left) {
    // Maintaining: left <= k <= right, while enclosing left to right 
    pivotDist = partitionStart(arr, left, right)        
    // You were returning arr[k] here if pivotDist == k, 
    // but that is incorrect considering function's invariant - 
    // we can't make such a conclusion unless left == right.
    // I corrected that check - it is now located in the while loop.
    if (k < pivotDist) {
      right = pivotDist - 1;
    } else {
      // You were adding 1 here, which is incorrect, 
      // because item at pivotDist may be the answer as well.
      left = pivotDist;
    }
  }    

  // left == right, and we maintained 'left <= k <= right', so we have an answer
  return arr[k]
}

jsfiddle

edited Aug 17, 2016 at 6:48

answered Aug 17, 2016 at 6:40

user3707125

3,48916 silver badges23 bronze badges

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

9 Comments

Anthony Chung Over a year ago

Got it. So first core flaw was choosing a pivot element based on arr length and not dist between left and right pointers. Second was that I cannot assume items btwn left and right pointers contain the smallest items. (could be partitioning towards the other side. With each iteration of while loop, left or right index should be moving closer inwards. Depending on comparison btwn pivotDist and k, left/right is reassigned

Anthony Chung Over a year ago

I saw two implementations of partition, this one swapped the pivot element with the end, partitioned the halves and tracked the starting point of the "larger half". upon completion, the partition switched it back. I did not manage state of my arr length or pivot at all in my interpretation.

Anthony Chung Over a year ago

thank you user3703125! I will study this and then try to implement it on my own without looking again.

user3707125 Over a year ago

@AnthonyChung, "Second was that I cannot assume items btwn left and right pointers contain the smallest items.", - no, I meant exactly the opposite: you can assume that sorted version of array will contain exactly the same items at indices between left and right, but exact positions of items within these boundaries may differ. In other words quickSelectLoop always guarantees you that any item in arr between left and right will have index between left and right in sorted version of arr.

Ivan Kuckir Over a year ago

This implementation causes an infinite loop, when some values occur multiple times in an input.

|

Collectives™ on Stack Overflow

quickselect into JavaScript

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related