Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Data Structure: Quick Sort


The basic version of quick sort algorithm was invented by C. A. R. Hoare in 1960 and formally introduced quick sort in 1962.  It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations because it is not difficult to implement, it is a good "general purpose" sort and it consumes relatively fewer resources during execution.

 

Good points

  • It is in-place since it uses only a small auxiliary stack.
  • It requires only n log(n) time to sort n items.
  • It has an extremely short inner loop
  • This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Bad Points

  • It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
  • It requires quadratic (i.e., n2) time in the worst-case.
  • It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Quick sort works by partitioning a given array A[p . . r] into two non-empty sub array A[p . . q] and A[q+1 . . r] such that every key in A[p . . q] is less than or equal to every key in A[q+1 . . r]. Then the two subarrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.

QuickSort

  1. If p < r then
  2.     q Partition (A, p, r)
  3.     Recursive call to Quick Sort (A, p, q)
  4.     Recursive call to Quick Sort (A, q + r, r)

Note that to sort entire array, the initial call Quick Sort (A, 1, length[A])

As a first step, Quick Sort chooses as pivot one of the items in the array to be sorted. Then array is then partitioned on either side of the pivot. Elements that are less than or equal to pivot will move toward the left and elements that are greater than or equal to pivot will move toward the right.

 

Partitioning the Array

Partitioning procedure rearranges the subarrays in-place.

PARTITION (A, p, r)
  1. x ← A[p]
  2. i ← p-1
  3. j ← r+1
  4. while TRUE do
  5.     Repeat j ← j-1
  6.     until A[j] ≤ x
  7.     Repeat i ← i+1
  8.     until A[i] ≥ x
  9.     if i < j
  10.         then exchange A[i] ↔ A[j]
  11.         else return j

Partition selects the first key, A[p] as a pivot key about which the array will partitioned:
Keys ≤  A[p] will be moved towards the left .
Keys ≥ A[p] will be moved towards the right.

The running time of the partition procedure is (n) where n = r - p +1 which is the number of keys in the array.
Another argument that running  time of PARTITION on a subarray of size (n) is as follows: Pointer i and pointer j start at each end and move towards each other, conveying somewhere in the middle. The total number of times that i can be incremented and j can be decremented is therefore O(n). Associated with each increment or decrement there are O(1) comparisons and swaps. Hence, the total time is O(n).

 

Array of Same Elements

Since all the elements are equal, the "less than or equal" teat in lines 6 and 8 in the PARTITION (A, p, r) will always be true. this simply means that repeat loop all stop at once. Intuitively, the first repeat loop moves j to the left; the second repeat loop moves i to the right. In this case, when all elements are equal, each repeat loop moves i and j towards the middle one space. They meet in the middle, so q= Floor(p+r/2). Therefore, when all elements in the array A[p . . r] have the same value equal to Floor(p+r/2).

 

Performance of Quick Sort

The running time of quick sort depends on whether partition is balanced or unbalanced, which in turn depends on which elements of an array to be sorted are used for partitioning.
A very good partition splits an array up into two equal sized arrays. A bad partition, on other hand, splits an array up into two arrays of very different sizes. The worst partition puts only one element in one array and all other elements in the other array. If the partitioning is balanced, the Quick sort runs asymptotically as fast as merge sort. On the other hand, if partitioning is unbalanced, the Quick sort runs asymptotically as slow as insertion sort.

Best Case

The best thing that could happen in Quick sort would be that each partitioning stage divides the array exactly in half. In other words, the best to be a median of the keys in A[p . . r] every time procedure 'Partition' is called. The procedure 'Partition' always split the array to be sorted into two equal sized arrays.
If the procedure 'Partition' produces two regions of size n/2. the recurrence relation is then
T(n) = T(n/2) + T(n/2) + (n)
       = 2T(n/2) + (n)
And from case 2 of Master theorem
        T(n) = (n lg n)

 

Worst case Partitioning

