This chapter is intended to cover various sorting algorithms. We perform various kinds of sorts in our everyday lives, such as sorting a pack of cards, ordering a pile of books, comparing multiple bills, and so on. These sorts are primarily based on intuition. Sometimes, sorting can be an essential part of other algorithms which are used for route optimization. In the current chapter, two different types of sorts will be covered. The first is comparison-based sorting, wherein all the key values of the input vector are directly compared with each other prior to ordering. The second type is non-comparison-based sorting, wherein computations are performed on each key value, and then the ordering is performed based on the computed values. Overall, all algorithms primarily follow the principle of divide and conquer. Some of the ways of dividing covered in the chapter are length-based splits (used in merge sort), pivot-based splits (used in quick sort), and digit-based splits (used in radix sort). The initial part of the chapter deals with comparison-based sorts with three simple and intuitive sorting algorithms, which are relatively slow and have an asymptotic complexity of θ(n2) in average and worst-case scenarios. Then we'll cover algorithms with better asymptotic performance in worst-case scenarios, such as θ(nlog n). Finally, non-comparison-based sorts are covered, which show better asymptotic performance in worst-case scenarios, such as θ(n) under special conditions. The current chapter will cover the following topics:
- Sorting terminology and notation
- Three Θ(n2) sorting algorithms
- Insertion sort
- Bubble sort
- Selection sort
- The cost of exchange sorting
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Bin sort and radix sort
- An empirical comparison of sorting algorithms
- Lower bounds for sorting
In this chapter, the input for any algorithm is a vector of elements (key values) unless stated otherwise. These elements can be of any type: numeric, character, logical, or complex.
Consider an input vector V of elements i1,i2,...,in. These elements are said to be sorted provided their corresponding values satisfy a particular order. In other words, the elements of vector V are said to be sorted in non-decreasing order provided their values satisfy the condition i1<i2<,...,<in.
All the algorithms presented in this chapter can handle the special case of sorting, that is, duplicate elements in a given input vector; however, only some of them perform it optimally. An algorithm is said to be performing optimally provided it retains the original position of duplicate elements without redundantly ordering them, thereby reducing computation time.
The simplest way to compare performances of two algorithms is by assessing their computational system runtime. Table 5.2 shows the system runtime of sorting algorithms for comparison purposes. The runtime depends on the following factors:
- Parameters of the input data
- Number of elements in the input vector
- Memory size of the elements and their respective keys
- Allowable range of elements (key values)
- Original order of the input vector
- Parameters of the algorithm (approach)
- Number of comparisons between keys
- Number of swapping or element interchange operations
- List of vectors that need to be sorted and their frequency of recurrence
- Asymptotic analysis—functional forms of runtime