# Sorting in Design and Analysis of Algorithm Study Notes with Example

## S**orting**

In Computer Science, sorting operation is used to put the elements of list in a certain order, *i.e., *either in non-decreasing or decreasing order.

*Sorting can be of two types*

**In-place sorting****Stable Sorting**

**In-place Sorting**

The in-place sorting algorithm does not use extra storage to sort the elements of a list. An algorithm is called in-place as long as it overwrites its input with its output. Those algorithms, which are not in-place, are out of place algorithms.

**Stable Sorting**

Stable sorting algorithm maintain the relative order of records with equal values during sorting and after sorting operation or we can say that a stable sorting algorithm is called stable, if it keeps elements with equal keys in the same relative order as they were in the input.

**Divide and Conquer Approach**

The divide and conquer approach is based on the recursion or it works by recursively breaking down a problem into two or more sub problems, until these becomes simple enough to be solved directly. The solutions of the sub problems are then combined to give a solution to the original problem. ,

**Methods of Sorting**

*There are different sorting techniques as given below *

**Bubble Sorting**

Bubble sorting is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them, if they are in random or unorganized order. This sorting technique go through multiple passes over the array and each pas^{s} moves the largest (or smallest) element to the end of the array.

**pseudo Code for Bubble Sorting**

** void Bubble Sort (int a[ ], int n)**

**{**

**int i , temp,j;**

**for (i=1; i <=n; i++)**

**{**

**for(j=1; j<=i; j++)**

**{**

**if (a[j] > a [j +1])**

**{**

**temp= a [j],**

**a [j]= a [j +1];**

**a [j +1] = temp;**

**}**

**}**

**}**

**}**

The internal loop is used to compare adjacent elements and swap elements, if they are not in order. After the internal loop has finished the execution, the largest element in the array will be moved at the top. The external loop is used to control the number of passes.

**Flow Chart for Bubble Sorting**

**Analysis of Bubble Sort**

Generally, the number of comparisons between elements in bubble ** **short can be stated as follows

*(n – 1) + (n – *2) +…+ 2 + 1 = *n (n – *1)/2 = 0 (n^{2})

In any case (worst case, best case or average case) to sort the list in b_{e} ascending order, the number of comparisons between elements would b same. But the time complexity is different.

*The time complexity of bubble sort in all three cases is given *below

**Best case**0*(n)***Average case**0 (n^{2}) •**Worst case**0 (n^{2})

**Insertion Sorting**

The insertion sort only passes through the array once. Therefore, it is very fast and efficient sorting algorithm with small arrays.

** **** Key Points**

- This algorithm works the way you might sort a hand of playing cards
- We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
- 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].
- To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

**Pseudo Code of Insertion Sort**

**int insertionsort (int a[], int n)**

**{**

** int i , j, key;**

**for (j =2; j<= n; j -H-)**

**{**

**key = a [j];**

**i =j —1;**

**while (i > && a [i] > key)**

**{**

**a [1 +1] = a [i] ;**

**i=i – 1;**

**}**

**a [i +1] = key;**

**}**

**}**

**Flow Chart for **** ****Insertion**** Sorting **

**Flow Chart for**

**Sorting**

**Analysis of Insertion Sort**

The running time depends on the input. An already sorted sequence is easier to sort.

The time complexity of insertion * sort in all these cases is given below .*

**Worst case** Input is in reverse sorted order

** n**

*. T(n) = E 0(j) =*0 (n^{2})

** j=2**

**Average case** All permutations equally likely

** T(n) = I 0 (j /2) = 0 (n^{2}) j = 2**

**Best case **If array is already sorted

*T(n) = 0(n)*

**Merge Sort**

Merge sort is a comparison based sorting algorithm. Merge sort is a *stable short,* which means that the implementation preserves the input order of equ*al *elements in the sorted output array.

Merge sort is a divide conquer *algorit*hm The Performance is independent of the initial order of the array items**.**

**Pseudo Code of Merge Sort**

**void mergeSort (int a [ ], int first, int last)**

**{**

** if (first < last)**

** {**

** Int mid= (first+ last)/2; **

** mergeSort (a, first, mid);**

** mergeSort (a, mid + 1, last);**

**//Divide the array into pieces**

**merge (a, first, mid, last);**

**//Small pieces are merged**

**}**

**}**

**void merge (int a [],**

**int first, int mid, int last)**

