Sorting

Written by Kousik : 

“Sorting”, this word must come when you are reading C programming language as well as algorithm. This is important part of C programming and very interested problem. Many algorithms for sorting are there. In this section we discuss about several sorting algorithms and their time and space complexity.

Definition:

Input: A sequence of n numbers from linearly ordered set or totally ordered set.

Output: A permutation of the given input sequence such that a[i] <=a[i+1] , where I =1,2,3…,n

Sorting algorithms:

There are many algorithms for sorting. Every algorithm took some time for performing. Different algorithms for same problem would take different complexity.

Problem: Sorting

Name of algorithms	Time complexity	Space Complexity
Insertion sort	O( )	O(n)
Bubble sort	O( )	O(n)
Quick sort	O(nlogn) (In Expected case)	O(n)
Heap sort	O(nlogn)	O(n)
Radix sort or bucket sort	O(n)	O(n)

Now we will analysis about the algorithms shown in above table:

Quick Sort:

This is a way of solving a problem related with sorting. This is a divide-conquer method for sorting. It works by following rule.

1)      Partition the array into two parts.

2)      Sort the two sub array.

3)      Combine the solutions to get the solution for main problem.

Mainly the performance of this method depends upon the position where the partition is to be done. Partition can be done by three following ways.

1)      At first or last position.(Worst case)

2)      At middle position.(Best case)

3)      Randomly choose an element for partition(Randomized quick sort)

We will call the partitioning element by name ‘PIVOT’.

After selecting pivot element we scan the whole array. If we find an element greater than or equal to the pivot element then we keep it at right side of pivot element and otherwise keep it in left side.

By doing this we can claim that the pivot element gets it right position into the array. Then we recursively call the function to right and left side. So, at the end we will get the sorted array.

First we select the middle element as pivot element.

Now it is the time for writing the algorithm.

Method: We use a function named QUICKSORT(S) which works recursively.

Input: Sequence S of n elements a_1, a₂ ...a_n

Output: The elements of S in sorted order.
Continued...