1. INTRODUCTION:

In computer science and mathematics, a sorting algorithm is an algorithm in that the most-used orders are numerical order and lexicographical order. Proficient sorting is vital for optimizing the utilization of other algorithms that require sorted lists to work correctly. More properly, the output must gratify two circumstances: (1) The output is in non decreasing order and (2) The output is a variation, or reordering, of the input. Since the early of computing, the sorting problem has fascinated a great deal of research, perhaps due to the complexity of solving it proficiently although its simple, familiar statement. Sorting algorithms are rife in early computer science classes, where the plenty of algorithms for the problem provides a gentle opening to a variety of core algorithm concepts, such as big O notation, divide and conquer algorithms, data structures, randomized algorithms, and case analysis.

2. CLASSIFICATION OF ALGORITHMS:

1) Swap Based, in which pair of element is being exchanged, Ex: Shell Sort.

2) Merge Based, Having sequence swapped with each other afterwards any element, Ex: Insertion Sort.

3) Tree Based, wherever data is stored in form of binary tree, Ex: Heap Sort.

4) Other Categories, Having an additional key for perform swap, Radix and Bucket Sort.

3. METHODS OF SORTING:

1) Selection Sorting: Selection Sort, Heap Sort, Smooth Sort, Strand Sort, Insertion Sort.

2) Insertion Sorting: Shell Sort, Tree Sort, Liberary Sort.

3) Exchange Sorting: Bubble Sort, Cocktail Sort, Gnome Sort, Comb Sort, Quick Sort.

4) Merge Sorting: Merge Sort.

5) Non Comparison Sorts: Radix Sort, Counting Sort, Bucket Sort

6) Other Sorting techniques: Topological Sorting, Sorting Network.

4. COMPARISONS ON THE BASIS OF COMPLEXITY AND OTHER FACTORS:

Table 1: Comparisons on the Basis of Complexity and Other Factors

Sorting Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	O(n)	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)	O(n²)
Insertion sort	O(n)	O(n²)	O(n²)
Merge Sort	O(nlog n)	O(n log n)	O(n log n)
Heap Sort	O(nlog n)	O(n log n)	O(n log n)
Quick Sort	O(nlog n)	O(n log n)	O(n²)

Bubble Sort:

Bubble Sort is the simplest sorting algorithm that works by frequently exchange the neighboring elements if they are in wrong order. An alternate way of putting the largest element at the highest index in the array uses an algorithm called bubble sort.

Function BubbleSort(array, array_size)

var i, j, temp;

For i:=(array_size-1)down to 0 step-1

For j := 1 to i do

If array(j-1) > array(j) then

temp := array[j-1];

array[j-1] := array[j];

array[j] := temp;

End If

End For

End Function

Example:

First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ),

Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) –>( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) –>( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ),

Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) –>( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed.

The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Selection sort:

The selection sort algorithm sorts an array by frequently finding the least element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two sub arrays in a given array.

1) The sub array which is already sorted.

2) Remaining sub array which is unsorted.

Every iteration of selection sort, the least element (considering ascending order) from the unsorted sub array is picked and moved to the sorted sub array.

Function SelectionSort(array, size)

var min, temp, i, j

For i := 0 to size-2 do

min := i

For j := i+1 to size-1 do

If array(j) < array(min)

min := j

End If

End For j

temp := array(i)

array(i) := array(min)

array(min) := temp

End For i

End Function

Figure 1: Example for Selection Sort

Insertion Sort:

Insertion sort is one way to sort an array of numbers. Data is divided into sorted and unsorted portions. One by one, the unsorted values are inserted into their appropriate positions in the sorted sub array. Following are some of the important characteristics of Insertion Sort.

· It has one of the simplest implementation

· It is efficient for smaller data sets, but very inefficient for larger lists.

· Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

· It is better than Selection Sort and Bubble Sort algorithms.

· Its space complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.

· It is Stable, as it does not change the relative order of elements with equal keys

For I=2 to N

A [I] =item, J=I-1

WHILE j>0 and item<A[J]

A[J+1]=A[J]

J=J-1

A [J+1]=item

end while

end for

Insertion Sort working procedure:

Figure 2: Insertion Sort Working Procedure

Figure 3: Screen sort for insertion sort

Heap Sort:

It is similar to selection sort where we first find the maximum element and place the maximum element at the end. Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data structure (Max-Heap or Min-Heap). Once heap is built, the first element of the Heap is either largest or smallest (depending upon Max-Heap or Min-Heap).