The worst-case occurs if given array A[1 . . n] is already sorted. The PARTITION (A, p, r) call always return p so successive calls to partition will split arrays of length n, n-1, n-2, . . . , 2 and running time proportional to n + (n-1) + (n-2) + . . . + 2 = [(n+2)(n-1)]/2 = (n2). The worst-case also occurs if A[1 . . n] starts out in reverse order.


  

Randomized Quick Sort

In the randomized version of Quick sort we impose a distribution on input. This does not improve the worst-case running time independent of the input ordering.
In this version we choose a random key for the pivot. Assume that procedure Random (a, b) returns a random integer in the range [a, b); there are b-a+1 integers in the range and procedure is equally likely to return one of them. The new partition procedure, simply implemented the swap before actually partitioning.

RANDOMIZED_PARTITION (A, p, r)
i ← RANDOM (p, r)
Exchange A[p] ↔ A[i]
return PARTITION (A, p, r)
Now randomized quick sort call the above procedure in place of PARTITION

RANDOMIZED_QUICKSORT (A, p, r)
If p < r then
    q ← RANDOMIZED_PARTITION (A, p, r)
    RANDOMIZED_QUICKSORT (A, p,q)
    RANDOMIZED_QUICKSORT (A, q+1,    
 
r)

Like other randomized algorithms, RANDOMIZED_QUICKSORT has the property that no particular input elicits its worst-case behavior; the behavior of algorithm only depends on the random-number generator. Even intentionally, we cannot produce a bad input for RANDOMIZED_QUICKSORT unless we can predict generator will produce next.

 

Analysis of Quick sort


Worst-case
Let T(n) be the worst-case time for QUICK SORT on input size n. We have a recurrence
T(n) = max1≤q≤n-1 (T(q) + T(n-q)) + (n)             --------- 1
where q runs from 1 to n-1, since the partition produces two regions, each having size at least 1.
Now we guess that T(n) ≤ cn2 for some constant c.
Substituting our guess in equation 1.We get

    T
(n) = max1≤q≤n-1 (cq2 ) + c(n - q2)) + (n)
           = c max (q2 + (n - q)2) +  (n)
Since the second derivative of expression q2 + (n-q)2  with respect to q is positive. Therefore, expression achieves a maximum over the range 1≤ q  ≤ n -1 at one of the endpoints. This gives the bound max (q2 + (n- q)2)) 1 + (n -1)2 = n2 + 2(n -1).
Continuing with our bounding of T(n) we get
    T(n) ≤ c [n2 - 2(n-1)] + (n)
            = cn2 - 2c(n-1) + (n)
Since we can pick the constant so that the 2c(n -1) term dominates the (n) term we have
     T(n)  ≤  cn2
Thus the worst-case running time of quick sort is (n2).

 

Average-case Analysis

If the split induced by RANDOMIZED_PARTITION puts constant fraction of elements on one side of the partition, then the recurrence tree has depth (lgn) and (n) work is performed at (lg n) of these level. This is an intuitive argument why the average-case running time of  RANDOMIZED_QUICKSORT is (n lg n).
Let T(n) denotes the average time required to sort an array of n elements. A call to RANDOMIZED_QUICKSORT with a 1 element array takes a constant time, so we have T(1) =  (1).
After the split RANDOMIZED_QUICKSORT calls itself to sort two subarrays. The average time to sort an arrayA[1 . . q] is T[q] and the average time to sort an array A[q+1 . . n] is T[n-q]. We have
        T(n) = 1/n (T(1) + T(n-1) + n-1∑q=1 T(q) + T(n-q))) + (n)    ----- 1