**{**

**int c[100]; // temporary array**

**int i , j, k, m;**

**i = first ;**

** j= mid;**

**k=mid+1; m= first;**

**while (first < = last)**

**{**

**while (i <=j && k <= last)**

**{**

** if (a [1] < a [lc])**

**{**

**c[m]=a [1];**

**i ++;**

**m++;**

**}**

**else**

**{**

**c[m]= a [k];**

**m++;**

** k ++;**

**}**

**while(1<=j)**

**{**

**c [m] = a [i];**

**i++;**

**m ++ ;**

**}**

**while (k <= last)**

**{**

** c [m] = a [k];**

** m++;**

** K++;**

**}**

**for (1=0; i < = last; i++)**

**{**

** a[i] = c[i];**

**}**

**}**

**} **

**Key Points**

*There are three main steps in merge sort algorithm*

**Divide**An array into halves, until only one piece left.**Sort**Each half portion.**Merge**The sorted halves into one sorted array.

** ****Analysis of Merge Sort**

The merge sort algorithm always divides the array into two balanced lists. So, the recurrence relation for merge sort is

*The time complexity of merge sort in all three case *(best, average and worst) *is given below*

**Best case***0(n*log_{2}*n)***Average case***0 (n*log_{2}*n)***Worst case***0 (n*log_{e}*n)*

**Quick Sort**

It is in-place sorting, since it uses only a small auxiliary stack. It is also known as partition exchange sort. Quick sort first divides a large list int smaller subsists. Quick sort can then recursively sort the subsists.

**key Points**

- It is a divide and conquer algorithm.
- In quick sort algorithm, pivot element is selected and arrange all the items in the lower part are less than the pivot and all those in the upper part greater than it.

*The pseudo code of quick sort*

**int quicksort (int a [ J, int low, int high)**

**{**

** int pivot;**

** if (low < high)**

**{**

**pivot =partition (a, low, high); quicksort (a, low, pivot —1); quicksort (a, pivot +1,high);**

**}**

**}**

**int partition (int a [ J, int low, int high)**

**{**

**int temp;**

**int i = low;**

**int p= low;**

** int q = last; while (i < j)**

**{**

**while (a [p] < = a [1] && i< last)**

**{**

**I++;**

**}**

**while (a[q] > a [i])**

**{**

** j – -;**

**}**

**if (p<q)**

**{**

**temp= a [p];**

** a[p]= a[q];**

** a [q]= temp;**

**}**

**temp = a [i];**

** a [i]= a [q];**

**a [q] = temp;**

** return q;**

**}**

**Analysis of Quick Sort**

*The time complexity calculation of quick sort in all three cases is given **below*

**Worst case: ***0(n ^{2}) *This happens when the pivot is the smallest

(or the largest) element. Then, one of the partitions is empty and we repeat recursively the procedure of

*n –*1 elements.

The recurrence relation for worst case

*T(n) = T(n – *1) + *cn, n > *1

*T(n)=T(n – *2) + c(n – 1) + *cn*

*T(n)=T(n – *3) + *c(n *2)+c(n-1)+cn

*Repeat** upto K – 1 times, we get
*

*T(n) = *T(1) + c(2 + 3 +…+ *n)*

**= 1 + c (n (n + 1)_{ 1}**

**2**

*T(n) = O(n ^{2})*

** ****Best case: **0(n log_{2}* n) *The pivot is in the middle and the subarrays divide into balanced partition every time. So, the recurrence relation for this situation

*T(n)= *2T (n/2) + cn

Solve this, using master method

**a =2, b =2, f(n) = cn**

*cn cn *

*h(n)= *_{nlogb a }= _{nlog2 2 }c (log_{2} n)^{°}

*U(n) = *0 (log_{2}* n)*

**Then, **

** T(n) = n^{b}gb ^{a} U(n)**

*= n • *0(log_{2}* n)*

*T(n) = 0 (n *loge *n)*

**Average case: **0(n log_{2}* n) *Quick sort’s average running time is much closer to the best case than to the worst case.

**Size of Left Partition Size of Right Partition**

1 n – 1

2 *n — *2

3 *n — *3

**n-3 3**

**n-2 2**

n-1 1

**The **average value of *T(i) s — *times, the sum of T(0) through *T(n -1)*

1 . .

*-ET(i),J *=Oton-1

*T(n) = – ^{2 }(IT(j)) + cn*

**n**

(Here we multiply with 2 because there are two partition`

On multiply by *n, *we get

*n T(n) = *2(ET(j)) + *cn * n*

To remove the summation, we rewrite the equation for *n -1.*

*(n – 1) T(n – *1) = 2 (ET(/)) + c(n – 1)^{2}, *j = 0 to n – *1and subtract

*nT(n) – (n – *1) *T(n – *1) = 2T *(n *1) + 2cn – c

Rearrange the terms, drop the insignificant c *nT(n) = (n + 1) T(n – 1) + *2cn

On dividing by *n (n + *1), we get

__T(n) T (n -1)__* 2c*

*n +1 **n n + *1

__T(n -1) _T(n__* –*__ 2)__ + 2c *n **(n – 1) **n*

__T(n __*– *2) = *T(n – *

__3)__+

__2c__

*n – 1*

*(n –*2)

*n -1*

__T(2)___{ =}*T(1) + *2c

3 2 3

Add the equations and cross equal terms

^{T(n) 7}*:*^{(1)}+2c 4-^{1}),j=3ton+1 *n +1 2 *

*T(n) = (n + *1) (1/2 + 2c E(1/j))

The sum EOM, *j = *3 to *(n – *1) is about log_{2}* n*

*T(n) = (n + *1) (log_{2}* n)*

*T(n) = 0 (n *log_{e}* n)*

**Advantages of Quick Sort Method**

- One of the fastest algorithms on average.
- It does not need additional memory, so this is called in-place sorting.

**Heap Sort**

Heap sort is simple to implement and is a comparison based sorting. It is in-place sorting but not a stable sort.

**Note **Heap sorting uses a heap data structure.

**Heap Data Structure :**Heap *A *is a nearly complete binary tree.

Height of node = Height of edges on a longest simple path from the node down to a leaf

Height of heap = Height of root

= (log *n)*

*e.g., *We represent heaps in level order, going from left to right. The array corresponding to the heap at the right side is [25, 13, 17, 5, 8, 3].

The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed.

**Parent (**

**return fl oor (1/2)**

**Left (i )**

**re turn 2i**

**Right (i )**

**return 2i +1**

**Heap Property**

*The heap properties L used on the comparison of value of node and its parent are as given below*

Max heap In a heap, or every node i, other than the root, the value of a node is less than or equal (atmost) to the value of its parent.

*A[ p*arent (i)] ≥*A *[i]

Min heap In a heap, or every node i, other than the root, the value of a node is greater than or equal to the value of its parent.

*A *[parent (i)]≤A[i]

**Maintaining the ****Heap** **Property**

Max heapify is imp orta t for manipulating Max heap. It is used to maintain the max heap property

*The following con ‘Nulls will be considered for maintaining the heap **properly are given (Ds*

- Before max hea,)ify, may be smaller than its children.
- Assume left and right subtree of i are max heaps.
*Afte*r max heapify, subtree rooted at i is a max heap.

**Pseudo Code for Max Heapify**

**MaxHeapify (int a [ ],I, n)**

**{**

**int largest, temp;**

**int 1 =2*i;**

**int r = 2*i +1;**

**if (1._n &&a [1]>a[i])**

**{**

**largest =1;**

**}**

**else**

**largest = i;**

**if (r&& a [r] > a [largest])**

**{**

**largest = r;**

**}**

**if(largest!=i)**

**{**

**temp= a [largest];**

**a [largest] = a [i];**

**a [i] = temp;**

**}**

**MaxHeapify(a,,largest,n)**

**}**

*Basically, three basic operations performed on heap are given as*

- Heapify, which runs in
*0*(log_{2}*n)* - Build heap, which runs in linear time 0(1).
- Heap sort, which runs in
*0(n*log_{2}*n)*

We have already discussed the first operation of heap sort. Next we will discuss how to build a heap.

**Building a Heap**

*The following procedure given an unordered array, will produce a max heap **Buil*d

**MaxHeap (int a [ ], int n)**

**int i;**

**for (i = (n/2); i >1; 1—}**

**{**

**Maxheapify (a,.i,n)**

**}**

**}**

**Heap Sort Algorithm**

The heap sort algorithm combines the best of both merge and insertion sort. Like merge sort, the worst case time of heap sort is 0(n log_{2 }* ^{n}) *and like insertion sort, heap sort is in-place sort.

**Pseudo code for heap sort procedure**

** Heapsort (int a ], int n)**

**{**

**int i, temp;**

**BuildMaxHeap (a, n);**

**for (i =n; i >=2; ——)**

**{**

**temp= a[1];**

**a[1] =a [i];**

**a [i] = temp;**

**heapsize [a] = heapsize [a] —1;**

**}**

**Heapify (a, 1);**

**}**

**Analysis of Heap Sort**

The total time for heap sort is 0 *(n *log *n) *in all three cases *(i.e., *best case, average case and worst case)

# Sorting in Design and Analysis of Algorithm Study Notes with Example

Follow Us on Social Platforms to get Updated : **twiter, ****facebook, Google Plus**

Learn Sorting in Handbook Series: **Click here **