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 <> */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. * * * 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: * * */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分析和总结 <> * heapsort <> * */