CODEWITHSUNDEEP
algorithmsortingquicksort
Ujjwal Vaish
Ujjwal Vaish

Reputation: 375

Quick sort working and not-working code comparison

I have two implementations of quick-sort with a small change and I am failing to understand why one of them works and other doesn't.

Not-working 

function quickSort(arr, left = 0, right = arr.length){
  console.log(arr,left,right)
  if (left < right){
    let middle = pivot(arr, left, right)
    console.log(middle)
    quickSort(arr, left, middle-1)
    quickSort(arr, middle+1, right)
  }
  return arr
}


function pivot(arr, start = 0, end = arr.length)
// returns the correct index
{
 function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let index = start;
  for (let i = start + 1; i < end; i++){
    if(pivot > arr[i]){
      index++
      swap(arr,i,index)
    }
  }
  swap(arr,index, start)
  return index
}

Working The only change here is instead of using the "end" argument, I am using arr.length in the for loop

function quickSort(arr, left = 0, right = arr.length){
  console.log(arr,left,right)
  if (left < right){
    let middle = pivot(arr, left, right)
    console.log(middle)
    quickSort(arr, left, middle-1)
    quickSort(arr, middle+1, right)
  }
  return arr
}


function pivot(arr, start = 0, end = arr.length)
// returns the correct index
{
 function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let index = start;
  for (let i = start + 1; i < arr.length; i++){
    if(pivot > arr[i]){
      index++
      swap(arr,i,index)
    }
  }
  swap(arr,index, start)
  return index
}

Both the logics are identical and I am unable to find a difference. Ideally, I would want to reuse the end argument inside my code. Thanks!

Upvotes: 0

Views: 42

Answers (1)

Sajib
Sajib

Reputation: 414

Observing your code, I get that quickSort(arr, left, right) will sort the range of [left, right). Means that you are not including arr[right] in the sorting algorithm. So, when you are recursively calling quickSort(arr, left, middle-1), arr[middle-1] will not be included ever in your sorting algorithm. So, it doesn't work. You should make it quickSort(arr, left, middle). However, in your mentioned "working" code, you are always iterating till the last element of the whole array, that's why the case is being handled. But it should never be done that way because it is not contributing anything to improve the complexity.

Upvotes: 1

Related Questions