In this article, we will study recurrence relation for different sorting algorithms.
Recurrence Relation for Bubble Sort
Pseudo Code For Bubble Sort
for( i=0 ; i<N-1 ; ++i ){
for( j=0 ; j<N-i-1 ; ++j){
if( array[i] > array[j] )
swap( array[i] , array[j] );
}
}
For each iteration of the outer loop, we place the largest element at the end of the array. In simple words, the ith iteration of the outer loop move the largest element from the first elements to (N-i-1)th position.
Recurrence Relation
is the number of steps required to place the largest element at the end of the array and
signifies that time required to sort the rest of
elements.
Recurrence Relation for Selection Sort
In each iteration of selection sort, we search for the smallest element and place it at the beginning of the array. After that, we increment the beginning position of the array and again search for the smallest element among the rest of the elements and repeat.
Searching the smallest element in the array takes comparisons.
Recurrence Relation
is the time required to search the smallest element in the array and place it at the beginning of the array.
is the time required to sort the rest of the
elements.
Recurrence Relation for Insertion Sort
Insertion Sort Pseudo Code
i = 0
while i < N
temp = array[i];
j = i
// inserting array[i] in the sorted sequence
while j > 0 && array[j-1] > array[j]
array[j] = array[j-1];
j = j - 1;
end while
array[j] = temp;
end while
The ith iteration of the outer loop implies that we have sorted array till i – 1 index. We need to insert the ith element in the sorted elements in the range [0, i-1]. Since the size of the sorted portion is i, the insertion requires i – 1 comparison.
Recurrence Relation
is the time required to sort
elements.
denotes the time required to insert the Nth element in the sorted sequence of
elements.
Recurrence Relation for Merge Sort
Pseudo Code for Insertion Sort
function merge_sort(array, start, end)
if(start<end)
mid = (start + end)/2
merge_sort(array,start,mid-1)
merge_sort(array,mid+1,start)
merge(array,start,end)
end if
end function
On each call of merge_sort, we split the array into two equal parts. Then we recursively sort the two parts. After sorting the two halves, we merge them such that the array remains sorted.
Recurrence Relation
is the time required to sort the two equal parts of the array.
is the time required to merge the two sorted parts into a single sorted array.
Recurrence Relation for Quick Sort
Pseudo Code for Quick Sort
function quick_sort(array, start, end)
if(start<end)
pivot = partition(array,start,end)
quick_sort(array,start,mid-1)
quick_sort(array,mid+1,start)
end if
end function
Quicksort first chooses a random element X as the pivot and partition the array in 2 parts such that the elements smaller than X are on the left side and elements greater than X are on the right side. After partition, X is in the correct position. Then we recursively sort the elements on the left side X and elements on the right side of X.
The partition requires comparisons.
Recurrence Relation
Best Case
In the best-case scenario, the pivot will split the array into 2 equal parts. Therefore, the recurrence relation will be
comparisons to find the pivot position and
to sort the two partitions of the array.
Worst Case
In the worst case, the pivot will split the array of size N such that one part will contain no element, and the other party will contain elements. This happens if all the elements are either smaller or greater than the pivot element.
Recurrence Relation for Heap Sort
Suppose we have a min-heap. The top of the heap always points to the smallest element. We copy the top element of the heap to another array. After that, we delete/pop the top of the heap. The deletion requires comparisons. We repeat until the heap is empty.
Recurrence Relation
is the number of comparisons required to delete/pop the top element from a heap and copy it somewhere else.
is the time required to sort the rest of the elements using heapsort.