Data structure is a
particular way of organizing and storing a data in a computer. So that it can
be accessed and modify the data in an efficient way. In data structure sorting
is the fundamental and the most common used operation that helps to arranging list
of elements in a particular order. A sorting algorithm consists of comparison,
swap, and assignment operation. There are many different types of sorting
algorithms are used to sort a data. From that here we discuss five different
types of sorting algorithms and gives their performance analysis with respect
to time complexity, which are Bubble sort, Selection sort, Insertion Sort,
Merge sort and Quick sort. Here the main goal is to study how all
the five algorithms works and compare them on the basis of various parameters
to reach a conclusion.
A sorting algorithm is
helps to arrange the elements in a certain order. Till now many algorithm has
been discovered to sorting an elements. Very first work of sorting is comparing
elements with one another then swaps or copies those elements if necessary. It
continues executing over and over until the whole array or list is sorted. This
type of algorithms known as Comparison based sorting. Algorithms are classified
in four different ways that are, Internal Sorting, External Sorting, System
Complexity, Computational Complexity.
Classification of Sorting Algorithms
data are sorted directly in main memory, which is called internal sorting.
If data are sorted in auxiliary memory like hard disk,
floppy disk, pen drive, CD, etc. It termed as external sorting.
In terms of system complexity it shows the basic
performance of algorithms like worst case, average case, and best case.
It focusing a number of swapping that occurs in the
sorting also each algorithm performs various numbers of swaps in order to sort.
Memory usage is the important terms
to store and retrieve the data with the help of algorithms.
Stable sorting algorithms maintain the relative order of
records with equal keys.
WORKING PROCEDURE OF ALGORITHMS
Bubble sort is a comparison based
sort. Also it is a simplest sorting method among the entire comparison based
sort. Here in this sorting the comparison is done among adjacent elements. If
the top data is greater than the data below it, then they are swapped. This
process of comparison and swapping is continuously done for each pair of
adjacent elements till the end of the data set is reached. Once it’s complete
again the process is start comparing first two elements, and repeating until no
swaps occur in the data set. Also it is a slowest sorting method while
comparing other methods of sorting.
Let’s try to understand
the mechanism of Bubble Sorting
Fig. 1: Bubble Sort
Tab. 1: Execution time
for Bubble Sort
Selection sort, in this way of
sorting sort an n number of elements in the array repeatedly to find the
minimum number of element from the unsorted part and putting it at the
beginning. It maintain two sub arrays that are followed,
The sub array which is already sorted.
Remaining sub array which is unsorted.
every iteration of this selection sort, the minimum element from the unsorted
sub array is picked and move to the new sorted sub array.
At ith iteration,
elements from position 0 to i – 1 will be sorted
Fig. 2: Selection Sort
Tab. 2: Execution time
for Selection Sort
Insertion sort is a simple
algorithm. It’s also belongs to the family of comparison sorting. This is the
one of the efficient way for sorting arrays with small size. In this way of
sorting it takes elements form the list one by one and inserting them at their
correct position in ordered to create a new sorted list. Insertion sort is a
great example for an incremental algorithm. In this way of sorting algorithm we
can also scan each and every element form 0 to n. With the help of comparison
it placed each and every element in the right position. Also for sorting time
n-1 passes or steps are required to complete this type of sorting.
Tale Array = 7, 4,
Fig. 3: Insertion Sort
Tab. 3: Execution time
for Insertion Sort
Merge Sort is same like a quick
sort. It’s also breaking down a list into several sub-lists until each sub-list
consists of a single element and merging that sub-list in a manner that results
into a sorted list. Once completing dividing all the elements then we need to
compare two sub-lists for merging. The first element of both lists is taken
into consideration. While sorting in ascending order, the element that is of a
lesser value becomes a new element of the sorted list. This process is repeated
until both the smaller sub-lists are empty and the new combined sub-lit
comprises all the elements of both the sub-lists.
Fig. 1: Merge Sort
Tab. 4: Execution time
for Merge Sort
Quick sort is developed by Sir Charles Antony Richard
Hoare in 1962. In this quick sort is belongs to the family of exchange sorting
techniques. There are two different methods that help to done this quick sort.
That is follows, Divide and Conquer.
The list is divided by
choosing a partitioned element (pivot element). Here in the divided list one
list contain all the elements that are less than or equal to the partitioning
elements. And other list it contain all the elements that greater than the
Once the work of
dividing the list is done then it’s start recursively partitioned in the same
way till the resulting lists become trivially small to sort by comparison.
Finally sorted list is
combined to produce the sorted list which contains the entire input elements.
Fig. 1: Quick Sort
Tab. 5: Execution time
for Quick Sort
COMPARATIVE STUDY AND DISCUSSION
All thus five sorting
algorithms (Bubble sort, Selection sort, Insertion sort, Merge sort, Quick
sort) were implemented in C language on
GCC compiler on Linux Operating System implemented in C++ programming languages
and tested for the random number of inputs that shown in the table. Here to
calculate the running time of each sorting algorithm the function used is
clock(), this function helps to find out the exact execution time of each
sorting algorithm. From that for the large input Quick sort is the fastest and
other algorithms are slowest.
In this paper, efforts
are made to find the different between each algorithms by going through all the
experimental results and their analysis it is concluded that the Quick sort is
very efficient to comparing with other sorting algorithms. Finally Quick sort
is faster than Bubble sort, Selection Sort, Merge Sort, Insertion Sort when it
comes to sort largest data sets.