Quicksort algorithm – Sort an integer array in place.

As we know Quicksort algorithm follows Divide and Conquer rule. It divides array elements in to smaller parts and performing the sort operations on those divided smaller parts. It mainly useful for large datasets.

Select middle element which is to be called as pivot element.

Scan Array and compare all array elements with the selected pivot element and arrange them in such a way that, elements less than the pivot element are to it’s left and greater than pivot is to it’s right.

Read On Dglobaltech:

Software Engineering Prep Guide

Interview Brainteaser

Finally, perform the same operations on left and right side elements to the pivot element.

Explanation: For Example you have given Input Array => [3,7,8,5,2,1,9,5,4]. Now First you will find out the middle point. Which is right-index = 8, left-index = 0; (0+8)/2 = 4.

Now We will scan array and check if left scan item is greater than middle point or not? Same right scan item is less than middle point or not and if that conditions satisfies we will swap the item.

If you look at our example we have middle point 4, now from left side first 7 is greater than middle point and 1 is less than middle point swap them out. Then swap 8 and 2.

Now, You will have to recursively scan the array until you will have sorted array in-place.

Using Recursion we can achieve time complexity O(N) and in place operation gives us O(1) Space complexity.

We will add these steps into code.

const swapNumbers = (arr, leftIndex, rightIndex) => {
  let temp = arr[leftIndex];
  arr[leftIndex] = arr[rightIndex];
  arr[rightIndex] = temp;
}
const dividedArray = (arr, left, right) => {
  let middlePoint = arr[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;
  while (i <= j) {
    while (arr[i] < middlePoint) {
      i++;
    }
    while (arr[j] > middlePoint) {
      j--;
    }
    if (i <= j) {
      swapNumbers(arr, i, j);
      i++;
      j--;
    }
  }
    return i;
}

const quickSort = (arr, left, right) => {
    let index;
    if (arr.length > 1) {
        index = dividedArray(arr, left, right);
        if (left < index - 1) { 
            quickSort(arr, left, index - 1);
        }
        if (index < right) { 
            quickSort(arr, index, right);
        }
    }
    return arr;
}
const arr = [3,7,8,5,2,1,9,5,4];

console.log(quickSort(arr, 0, arr.length - 1));

Try Yourself on Coding Playground: