is QuickSort fastest?

Hey guys, lets gonna practice with the QuickSort algorithm.

This algorithm is based on the divide and conquer approach of programming. As a rule, the Quicksort is an in-place sorting algorithm, but that is not necessary.

This algorithm, on average, takes O(nlog n) time to sort n items. In the worst case, it makes O(n^2) (good implementations as a rule take O(nlog n))
The space complexity is O(log n) but it depends on implementation. Another interesting thing is that we can make this algorithm stable and unstable as well. And as for the stable case, it will take O(n) space or O(1) for in-place implementations
A little preparation in choosing a pivot
Used in V8 before Timsort algorithm

Let's visualize the algorithm:

During selecting the pivot we can sort the first, pivot, and last element - it is a constant operation and doesn't take additional time.

Rules for the code (as usual):

Choose the right names for variables
Choose the right loop statements: for, while, forEach, reduce etc.
Avoid excess conditions and comparisons for edge cases
Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity



class QuickSort {
  constructor(inputArray) {
    /**
     * it depends on the requirements, in our case we sort in place
     */
    this.inputArray = inputArray;
  }

  inputArray;

  swap = (arr, firstIndex, secondIndex) => {
    const temp = arr[firstIndex];
    arr[firstIndex] = arr[secondIndex];
    arr[secondIndex] = temp;
  };

  getMedianFrom3WithSwap = (arr, from = 0, to = arr.length - 1) => {
    const middleIndex = Math.round((from + to) / 2);

    if (arr[middleIndex] < arr[from]) {
      this.swap(arr, middleIndex, from);
    }

    if (arr[to] < arr[from]) {
      this.swap(arr, from, to);
    }

    if (arr[to] < arr[middleIndex]) {
      this.swap(arr, to, middleIndex);
    }

    return arr[middleIndex];
  };

  sortPartition = (arr, from, to) => {
    const pivot = this.getMedianFrom3WithSwap(arr, from, to);

    while (from <= to) {
      while (arr[from] < pivot) {
        from++;
      }

      while (arr[to] > pivot) {
        to--;
      }

      if (from <= to) {
        this.swap(arr, from, to);
        from++;
        to--;
      }
    }

    return [from, to];
  };

  sort = () => {
    const repeatSorting = (arr, from, to) => {
      if (arr.length < 2 || from > to) {
        return;
      }

      const [nextFrom, nextTo] = this.sortPartition(arr, from, to);

      repeatSorting(arr, from, nextTo);
      repeatSorting(arr, nextFrom, to);
    };

    repeatSorting(this.inputArray, 0, this.inputArray.length - 1);

    return this.inputArray;
  };
}

console.log(new QuickSort([7, 4, 3, 5, 6, 8, 1, 9]).sort());
console.log(new QuickSort([100, 3, 4, 5, 13, 7, 3, 0]).sort());
console.log(new QuickSort([1, 4, 3, 5]).sort());
console.log(new QuickSort([3, -1]).sort());

Check result on leetcode

Sources:
https://favtutor.com/blogs/quick-sort-cpp
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort

Let me know your thoughts in the comment section below! 😊

Blog

is QuickSort fastest?

Sebastian Leukhin

Join Our Newsletter. No Spam, Only the good stuff.

Related