We know from worst-case analysis
T(1) =  (1) and T(n -1) = O(n2)
T(n) = 1/n ((1) + O(n2)) + 1/n n-1∑q=1 (r(q) + T(n - q)) + (n)
       = 1/n  n-1∑q=1(T(q) + T(n - q)) + (n)                          ------- 2
       = 1/n[2  n-1∑k=1(T(k)] + (n)
       = 2/n n-1∑k=1(T(k) + (n)                                           --------- 3
Solve the above recurrence using substitution method. Assume inductively that T(n) ≤ anlgn + b for some constants a > 0 and b > 0.
If we can pick 'a' and 'b' large enough so that n lg n + b > T(1). Then for n > 1, we have
T(n) ≥ n-1∑k=1 2/n (aklgk + b) + (n)
        = 2a/n n-1∑k=1 klgk - 1/8(n2) +  2b/n (n -1) + (n)     ------- 4
At this point we are claiming that
n-1∑k=1 klgk  ≤  1/2 n2 lgn - 1/8(n2)
Stick this claim in the equation 4 above and we get
T(n)  ≤   2a/n [1/2 n2  lgn - 1/8(n2)] + 2/n b(n -1) + (n)
         ≤  anlgn - an/4 + 2b + (n)                                  ---------- 5
In the above equation, we see that (n) + b and an/4 are polynomials and we certainly can choose 'a' large enough so that an/4 dominates (n)  + b.
We conclude that QUICKSORT's average running time is (n lg(n)).

Conclusion
Quick sort is an in place sorting algorithm whose worst-case running time is (n2) and expected running time is (n lg n) where constants hidden in (n lg n) are small.

 Implementation

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}
Read More

Data Structure:Merge Sort


Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.
To sort A[p .. r]:
1. Divide Step
If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p.. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
2. Conquer Step
Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step
Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

Algorithm: Merge Sort
To sort the entire sequence A[1 .. n], make the initial call  to the procedure MERGE-SORT (A, 1, n).
MERGE-SORT (A, p, r)
1.     IF p < r                                                    // Check for base case
2.         THEN q = FLOOR[(p + r)/2]                 // Divide step
3.                 MERGE (A, p, q)                          // Conquer step.
4.                 MERGE (A, q + 1, r)                     // Conquer step.
5.                 MERGE (A, p, q, r)                       // Conquer step.

Example: Bottom-up view of the above procedure for n = 8.

Merging
What remains is the MERGE procedure. The following is the input and output of the MERGE procedure.
INPUT: Array A and indices p, q, r such that p ≤ q ≤ r and subarray A[p .. q] is sorted and subarray A[q + 1 .. r] is sorted. By restrictions on p, q, r, neither subarray is empty.
OUTPUT: The two subarrays are merged into a single sorted subarray in A[p .. r].
We implement it so that it takes Θ(n) time, where n = r − p + 1, which is the number of elements being merged.

Idea Behind Linear Time Merging
Think of two piles of cards, Each pile is sorted and placed face-up on a table with the smallest cards on top. We will merge these into a single sorted pile, face-down on the table.
A basic step:
  • Choose the smaller of the two top cards.
  • Remove it from its pile, thereby exposing a new top card.
  • Place the chosen card face-down onto the output pile.
  • Repeatedly perform basic steps until one input pile is empty.
  • Once one input pile empties, just take the remaining input pile and place it face-down onto the output pile.
Each basic step should take constant time, since we check just the two top cards. There are at most n basic steps, since each basic step removes one card from the input piles, and we started with n cards in the input piles. Therefore, this procedure should take Θ(n) time.
Now the question is do we actually need to check whether a pile is empty before each basic step?
The answer is no, we do not. Put on the bottom of each input pile a special sentinel card. It contains a special value that we use to simplify the code. We use ∞, since that's guaranteed to lose to any other value. The only way that ∞ cannot lose is when both piles have ∞ exposed as their top cards. But when that happens, all the nonsentinel cards have already been placed into the output pile. We know in advance that there are exactly r − p + 1 nonsentinel cards so stop once we have performed r − p + 1 basic steps. Never a need to check for sentinels, since they will always lose. Rather than even counting basic steps, just fill up the output array from index p up through and including index r .
The pseudocode of the MERGE procedure is as follow:
MERGE (A, p, q, r )
1.      n1 ← q − p + 1
2.      n2 ← r − q
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞
10.    i ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 1

Example [from CLRS-Figure 2.3]: A call of MERGE(A, 9, 12, 16). Read the following figure row by row. That is how we have done in the class.
  • The first part shows the arrays at the start of the "for k ← p to r" loop, where A[p . . q] is copied into L[1 . . n1] and A[q + 1 . . r ] is
    copied into R[1 . . n2].
  • Succeeding parts show the situation at the start of successive iterations.
  • Entries in A with slashes have had their values copied to either L or R and have not had a value copied back in yet. Entries in L and R with slashes have been copied back into A.
  • The last part shows that the subarrays are merged back into A[p . . r], which is now sorted, and that only the sentinels (∞) are exposed in the arrays L and R.]
