Quicksort in JavaScript ES6

Quicksort: Divide and Conquer

  1. Find a pivot in the middle; 4 5 [3] 1 2
  2. Swap pivot with the last element; 4 5 <2> 1 <3>
  3. Set pivot index (pi) to the start index of array; pi = 0
  4. Loop from the start to the end of array; i = 0, 1, 2, 3
    let pi = start index = 0
    if element < pivot, swap element with pi, increment pi
    a. at i = 0, 4 < 3 is false , so skip; P{4} 5 2 1 3
    b. at i = 1, 5 < 3 is false, so skip; P{4} 5 2 1 3
    c. at i = 2, 2 < 3 is true, swap arr[i] with arr[pi], pi++ ; <2> P{5} <4> 1 3
    d. at i = 3, 1 < 3 is true, swap arr[i] with arr[pi], pi++ ; 2 <1> P{4} <5> 3
  5. Swap pi with last element; 2 1 <3> 5 <4>
  6. Return pivot index (pi) = 2 with array sorted by first partition call; 2 1 [3] 5 4
  7. Anything smaller than pivot value 3 will be on the left side, and bigger on the right side
  8. Do Step 1-7 on the subset of array on left side of pivot and same for the right side
  9. Recursion
  10. Doned
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};

partition = (arr, start, end) => {
let pivotIndex = start;

// prevent O(n*n) time complexity by selecting pivot from the middle
const pivotSelectedInTheMiddle = start + Math.ceil((end - start) / 2);
swap(arr, end, pivotSelectedInTheMiddle);

for(let i = start; i < end; i++) {
if(arr[i] <= arr[end]) {
swap(arr, i, pivotIndex);
pivotIndex++;
}
}

swap(arr, pivotIndex, end);
return pivotIndex;
}

quicksort = (arr, start = 0, end = arr.length - 1) => {
if (start < end) {
let pivotIndex = partition(arr, start, end);
quicksort(arr, start, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, end);
}
return arr;
}

let arr = [];
for(let i = 0; i < 10; i++) {
arr.push(Math.round(Math.random() * 100));
}

const sortedArr = quicksort(arr);
console.log(sortedArr);

Console output:

1
2
3
4
5
6
7
Original Array:  [ 33, 19, 25, 63, 66, 66, 67, 34, 76, 56 ]
after partition: [ 33, 19, 25, 63, 66, 56, 34, 66, 76, 67 ] start 0 end 9 pi 7
after partition: [ 33, 19, 25, 34, 56, 63, 66, 66, 76, 67 ] start 0 end 6 pi 5
after partition: [ 19, 25, 56, 34, 33, 63, 66, 66, 76, 67 ] start 0 end 4 pi 1
after partition: [ 19, 25, 33, 34, 56, 63, 66, 66, 76, 67 ] start 2 end 4 pi 3
after partition: [ 19, 25, 33, 34, 56, 63, 66, 66, 67, 76 ] start 8 end 9 pi 8
Sorted Array: [ 19, 25, 33, 34, 56, 63, 66, 66, 67, 76 ]

Related Questions

[aka relatives aka family aka never ending drama]

  1. Dive into Quicksort's time complexity where you discover the truth on do I even math.

  2. Just find out about Hoare and Lomuto partition. What the. Quicksort with different partitions

  3. And of cos, Interview questions on quicksort


hexo cheatsheet for noobs

Serve locally

1
$ hexo serve

Create a new post

1
$ hexo new this-is-a-post

Deploy to firebase or any hosting platform with changes to layout

1
2
3
$ hexo clean
$ hexo generate
$ firebase deploy

// You can just type the inital of the command and it will work well.
// $ hexo s is the same as $ hexo serve


hexo + amp

I was told ⚡ page will bring me amazing speed and rank in google search. THOU LIE. Google search returns default index.html, not my amp.html. ⚡ amp logo does not appear on google search!

-> Update: Day 5, …

-> Update: Day 8, I still haven’t gotten my amp logo. WHY WHY WHY!

-> Update: Day 10, HIP HIP HURRAY. Senpai google has noticed me.

Amp site loads insanely fast for new user despite a long dreadful wait on my side for Google to cache/notice my site. Amp logo does not appear instantly after the article is deployed. The estimated time for amp logo to be reflected for the first amp post is about 10 days for me.

Notice how the 2 days ago content has amp logo but not the 3 days ago content.

Same for the quicksort article that was posted 3 days ago. NO LOGO.

Beside waiting for google to crown my site with a ⚡ amp logo, I came across a submit button at https://search.google.com/test/amp .

I clicked the submit button… twice. ( ͡° ω ͡°)