REVIEW ON SORTING ALGORITHMS
A comparative study on two sorting algorithms
By
Pooja Adhikari
A Term Paper
Submitted to the Faculty of Dr. Gene Boggess
Mississippi State University
In the Department of Computer Science & Engineering
Mississippi State, Mississippi
04 20072

ABSTRACT Any number of practical applications in computing requires things to be in order. The performance of any computation depends upon the performance of sorting algorithms.
Like all complicated problems, there are many solutions that can achieve the same results. One sort algorithm can do sorting of data faster than another. A lot of sorting algorithms has been developed to enhance the performance in terms of computational complexity, memory and other factors. This paper choose two of the sorting algorithms among them selection sort and shell sort and compares the various performance factor among them.
1. INTRODUCTION
Sorting is the rearrangement of things in a list into their correct lexicographic order. A number of sorting algorithms have been developed like include heap sort , merge sort, quick sort, selection sort all of which are comparison based sort .There is another class of sorting algorithms which are non comparison based sort. This paper gives the brief introduction about sorting algorithms [2] where it discuss about the class of sorting algorithms and their running times. It mainly analyses the performance between two sorting algorithms .Selection sort [3] and Shell sort [5].
Selection sort is the simple sorting method with a very simple sorting algorithm [3].
However the running time of this algorithm is not that optimal as compared to performance of best sorting algorithm .The analysis of the running time [4] concludes this thing. Shell sort is another comparison based sorting algorithm which is better than selection sort [5] and works in a gap sequence [7]. The running time and the performance analysis
[6] shows that although its performance is better than the selection sort, there are other various factor that needs to be keep in mind.
The advantages of selection sort contain within it a lot of disadvantage and so are shell sort [8].However there are equally important and is best for a particular purpose.
2. SORTING Sorting is one of the basic operations that are performed by many computers since handling the data in a certain order is more efficient than handling the randomized data.3
There are different kinds of sorting algorithms .Two common sorting algorithms among them are: Selection Sort and Shell Sort
3. SELECTION SORT
Selection sort is one of the simplest algorithms. It is actual an improvement in performance of bubble sort. This algorithm is called selection sort because it works by selecting a minimum element in each step of the sort. This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case runtime of Θ (n
2
), assuming that comparisons can be done in constant time. The
Selection sort spends most of its time trying to find the minimum element in the
"unsorted" part of the array. The brief algorithm for selection sort is given below. SELECTION_SORT (A) Cost of Each Step
1. for i ← 0 to n-1 do O(n)
2. min ← i; O(1)
3. for j ← i + 1 to n do O(n
2
)
4 If A[j] < A[min] then O(1)
5. min←j O(1)
6. swap(A[i] ,A[min]) O(1)
Total run time Cost== Θ (n
2
) asymptotically
It works as follows:
1. Find the smallest element using a linear scan.
2. Swap the element with the element in first position.
3. Find the second smallest element in the remaining array.
4. Then swap to the second position.
5. Continue the steps until a sorted list is obtained.4
4. PERFORMANCE ANALYSIS OF SELECTION SORT For each value of element until n it needs to compare and check whether there is any value smaller than it and needs (n-1) comparisons. Thus it can be easily seen that run time complexity of selection sort is Θ (n
2
) due to the line no.3.But since it just requires the Θ (n) swaps means linear order writes to the memory which is optimal to any sorting algorithm .
Table 1. further clarifies the above statement. The running time is obtained by calculating how many times the line 4 of the above algorithm got executed on the specified array size. Number of Array Elements Running Time
8 28
16 120
32 496
64 2016
128 8128
256 32640 Table 1. Running time of selection sort From the above table it is clear that this naive approach is very good for small number of elements. But it requires the comparison of every element to every other element which will lead to a great deal of work for large data sets.
The worst case occurs if the array is already sorted in descending order. Nonetheless, the time require by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test "if A[j]