The operation of lines 10 through 17 in the call MERGE (A, 9, 12, 6).

Running Time
The first two for loops (that is, the loop in line 4 and the loop in line 6) take Θ(n1 + n2) = Θ(n) time. The last for loop (that is, the loop in line 12) makes n iterations, each taking constant time, for Θ(n) time. Therefore, the total running time is Θ(n).

Analyzing Merge Sort
For simplicity, assume that n is a power of 2 so that each divide step yields two subproblems, both of size exactly n/2.
The base case occurs when n = 1.
When n ≥ 2, time for merge sort steps:
  • Divide: Just compute q as the average of p and r, which takes constant time i.e. Θ(1).
  • Conquer: Recursively solve 2 subproblems, each of size n/2, which is 2T(n/2).
  • Combine: MERGE on an n-element subarray takes Θ(n) time.
Summed together they give a function that is linear in n, which is Θ(n). Therefore, the recurrence for merge sort running time is
merge sort recurrence

Solving the Merge Sort Recurrence
By the master theorem in CLRS-Chapter 4 (page 73), we can show that this recurrence has the solution
T(n) = Θ(n lg n).
Reminder: lg n stands for log2 n.
Compared to insertion sort [Θ(n2) worst-case time], merge sort is faster. Trading a factor of n for a factor of lg n is a good deal. On small inputs, insertion sort may be faster. But for large enough inputs, merge sort will always be faster, because its running time grows more slowly than insertion sorts.

Recursion Tree
We can understand how to solve the merge-sort recurrence without the master theorem. There is a drawing of recursion tree on page 35 in CLRS, which shows successive expansions of the recurrence.
The following figure (Figure 2.5b in CLRS) shows that for the original problem, we have a cost of cn, plus the two subproblems, each costing T (n/2).
Construction of recursion tree

The following figure (Figure 2.5c in CLRS) shows that for each of the size-n/2 subproblems, we have a cost of cn/2, plus two subproblems, each costing T (n/4).
Construction of recursion tree

The following figure (Figure: 2.5d in CLRS) tells to continue expanding until the problem sizes get down to 1.
Construction of the recursion tree

In the above recursion tree, each level has cost cn.
  • The top level has cost cn.
  • The next level down has 2 subproblems, each contributing cost cn/2.
  • The next level has 4 subproblems, each contributing cost cn/4.
  • Each time we go down one level, the number of subproblems doubles but the cost per subproblem halves. Therefore, cost per level stays the same.
The height of this recursion tree is lg n and there are lg n + 1 levels.

Mathematical Induction
We use induction on the size of a given subproblem n.
Base case: n = 1
Implies that there is 1 level, and lg 1 + 1 = 0 + 1 = 1.
Inductive Step
Our inductive hypothesis is that a tree for a problem size of 2i has lg 2i + 1 = i +1 levels. Because we assume that the problem size is a power of 2, the next problem size up after 2i is 2i + 1. A tree for a problem size of 2i + 1 has one more level than the size-2i tree implying i + 2 levels. Since lg 2i + 1 = i + 2, we are done with the inductive argument.
Total cost is sum of costs at each level of the tree. Since we have lg n +1 levels, each costing cn, the total cost is
cn lg n + cn.
Ignore low-order term of cn and constant coefÞcient c, and we have,
Θ(n lg n)
which is the desired result.


Implementation
void mergeSort(int numbers[], int temp[], int array_size)
{
        m_sort(numbers, temp, 0, array_size - 1);
}



