quicksort-versus-mergesort

QuickSort wins MergeSort at sorting Array

  • QS is an in place sort [means swap elements within 1 array only]
  • MS requires O(N) extra storage [need to assign new arrays to store value]
  • Tail recursive, tail call optimizations [NO IDEA WHAT IT MEANS]
  • Everyone is saying QS is practical

MergSort wins QuickSort at sorting Linked List

reference: http://www.geeksforgeeks.org/quick-sort/


apply-of-undefined

Error:

If you get the error below out of a sudden, it’s probably because one of your million dependencies screwed up.

1
TypeError: Cannot read property 'apply' of undefined

Solution:

Use tilde ~ for your dependency in package.json. ~ allows patches only, while ^ allows minor changes and patches.
For production, I highly recommend you to ~ your important dependencies. I learnt it the hard way. ~.~ tmd

1
2
3
4
5
6
7
Package.json
{
"name": "toomuch",
"dependencies": {
"hexo": "~3.2.0",
}
}

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. ( ͡° ω ͡°)