[Algo] the mathematical theory of QuickSort

1  We start with the simplest : guess number game :I have a number from 1 to 64, you can ask me questions(Y/N) and how many questions to have the result ? 

Obviously, firstly we will ask : if i < 32 ? Why? because this 32 can remove 1/2 possibilities for us :  p(i<=32) = p(i> 33)   = 1/2
what if we ask if i<10 ? we remove 10/64 possibilities, it's surly smaller than 1/2. So we "waste " a chance of question.

So the logic is :
i have 64 possibilities, every question, we should reduce the possibilities as much as we can.

64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 : log2(64) = 6 , so 6 question we can get the number.

2  another game : balance the balls : I have 12 balls, one of them is not normal (heavier or lighter). how many steps to find it with a balance ? 

do not hurry to give a solution, we can try to understand the nature of the problem:
what means find the ball ? --> remove all the possibilities
what are all the possibilities ? --> every one can be heavier(+) or lighter(-) : that's 24 possibilities and 24 same possibilities.

what balance can do? --> give 3 results : left heavier or right heavier or equals
so, what we can do :

from book: Information Theory: Inference and Learning Algorithms
So we got : 24 -> 8 -> 3 ->1 : log3(24) = 2.892 ~ 3 steps

3 now let's talk about sort problem : 

what is a sort problem indeed ? --> arrangement(排列)

How many possibilities ? --> first position : N, second : N-1 ...-->N! possibilities

what we do to sort? --> compare : if a>b (like the Y/N question in gess number)
So when we got a>=b or a<b, we reduce the possibilities to N!/2

So we hope that p(a>=b) = p(a<b) = 1/2, so that every time we can reduce 1/2 of the possibilities :  O(N) = O( log2(N!) ) ~ O( Nlog2(N) )

the algorithms who use this principle theory : Heapsort and Quicksort

Heapsort : 

first we need a MaxHeap : every root is bigger(or smaller) than their childs
for using this algo, we need a method to make MaxHeap :
makeMaxHeap()    :
it will make a heap to a MaxHeap:
while(not all root bigger than their chile){
     swap(root, max( left, right ))
}

with this method, we can make sure the heap is maxHeap;

when we have a max heap, we can know the root is the biggest in this heap, so we add root in to the list, then we make the last in the heap to be the root.

and we redo the makeMaxHeap() and redo the exchange with the last....

https://www.youtube.com/watch?v=PqS5T9ZKZno

repeat until not point in the heap,  we can have all sorted in the list.



Complexity ?--> O( NlogN )
Why it is slower than QuickSort ?
We concentrate on the step for put the root in the list and put the last to the root : the last one is surly smaller than his parent node, so this is not 1/2 possibility so we lose some steps.

One optimized solution is not to use the last one as root, but take the bigger one of the root's two childs, than re forme the heap.

Quick Sort:
take a value randomly (ex : the last one) as pivot value, put all the elements that smaller than pivot on the left ,and bigger ones on the right of the pivot. , then do the same thing for the left part and left part.

why it's quick? --> when we choose a pivot randomly, and we want to position a : p( a<= pivot ) = p( a> pivot ) = 1/2, so this step is very worthy.

But it's not such quick  :
we have [a1,a2,a3, ........ pivot]

when we compare a1 and pivot --> p (a1<pivot ) = 1/2
(1/2 -- > we suppose that there are n numbers smaller than pivot, n are bigger than pivot)
after, if a1<pivot when we compare a2 and pivot -- > p( a1<pivot ) = n-1 / 2n
a3 = n-2 / 2n ....

so after the first "beautiful" comparaison, the rest comparisons are not perfect 1/2 possibility. So Quick sort is not so quick as we imagined.