void m_sort(int numbers[], int temp[], int left, int right)
{
        int mid;

        if (right > left)

        
{

            mid = (right + left) / 2;

            m_sort(numbers, temp, left, mid);

            m_sort(numbers, temp, mid+1, right);


            merge(numbers, temp, left, mid+1, right);

        
}
}



void merge(int numbers[], int temp[], int left, int mid, int right)

        
{

            int i, left_end, num_elements, tmp_pos;


            left_end = mid - 1;

            tmp_pos = left;

            num_elements = right - left + 1;



while ((left <= left_end) && (mid <= right))

        
{

                if (numbers[left] <= numbers[mid])

                
{

                        temp[tmp_pos] = numbers[left];

                        tmp_pos = tmp_pos + 1;

                        left = left +1;

                
}

                else

                
{

                        temp[tmp_pos] = numbers[mid];

                        tmp_pos = tmp_pos + 1;

                        mid = mid + 1;

                
}

        
}



        while (left <= left_end)

                
{

                        temp[tmp_pos] = numbers[left];

                        left = left + 1;

                        tmp_pos = tmp_pos + 1;

                
}

                while (mid <= right)

                
{

                        temp[tmp_pos] = numbers[mid];

                        mid = mid + 1;

                        tmp_pos = tmp_pos + 1;

                
}



                for (i = 0; i <= num_elements; i++)

                
{

                        numbers[right] = temp[right];

                        right = right - 1;

                
}

        
}
Read More

Data Structure: Insertion Sort


If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is called insertion sort. An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time. This is perhaps the simplest example of the incremental insertion technique, where we build up a complicated structure on n items by first building it on n − 1 items and then making the necessary changes to fix things in adding the last item. The given sequences are typically stored in arrays. We also refer the numbers as keys. Along with each key may be additional information, known as satellite data. [Note that "satellite data" does not necessarily come from satellite!]

Algorithm: Insertion Sort
It works the way you might sort a hand of playing cards:
  1. We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
  2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
  3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.
Note that at all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table.

Pseudocode
We use a procedure INSERTION_SORT. It takes as parameters an array A[1.. n] and the length n of the array. The array A is sorted in place: the numbers are rearranged within the array, with at most a constant number outside the array at any time.

INSERTION_SORT (A)
1.     FOR j ← 2 TO length[A]
2.             DO  key ← A[j]   
3.                   {Put A[j] into the sorted sequence A[1 . . j − 1]}  
4.                    i ← j − 1   
5.                    WHILE i > 0 and A[i] > key
6.                                 DO A[i +1] ← A[i]           
7.                                         i ← i − 1    
8.                     A[i + 1] ← key

Example: Following figure (from CLRS) shows the operation of INSERTION-SORT on the array A= (5, 2, 4, 6, 1, 3). Each part shows what happens for a particular iteration with the value of j indicated. j indexes the "current card" being inserted into the hand.
The operation of INSERTION-SORT on the array A = <5, 2, 4, 6, 1, 3>
Read the figure row by row. Elements to the left of A[j] that are greater than A[j] move one position to the right, and A[j] moves into the evacuated position.

Analysis
Since the running time of an algorithm on a particular input is the number of steps executed, we must define "step" independent of machine. We say that a statement that takes ci steps to execute and executed n times contributes cin to the total running time of the algorithm. To compute the running time, T(n), we sum the products of the cost and times column [see CLRS page 26]. That is, the running time of the algorithm is the sum of running times for each statement executed. So, we have
T(n) = c1n + c2 (n − 1) + 0 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n ( tj )+ c6 ∑2 ≤ j ≤ n (tj − 1) + c7 ∑2 ≤ j ≤ n (tj − 1) + c8 (n −1)                               
In the above equation we supposed that tj  be the number of times the while-loop (in line 5) is executed for that value of j. Note that the value of j runs from 2 to (n − 1). We have
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n ( tj )+ c6 ∑2 ≤ j ≤ n (tj  − 1) + c7 ∑2 ≤ j ≤ n (tj  − 1) + c8 (n − 1)  Equation (1)

