is QuickSort fastest?
Tags: algorithms, javascript, programming, quicksort
Published: 2022-12-17 17:17:25

Hey guys, lets gonna practice with the [QuickSort](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Quicksort#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
- A little preparation in [choosing a pivot](https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot)
- Used in [V8](https://v8.dev/blog/array-sort) before Timsort algorithm

**Let's visualize the algorithm:**

<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j505wku2bnd7e0c38ywv.png" alt="quick sort steps" />


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):**

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

```js
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](https://leetcode.com/problems/sort-an-array/submissions/850557047/)

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! 😊