Heap Sort Algorithm for sorting in increasing order:

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

3. Repeat above steps until size of heap is greater than 1.

heapSort(DATA, N)

heapify(DATA, N)

Set end = N - 1

while end > 0 do

a) swap(DATA[end], DATA[0])

b) Set end = end – 1

c) siftDown(DATA, 0, end)

[End of while in Step 3]

Exit

FUNCTION heapify(DATA,N)

start := (N - 2) / 2

while start ≥ 0 do

a) siftDown(DATA, start, N-1)

b) start := start–1[End of While in step 2]

Merge Sort:

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

1. Divide Step:

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two sub arrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two sub arrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

MERG-SORT (A, p, r)

IF p < r // Check for base case

THEN q = FLOOR[(p + r)/2] // Divide step

MERGE (A, p, q) // Conquer step.

MERGE (A, q + 1, r) // Conquer step.

MERGE (A, p, q, r) // Conquer step.

MERGE (A, p, q, r )

n1 ← q − p + 1

n2 ← r − q

Create arrays L[1 .. n1+1] & R[1 ..n2+1]

For i ← 1 TO n1

do L[i] ← A[p + i − 1]

For j ← 1 TO n2

do R[j] ← A[q + j ]

L[n1 + 1] ← ∞

R[n2 + 1] ← ∞

i ← 1

j ← 1

For k ← p TO r

IF L[i ] ≤ R[ j ] THEN

A[k] ← L[I ]

i ← i + 1

ELSE

A[k] ← R[j]

j← j + 1

END IF

END FOR K

END FOR J

END FOR I

Figure 4: Merge Sort

Quick Sort:

Quick sort is not stable search, but it is very fast and requires very less additional space. Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

Different Sorting Algorithms Elapsed Time Analysis:

Table 2: Algorithms Elapsed Time Analysis

No of Elements	Elapsed Time (ms)
No of Elements	Selection Sort	Insertion Sort	Bubble Sort
1000	364	317	315
1500	565	482	528
2000	763	678	684
2500	865	842	795
5000	993	946	965
10000	1007	993	995
20000	1243	1141	1081
30000	1364	1320	1256

There are many different versions of quick Sort that pick pivot in different ways.

· Always pick first element as pivot.

· Always pick last element as pivot (implemented below)

· Pick a random element as pivot.

· Pick median as pivot.

Quick sort is also called partition-exchange sort

Table 3: Algorithms Elapsed Time Analysis

No of Elements	Elapsed Time (ms)
No of Elements	Quick Sort	Merge Sort	Heap Sort
1000	236	341	324
1500	438	498	562
2000	632	691	725
2500	781	844	796
5000	824	858	928
10000	918	988	984
20000	1040	1121	1093
30000	1108	1278	1317

Figure 5: Algorithms Elapsed Time Analysis

5. CONCLUSION:

The above analysis said that, Quick Sort is the fastest algorithm but it needs enough memory. Quick sort is more often used as external sorting. On the above comparison and the resultant analysis, it is clear to use Bubble Sort for small data set whereas Quick Sort for large data set.

6. REFERENCES

[1]. Jehad Alnihoud, Rami Mansi, "An Enhancement of Major Sorting Algorithms", The International Arab Journal of Information Technology, Vol. 7, No. 1, January 2010,PP:55-62.

[2]. Ibrahim M. Al Turani, Khalid S. Al-Kharabsheh, Abdallah M. AlTurani, “Grouping Comparison Sort”, Australian Journal of Basic and Applied Sciences, 7(7): 470-475, 2013.

[3]. Ankit R. Chadha, Rishikesh Misal , Tanaya Mokashi , Aman Chadha , “ARC Sort: Enhanced and Time Efficient Sorting Algorithm”, International Journal of Applied Information Systems (IJAIS), Volume 7– No. 2, April 2014, PP:31-36.

[4]. Hadi Sutopo, "Selection sorting algorithm visualization using flash", The International Journal of Multimedia and Its Applications (IJMA) Vol.3, No.1, February 2011, PP:22-35.

[5]. Bilal Jan, Bartolomeo Montrucchio, Carlo Ragusa, Fiaz Gul Khan and Omar Khan, "Fast parallel sorting algorithms on GPUS", International Journal of Distributed and Parallel Systems (IJDPS) Vol.3, No.6, November 2012,PP:107-118.