Best-Case
The best case occurs if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j − 1). In other words, when i = j −1, always find the key A[i] upon the first time the WHILE loop is run.
Therefore, tj = 1 for j = 2, 3, ..., n and the best-case running time can be computed using equation (1) as follows:
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 ∑2 ≤ j ≤ n (1) + c6 ∑2 ≤ j ≤ n (1 − 1) + c7 ∑2 ≤ j ≤ n (1 − 1) + c8 (n − 1)
T(n) = c1n + c2 (n − 1) + c4 (n − 1) + c5 (n − 1) + c8 (n − 1)
T(n) = (c1 + c2 + c4  + c5  + c8 ) n + (c2  + c4  + c5  + c8)
This running time can be expressed as an + b for constants a and b that depend on the statement costs ci. Therefore, T(n) it is a linear function of n.
The punch line here is that the while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.
T(n) = an + b = O(n)
It is a linear function of n.

Worst-Case
The worst-case occurs if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. So, we must compare each element A[j] with each element in the entire sorted subarray A[1 ..j − 1] and so tj = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j − 1) tests. Therefore, tj = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:
T(n) = c1n + c2 (n − 1) + c4  (n − 1) + c5 ∑2 ≤ j ≤ n ( j ) + c6 ∑2 ≤ j ≤ n(j − 1) + c7 ∑2 ≤ j ≤ n(j − 1) + c8 (n − 1)
And using the summations in CLRS on page 27, we have
T(n) = c1n + c2 (n − 1) + c4  (n − 1) + c5 ∑2 ≤ j ≤ n [n(n +1)/2 + 1] + c6 ∑2 ≤ j ≤ n [n(n − 1)/2] + c7 ∑2 ≤ j ≤ n [n(n − 1)/2] + c8 (n −1)
T(n) = (c5/2 + c6/2 + c7/2) n2 + (c1 + c2 + c4 + c5/2 − c6/2 − c7/2 + c8) n − (c2 + c4 + c5 + c8)
This running time can be expressed as (an2 + bn + c) for constants a, b, and c that again depend on the statement costs ci. Therefore, T(n) is a quadratic function of n.
Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order
T(n) = an2 + bn + c = O(n2)
It is a quadratic function of n.

The graph shows the n2 complexity of the insertion sort.

Worst-case and average-case Analysis
We usually concentrate on finding the worst-case running time: the longest running time for any input size n. The reasons for this choice are as follows:
  • The worst-case running time gives a guaranteed upper bound on the running time for any input. That is, upper bound gives us a guarantee that the algorithm will never take any longer.
  • For some algorithms, the worst case occurs often. For example, when searching, the worst case often occurs when the item being searched for is not present, and searches for absent items may be frequent.
  • Why not analyze the average case? Because it's often about as bad as the worst case.
Example: Suppose that we randomly choose n numbers as the input to insertion sort.
On average, the key in A[j] is less than half the elements in A[1 .. j − 1] and it is greater than the other half. It implies that on average, the while loop has to look halfway through the sorted subarray A[1 .. j − 1] to decide where to drop key. This means that tj  = j/2.
Although the average-case running time is approximately half of the worst-case running time, it is still a quadratic function of n.

Stability
Since multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, Insertion sort is stable.

Extra Memory
This algorithm does not require extra memory.
  • For Insertion sort we say the worst-case running time is θ(n2), and the best-case running time is θ(n).
  • Insertion sort use no extra memory it sort in place.
  • The time of  Insertion sort is depends on the original order of a input. It takes a time in Ω(n2) in the worst-case, despite the fact that a time in order of n is sufficient to solve large instances in which the items are already sorted.

Implementation
void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i = 1; i < array_size; i++)
  {
          index = numbers[i];
          j = i;
          while ((j > 0) && (numbers[j − 1] > index))
          {
                   numbers[j] = numbers[j − 1];
                   j = j − 1;
          }
          numbers[j] = index;
  }
}
Read More