Ijrar research Journal

S
ORTING 
A
LGORITHMS
 
In this paper we have discussed five sorting algorithms with their complexity and
stability. 
1.
Bubble sort 
2.
Selection Sort 
3.
Insertion Sort 
4.
Merge Sort
5.
Quick Sort 
A.
 
Bubble Sort 
The sorted array as input or almost all elements are in the proper place, bubble sort has O(n) as the best case performance and 
O(n*n) as the worst-case performance. Bubble sort has to perform a large number comparison when there are more elements in 
the list and it increases as the number of items increases that need to be sorted. Although bubble sort is quite easy to implement 
and it’s inefficient while comparing to all other sorting algorithms. It is the simplest sorting algorithm that works by frequently 
swaps the neighboring elements if they are in the wrong order.
Bubble sort algorithm [5] used in the experiments below was described by C++ language as shown in fig 1: 

---

© 2020 IJRAR September 2020, Volume 7, Issue 3 www.ijrar.org (
E-ISSN 2348-1269, P- ISSN 2349-5138
) 
IJRAR19L2026 
International Journal of Research and Analytical Reviews (IJRAR) 
www.ijrar.org
 
115 
Fig. 1 Bubble Sort Code
The above code shown in the Fig 1 takes O(n*n) even in the best case. This code can be optimized by introducing an extra 
variable swapped.
Example: First Pass:
(55 11 44 22 88) –> (11 55 44 22 88),
The first two elements compared by algorithm,
until swaps 55 > 11.
(11 55 44 22 88) –> (11 44 55 22 88),
Swaps until 55 > 44
(11 44 55 22 88) –> (11 44 22 55 88),
Swaps until 55 > 22
(11 44 22 55 88) –> (11 44 22 55 88),
Second Pass:
(11 44 22 55 88) –> (11 44 22 55 88), 
(11 44 22 55 88) –> (11 22 44 55 88),
Swaps until 44 > 22
(11 22 44 55 88) –> (11 22 44 55 88)
Now, the array is sorted but the algorithm wants one whole pass without any swap to verify.
Third Pass:
(11 22 44 55 88) –> (11 22 44 55 88)
(11 22 44 55 88) –> (11 22 44 55 88)
(11 22 44 55 88) –> (11 22 44 55 88)
(11 22 44 55 88) –> (11 22 44 55 88)