1. preface

/****
*    This article will try to explain something about:
*        --Bubble sort.
*        --Quick sort.
*        --Merge sort.
*        --Heap sort.
*    To read this, some prerequisites is necessary:
*        --a survive skill in C programming language.
*        --a basic skill in CPP.
*        --basic knowledge about Time complexity and Space complexity.
*        --a generous mind for my fault because this article is free.
*
*    Actually, their basic operating principle are easy to understand, but , unfortunately, the precise explication is big problem, at least for me. Here is the contents.
*        --Analysis about Bubble sort.
*        --Analysis about Quick sort.
*        --Analysis about Merge sort.
*        --Analysis about Heap sort.
*    their source code can be find in fellowing articles. As we all know, for a programmer, the source code is also a good choice.
*/

2. Bubble sort

/****
*    Bubble Sort
*    This is a really simple algorithm. I learn it when I began to learn C. It just compare two value successively and swap them. The core source code is as fellowing:
*/

    2.1 core code

bool BubbleSort::sort(void){    int i,j;    for( i=0; i<=n; i++)        for( j=0; j< n -i; j++)        {            if( this->array[ j]>this->array[ j+1])            {                this->swap( j, j + 1);	//swap two values            }        }}

    2.2 Time complexity and Space complexity

/**
*    For sort algorithm, it‘s basic operation is swap two values.So we can compute it‘s sentence frequency f(n):
*        f(n) = n*n = n^2
*        (at worst situation)
*    and it‘s time complexity is :
*        T(n) = O( f(n)) = O(n^2)
*
*
*    obviously, It‘s space complexity is :
*        S(n) = O( g(n)) = O( C) = O(1)
*    because it use only constant space whatever n change.
*/

/*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/

3. Quick sort

/****
*    Quick Sort
*    This is a famous algorithm. It was developed in 1960 , but never outdated even for now. I was face a problem about sort a million of numbers. Need to say that is a

*    nightmare if use bubble sort. Then I learn Quick Sort, it provide a exciting performance. I will explain this below. The principle of quicksort is "divided and process".

*    In detail,
*        --step1: Pick an element from the array as pivot.
*        --step2: Part all elements into two areas: left area and right area.put element that‘s value less than pivot‘s value into left area,and put other elements into right area.
*        --step3: Recursively do the step above to those sub-array.
*
*
*. First at all, examine it‘s core source code:
*/

    3.1 Core Code

static void quick_sort( int array[], INDEX left, INDEX right){    if( right-left>=2)    {//core code        int p;        p = pivot( array, left, right);		//step1 + step2        quick_sort( array, left, p-1);		//step3        quick_sort( array, p+1,  right);    }    else if( right -left ==1)    {//auxiliary        if( array[left] > array[right])        {            swap( array + left, array + right);        }    }}static int pivot( int array[], INDEX left, INDEX right){    //get povit, one of methods    INDEX	mInd = (left + right)/2;    //divide array into two parts    int	i = 0;    int	LLen = 0, RLen = 0;    for( i=left; i<=right; i++ )    {        if( i==mInd)            continue;        if( array[i]< array[mInd] )        {            Arr_back[left + LLen] = array[i];            LLen++;        }        else        {            Arr_back[right - RLen] = array[i];            RLen++;        }    }    Arr_back[left + LLen] =  array[mInd];    memcpy( array+left, Arr_back + left, (right-left + 1)*sizeof(int));	//use a auxiliary space    return left + LLen;}

    3.2 Time complexity

/**
*    For quicksort, the basic operation is similar to swap above. So we could compute a valid sentence frequency. If there are n elements, in average situation the depth of

*    recurrence is log2(n).Just as below:
*
*    step1: [1.........................................................n]    // n
*    step2: [1......................m1] [m1.......................n]    // n/2 + n/2
*    step3: [1.....m2] [m2.....m1]  [m1....m3]  [m3......n]    // n/4 + n/4 + n/4 + n/4
*    .......
*    stepX: [1,2][3,4]................................................
*
*    and funny is that: for step N, if we want to part those arrays into sub-array, we need the number of basic operation is :
*        N*(n/N)
*    that‘s means:
*        f(n) = n*log2(n)
*    and
*        T(n) = O( f(n)) = O( n*log2(n) )
*
*/

    3.3 Space complexity

/**
*    At least two points are deserve to consider.
*        Point.1 : Normally, we need more auxiliary space when n increase.
*        Point.2 : the recursion of function may be need more space.
*
*    In my situation, the auxiliary space of Point.1 is n. For Point.2, Assume that the cost is A for ecah function call, the totally number of call is
*        2^0 + 2^1 + 2^2 + .....2^log2(n)
*
*    then, the cost of point.2 is
*
*              A*[1 + 2^1 + 2^2 + ....2^log2(n) ]
*            =A*[1 + 2^1 + 2^2 + ....+ n]
*            =A*[2*n-1] < A*2*n
*
*    combine two parts:
*            S(n) = O( B*n) = O(n)
*/
/*
*    References
*        wikipedia-Quicksort <http://en.wikipedia.org/wiki/Quicksort>
*/

4. Merge sort

/****
*    Merge Sort
*    The common view is that: compare with famous Quicksort and Heapsort, it is slightly worse in sort a array.  but it provide a excellent performance in sort a link list,

*    which is difficult to Quicksort and Heapsort. on the other side, Mergesort is a stable sort, unlike standard in-place quicksort and heapsort. It‘s core principle is "divide

*    and conquer".
*
*    conceptually, Mergesort work as fellow:
*        step1: divide the array into n sublists.That means every sublist is only contain of 1 element.
*        step2: repeatedly merge all sublists to create new sorted sublist untill there is only 1 sublist remaining.
*
*    just like this:
*    step1:    [0] [1] [2] [3] [4] [5] [6] [7]
*    step2:    [0...1] [2...3]  [4...5] [6...7]
*    step3:    [0............3]  [4..............7]
*    step4:  [0..................................7]
*
*    If you need more information, there will be a good place.
*        http://en.wikipedia.org/wiki/Merge_sort
* 
*    then , examine the core source code:
*/

    4.1 core code

bool MergeSort::sort(void){    ......    int width = 1;    while( width < (this->right - this->left + 1) )    {        this->subsort( width);	//sort sublists        width *= 2;    }    .....}bool MergeSort::subsort( int width){    .....    INDEX	cur = this->left;    while( cur + width <= this->right)    {        //sort two sublists into a new sorted list.        this->sort2Arr( cur, width, cur + width, MIN( width, this->right-cur-width+1));        cur += 2*width;    }    memcpy( this->array,  this->array_back, (this->right - this->left + 1)*sizeof(int));    .....}

    4.2 Time complexity

/**
*    Time complexity
*
*    Now, let me see a interesting thing before check it‘s Time frequency. Image this, there are two  arrays ,both of them are progressive increase. they are contain of n and

*    m elements respectively.
*
*    [1.............n] [1..........m]
*
*    How many times is necessary to merge them into a new sorted array?
* 
*       --  at least:  MIN( n,m);
*            at most:  m+n;
*
*            For example:
*                [ 1, 2, 3] [4,5,6,7]
*            and
*                [1,2,3,7] [4,5,6]
*
*
*    Based on the conclusions above, we could know that : at worst situation, if we want to sort n elements by the way of Mergesort,  the times of compare operation is n.
*
*    So, Time frequency is n*log2(n)
*    and
*        T(n) = O( f(n)) = O( n*log2(n) )
* 
*/

    4.3 Space complexity

/**
*    Space complexity
*        In my example, a additional array was used to auxiliary operation.
*        obviously, the space complexity is :
*                S(n) = O(n);
*
*        but that is at worst situation. It could be optimized.
*
*/

5. Heap sort

/****
* Heap Sort
*  This is another famous sort algorithm. Need to say: it‘s very cool. Although sometimes it is slower in practice on most machine than  well-implemented quicksort, it‘s

*have the advantage of a more favorable worst-case O( n*log(n)) runtime. unfortunately, it is not a stable sort.
*/

/*
* Before explain heapsort, some questions are necessary to know:
* 1). How can we store a binary tree into a array ?
*
*  --if we number all nodes of a tree , based on 1, you will find a rule. To a node n, it must have the fellowing relationship:
*   parent    : floor(n/2)
*   left chil   : 2*n
*   right chil : 2*n + 1
*
*   This feature gives us a chance to save a tree into a array.
*
* 2). What is max heapify ?
*  --For a binary tree, if all of parent nodes greater than or equal to those corresponding child nodes, the root node must be the largest node in this tree. In other words,
*   we can get  the largest one between some nodes by arrange those number into a max binary tree. By the way, if binary tree can do that, then heap can, too.
*/

/*
* The Heapsort algorithm can be divided into two parts.
*  step 1: build a max binary tree.
*
*  step 2: remove the largest node( the root of the tree) ,and then update the tree repeatedly untill all of nodes has been get out.
*
*/

    5.1 core code

bool HeapSort::sort(void){	/**	As we all know, some of nodes haven't child node.*	For skip those nodes, we need to find the last parent node.*	*	but How can we do that?**	--the answer is the last child node.*/	INDEX	nInd = 0;	nInd = this->fun.GetParentInd( this->right );	/**	Adjust nodes from bottom to top.Function MaxHeapify() *	will arrange a node and its's sublayer nodes to *	a max binary tree. */	while( nInd>=0)	{		// @(this->right) is the number of nodes.		this->MaxHeapify( nInd, this->right);		nInd--;	}/**	moving the largest one between all of nodes into a array,*	and tidy the remaining. Repeat this process untill *	we get all of nodes.*/	nInd = this->right;	while( nInd>0 )	{		this->Swap( 0, nInd);				nInd --;		this->MaxHeapify( 0, nInd);	}	return true;}bool HeapSort::MaxHeapify( INDEX nInd, INDEX right){	INDEX	max = this->GetBigNodeInd( nInd, right);	while( max!=nInd)	{		this->Swap( max, nInd);		nInd = max;		max = this->GetBigNodeInd( nInd, right);	}		return true;}

/*
* About @MaxHeapify(), there are many problems need to solve. This article is worth to reading:
*  http://shmilyaw-hotmail-com.iteye.com/blog/1775868
* 
*/

    5.2 Time complexity

/**
*    sorry, I have no idea.
*/

    5.3 Space complexity

/**
* space complexity 
*
* It is simple to compute the space complexity.
*  S(n) = O(1);
* because it use a constant space.
*/

/*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/

/**
* References:
*
*  heap sort分析和总结 <http://shmilyaw-hotmail-com.iteye.com/blog/1775868>
*  heapsort   <http://en.wikipedia.org/wiki/Heapsort>
*
*/