[Quick Sort] Quick Select

• Quck sort, Quick Select

  Quick Sort

    function quickSortWidthEndPivot(arr, start, end) {
        if (start >= end) {
            return arr;
        }
  
        let left = start;
        let right = end - 1;
        let pivot = end;
  
        while (left <= right) {
            const low = arr[left];
            const high = arr[right];
            if (low > arr[pivot] && high < arr[pivot]) {
                swap(arr, left, right);
            }
  
            if (low <= arr[pivot]) left++;
            if (high >= arr[pivot]) right--;
        }
  
        swap(arr, left, pivot);
        pivot = left; // renew pivot position for next process
  
        quickSortWidthEndPivot(arr, start, pivot - 1);
        quickSortWidthEndPivot(arr, pivot + 1, end);
  
        return arr;
    }
  
    const sortedWithEnd = quickSortWidthEndPivot(arr, 0, arr.length - 1);
    console.log('sortedWithEnd pivot:: ', { sortedWithEnd });

  • Time: O(nlogn) worst n^2

  • Space: O(logn) worst n

    Quck Select

  • Write a function that takes in an array of distinct integers as well as an integer k and returns kth smallest integer in that array. The function should this in linear time, on average

    1st try with counting sort

    function quickselect(arr, k) {
    const min = Math.min(...arr);
    const minusNum = min < 0 ? Math.abs(min) : min;
    
    const counts = [];
    for (let i = 0; i < arr.length; i++) {
      const num = arr[i] + minusNum;
      if (counts[num] === undefined) 
        counts[num] = 0;
      counts[num] += 1;
    }
    
    console.log(counts);
    
    let sum = 0;
    for (let i = 0; i < counts.length; i++) {
      const count = counts[i];
      if (count === undefined) continue;
      sum += count;
      if (sum < k) continue;
      return i - minusNum;
    }
    return 0;
    }

    Time: O(MAX(arr) + minusNum)

    Space: O(MAX(arr) + minusNum)

    only satisfied when elements in arr sparsely distributed (distributed continuously)

    2nd try with iteration

    function quickselect(arr, k) {
    const indexToSelect = k - 1;
    
    let start = 0;
    let end = arr.length - 1;
    
    while (true) {
      if (start > end) {
        throw new Error('not supposed to be');
      }
    
      let pivot = end;
      let left = start;
      let right = end - 1;
    
      while (left <= right) {
        const low = arr[left];
        const high = arr[right];
    
        if (low >= arr[pivot] && high <= arr[pivot]) {
          swap(arr, left, right);  
        }
    
        if (arr[left] < arr[pivot]) {
          left++;
        }
        if (arr[right] > arr[pivot]) {
          right--;
        }
    
        console.log({
          start, end, pivot,
          left,
          right,
          indexToSelect,
          arr
        });
      }
      console.log('>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>')
    
      swap(arr, pivot, left);
      pivot = left;
      if (pivot === indexToSelect) {
        return arr[pivot];
      }
    
      if (pivot > indexToSelect) {
        end = pivot - 1;
      } else if (pivot < indexToSelect) {
        start = pivot + 1;
      }
    
    }
    
    

}

function swap(arr, a, b) {
  [arr[a], arr[b]] = [arr[b], arr[a]];
}
```

Time: O(nlogn) worst n^2

Space: O(logn) worst n