[6]. Toqeer Ehsan, M. Usman Ali, Meer Qaisar Javed, "An Efficient Sorting Algorithm by Computing Randomized Sorted Sub-Sequences Based on Dynamic Programming", IJCSNS International Journal of Computer Science and Network Security, VOL.13 No.9, September 2013,PP:51-57.

[7]. Shweta Popli, Arshi Talwar, Sneha Gupta, "A comparison between three sorting algorithms based upon the time complexity", International Journal of Advanced Technology in Engineering and Science, Volume No.02, Special Issue No. 01, September 2014,PP:643-647.

[8]. R. Angrish, D. Garg, "Efficient String Sorting Algorithms: Cache-aware and Cache-Oblivious", International Journal of Soft Computing and Engineering (IJSCE), Volume-1, Issue-2, May 2011,PP:12-16.

[9]. Prof. (Dr.) V. N. Maurya, Dr. R. K. Bathla, Diwinder Kaur Arora, Er. Avadhesh Kumar Maurya,Ram Asrey Gautam, "An Alternate Efficient Sorting Algorithm Applicable for Classification of Versatile Data", International Journal of Mathematical Modeling and Applied Computing, Vol. 1, No. 1, April 2013, PP: 01 – 10.

[10]. Sarvjeet Singh, Surmeet Kaur, "Freeze Sorting Algorithm Based on Even-Odd Elements", International organization of Scientific Research, Vol. 04, Issue 03 (March. 2014), V6, PP 18-23.

[11]. Mounir Hamdi, Chunming Qiao, Yi Pan and J. Tong, "Communication-Efficient Sorting Algorithms on Reconfigurable Array of Processors With Slotted Optical Buses", Journal of Parallel and Distributed Computing 57, 166-187 (1999).

[12]. Avinash Shukla, Anil Kishore Saxena, "Review of Radix Sort and Proposed Modified Radix Sort for Heterogeneous Data Set in Distributed Computing Environment", International Journal of Engineering Research and Applications (IJERA),Vol. 2, Issue 5, September- October 2012, pp.555-560.

[13]. Ahmed M. Aliyu, Dr. P. B. Zirra, "A Comparative Analysis of Sorting Algorithms on Integer and Character Arrays",The International Journal Of Engineering And Science (IJES),Volume:2,Issue:7,PP: 25-30,2013.

[14]. Debadrita Roy, Arnab Kundu, "A Comparative Analysis of Three Different Types of Searching Algorithms in Data Structure", International Journal of Advanced Research in Computer and Communication Engineering, Vol. 3, Issue 5, May 2014,PP:6626-6630.

[15]. Jagbeer Singh, Bichitrananda Patra, Satyendra Prasad Singh, "An Algorithm to Reduce the Time Complexity of Earliest Deadline First Scheduling Algorithm in Real-Time System", International Journal of Advanced Computer Science and Applications, Vol. 2, No.2, February 2011,PP:31-37.

[16]. Ashutosh Bharadwaj, Shailendra Mishra, "Comparison of Sorting Algorithms based on Input Sequences", International Journal of Computer Applications, Volume 78 – No.14, September 2013, PP: 7-10.

[17]. Ms. Nidhi Chhajed, Mr. Imran Uddin, Mr. Simarjeet Singh Bhatia, "A Comparison Based Analysis of Four Different Types of Sorting Algorithms in Data Structures with Their Performances", International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 2, February 2013,PP:373-381.

[18]. Pankaj Sareen, "Comparison of Sorting Algorithms (On the Basis of Average Case)",International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 3, March 2013,PP:522-532.

[19]. Mohsin Khan, Samina Shaheen, Furqan Aziz Qureshi, "Comparative Analysis of five Sorting Algorithms on the basis of Best Case, Average Case, and Worst Case", International Journal of Information Technology and Electrical Engineering, Volume 3, Issue 1, February, 2014,PP:1-10.

[20]. Miraj Gul, Noorul Amin, M. Suliman, "An Analytical Comparison of Different Sorting Algorithms in Data Structure", International Journal of Advanced Research in Computer Science and Software Engineering, Volume 5, Issue 5, May 2015,PP:1289-1298.

Received on 29.12.2015 Accepted on 08.06.2016

Int. J. Tech. 2016; 6(1): 23-30

DOI: 10.5958/2231-3915.2016.00006.7