Sorting Algorithms
Introduction
Sorting refers to arranging items in a desired manner. This operation finds plenty of applications in real life like searching algorithms, processing data, and for producing human-friendly output. The sorting problem has caught the attention of many researchers. As a result, we find many algorithms to optimize this problem in the required fashion. In this report, we will consider two important sorting algorithms to give readers brief idea about how data management and ordering is done. These sorting algorithms are Insertion sort and Shell sort.
Insertion Sort
It is one of the simplest sorting algorithms based on comparisons between items and sorting one entry at a time . It is quite efficient for small data sets, but provides high computational cost for large arrays.
The process of Insertion sort is straightforward in its implementation. It works by inputting a single number acting as a key. The algorithm starts finding its correct position in the array by comparing it with other items in the list. The input numbers are provided either randomly or by using s set pattern i.e. from left to right or vice versa. Let’s consider that we start inserting numbers from the left side of the array while arranging it in ascending order. Keep the very first number at its place. The second element will be compared with the first. They are swapped if second element is smaller than the first one. Next, the third element from the left will be compared with two numbers preceding it. It gets its right place and we keep on moving towards right till the whole array is sorted out.
The algorithm for Insertion sort is presented as follows that helps in its MATLAB implementation.
First of all, you need to input array elements and find its length.
Choose a pivot element starting from the left. The first element is already considered to be sorted. The second element from the left becomes the pivot in first iteration.
The pivot element is compared with its preceding elements and it is swapped if it is found to be less than them. Comparisons are finished as soon as we find a number smaller than the pivot element.
Move the pivot position one step towards right and repeat step 3 until you reach at the end of the list.
The implementation of Insertion sort in MATLAB is provided in the form of flowchart as follows:
Let’s consider the procedure of Insertion sort with a specific array: (2,1,3,0,22,-1,7,10,8,6,5,-2). The pivot position comes at ‘1’first of all. It is swapped with ‘2’. Then, pivot moves to the next element ‘3’. It is compared with the preceding elements ‘1’ and ‘2’ and it stays at its place. Next, ‘0’ is inserted at the extreme left position and so on till the whole array is sorted.
The algorithm of Insertion sort works quite efficiently for partially sorted lists .It is mostly employed as a sub-routine of more complex sorting algorithms. It requires comparisons equal to one less than the length of the array. If the elements are in the reverse order, then the worst case complexity will come out to be of the order of the square of the number of elements. On2. For the best case of already sorted array, the cost will be linear n . It works more intelligently as compared to Bubble sort. Owing to the fact that this algorithm is extremely easy in its implementation, it is employed in some other sorting methods like Shell sort, Quick sort, and merger sort for providing greater efficiency. It only requires O1 auxiliary space for its computation . If the array size is quite large, Insertion sort is not used alone as the computational cost will be high.
Shell Sort
Shell sort is basically one of the most popular variant of Insertion sort . This algorithm was proposed in 1959. The idea of this sorting takes credit from the high efficiency of Insertion sort for arrays that are almost sorted . It uses the idea of Insertion sort by dividing the original array into sub-arrays containing elements far apart from each other. The last step is simple Insertion sort when the list is almost sorted out .
The algorithm of Shell sort is easy to code, but it is difficult to analyze theoretically. It performance depends upon choosing the gap while forming sub-arrays. It was one of the first algorithms to have complexity less than quadratic.
The algorithm of Shell sort is provided below that aids in its MATLAB implementation.
Input an array and find its total length.
Choose a suitable wide gap size to take advantage of Insertion sort in sorting sub-arrays.
Let’s assume that gap size is initially half of the size of the array. It means that we will sort three elements: (first, middle, and end).
Perform insertion sort on the sub-array with the chosen gap size.
Reduce gap to half and perform step 4 again.
Keep reducing gap and applying Insertion sort till you end up with no gap between elements. But, by then the array will almost be completely sorted out.
In order to visually understand the aforementioned algorithm, we have prepared the following flowchart.
The flowchart clearly describes the algorithm of Shell sort in a simplified manner. Let’s discuss Shell sort with the help of an example to strengthen its base. Consider the same array that we chose for Insertion sort: (2,1,3,0,22,-1,7,10,8,6,5,-2). The length of the array is 12. First we choose the gap size to be half of the length of the array to make Insertion sort simple. The elements in the sub-array to be sorted will be 2, 7, -2. These elements are sorted (-2, 2, 7). Next, we reduce the gap to 12/4=3. Then the sub-array will be larger, but some elements will already be sorted. In this manner, we keep on reducing the gap and increasing the sub-array size till we end up at the original array. At the end, the Shell sort will be simply Insertion sort .
Plenty of study has been carried out regarding optimization of Shell sort algorithm. V. Pratt proposed slightly different approach for dealing with this gap issue . He improved the original worst case complexity of On2 to (nlog2n). This computational cost is slightly worse as compared to those of optimal comparison sorts (nlogn). However, still Shell sort is optimal in utilizing Insertion sort with the proper gap size.
The effectiveness of Shell sort is obvious in the cases in which a small element resides at the end of the list. To pull it back using Bubble sort, we have to spend a number of comparisons and swapping before the smaller number reaches its desired place. When we use Shell sort for solving the same problem, it uses elements far apart from each other for sorting. In this manner, the smaller element is placed at the right position in initial iterations.
Let’s take another look into visualizing Shell sort. We can think of the list to be arranged into a table form. We pick columns and apply Insertion sort on them. We will pick smaller number of longer columns in next stages. At the end, we will be left with only one column.
The advantage of Shell sort is its good computational cost and relatively easy coding method. It is suitable for using with relatively large arrays. However, if the array size is too large, then Shell sort is not recommended to use.
Conclusion
This report presented some popular sorting algorithms for arrays that are used in modern day computer sciences. First of all, we took a look at Insertion sort that is one of the simplest sorting algorithms. It uses the approach of inserting the elements at the pivot position at their right place. The pivot is selected using desired criteria depending upon application. The complexity of this algorithm is quadratic. Next, we considered the generalization of Insertion sort in the form of Shell sort. This algorithm reduces the quadratic complexity of Insertion sort to a lower logarithmic value. This sorting approach uses the inherent advantage of Insertion sort of arranging elements quickly that are partially sorted. The major contributor the success of this algorithm is intelligent choice of gap size.
References
Canaan, C. a. G. M. a. D. M., 2011. Popular sorting algorithms. World Applied Programming, 1(1), pp. 42--50.
Kumar Karunanithi, A., 2014. A Survey, Discussion and Comparison of Sorting Algorithms. s.l.:Master's Thesis, Department of Computing Science Ume'a University, Sweden.
Pratt, V., 1979. Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Garland.
Shell, D. L., 1959. A high-speed sorting procedure. Communications of the ACM, 2(7), pp. 30--32.
Appendix A (MATLAB Code for Insertion Sort)
display('Unsorted Array');
array=[2,1,3,0,22,-1,7,10,8,6,5,-2]
l=length(array);
for i=2:l
pivot=array(i);
check=0;
j=i-1;
while(check==0&&j>0)
if(pivot<array(j))
intermediate=pivot;
array(j+1)=array(j);
array(j)=intermediate;
else
check=1;
end
j=j-1;
end
array
end
display('Sorted Array')
array
Appendix B (MATLAB Code for Shell Sort)
display('Unsorted Array');
array=[2,1,3,0,22,-1,7,10,8,6,5,-2]
l=length(array)
i=floor(l/2)
while(i>0)
for j=i:l-1
k=j-i+1
while(k>0)
if(array(k+i)>=array(k))
break;
else
intermediate=array(k);
array(k)=array(k+i);
array(k+i)=intermediate;
end
k=k-i;
end
end
i=floor(i/2);
end
display('Sorted Array')
array
