ABSTRACT

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.

1.

INTRODUCTION

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.

1.1

Classification of Sorting Algorithms

Internal Sorting:

If

data are sorted directly in main memory, which is called internal sorting.

External Sorting:

If data are sorted in auxiliary memory like hard disk,

floppy disk, pen drive, CD, etc. It termed as external sorting.

System Complexity:

In terms of system complexity it shows the basic

performance of algorithms like worst case, average case, and best case.

Computational

Complexity:

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

Memory usage is the important terms

to store and retrieve the data with the help of algorithms.

Stability:

Stable sorting algorithms maintain the relative order of

records with equal keys.

2.

WORKING PROCEDURE OF ALGORITHMS

Bubble Sort

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

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,

(i)

The sub array which is already sorted.

(ii)

Remaining sub array which is unsorted.

In

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

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,

5, 2

Fig. 3: Insertion Sort

Tab. 3: Execution time

for Insertion Sort

Merge 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

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.

Divide

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

partitioning elements.

Conquer

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.

Combine

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

3.

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.

4.

CONCLUSION

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.

REFERENCES