In the previous chapter, we discussed several linear data structures, such as linked list, stack, queue, and dequeue. In this chapter, we are going to arrange data elements in a list using some sorting algorithm techniques. The following are the popular sorting algorithms that we are going to discuss in this chapter:
To follow along with this chapter, as well as the source code, you are going to require the following:
Bubble sort is a simple sorting algorithm, but it has a slow process time. It will divide an input list into two parts—a sublist of items already sorted on the right side and a sublist of items remaining to be sorted in the rest of the list. If we are going to sort a list of elements in ascending order, the algorithm will move the greatest value to the right position followed by the second greatest value and so on, similar to air bubbles when they rise to the top. Suppose we have an array of unsorted elements and are going to sort them using the bubble sort algorithm. The following are the steps required to perform the sorting process:
array[0] with array[1], array[1] with array[2], and so on.array[0] <= array[1], array[1] <= array[2], and so on.Similar to bubble sort, selection sort also divides an input list into two parts—a sublist of items already sorted in the left side and a sublist of items remaining to be sorted in the rest of the list. If we are going to sort the input list in ascending order, the lowest items will be in the leftmost position in the input list. These are the steps to perform a selection sort on a given input list:
minIndex. If it's the first sorting iteration, the index should be 0.1throughn - 1) and compare the current value element in the iteration with the first index of the unsorted sublist. If the value of the current index is lower than the value of the first index, set the current index to minIndex.sublist and...Insertion sort is a sorting algorithm that is similar to arranging a hand of poker cards. This sorting algorithm will also divide the list into a sorted and unsorted sublist in the sorting process. For clarity, we pick an item as a reference, then go through the sorted sublist and find the correct position based on performing a comparison. This process is repeated until all the items are sorted, which means that we have to iterate through all of the array's elements.
Let's use our previous array {43, 21, 26, 38, 17, 30} and then perform an insertion sort algorithm on it. First, we set array[0] as the sorted sublist, so we pick array[1] as the reference. Now, we compare the reference item, which is 21, with the sorted sublist. See the following diagram:
Since 21 is lower than 43, 43 will be shifted to array[1] and since no more items are in the sorted sublist, 21 is put into array[0]. Now, array[0] and array[1] are in the sorted sublist, as we can see in the following diagram...
Merge sort is an efficient sorting algorithm that divides the input array into two parts of a sublist. It sorts each sublist and then merges them. To sort each sublist, the algorithm divides the sublist in two again. If this sublist of the sublist can be divided into two halves, then it will be. The idea of the merge sort is that it will merge all the sorted sublists into the fully sorted list. Suppose we have an array containing these elements, {7, 1, 5, 9, 3, 6, 8, 2}, as shown in the following diagram:
We can divide the array into two sublists, which are [7, 1, 5, 9] and [3, 6, 8, 2]. Then, the first sublist can be divided as well to become [7, 1] and [5, 9]. We can sort these sublists and they will be [1, 7] and [5, 9], and then we can merge this sublist so that it becomes [1, 5, 7, 9], as shown in the following diagram:
By now, we have one sorted sublist. We need to sort another sublist, [3, 6, 8, 2]. We can divide this sublist to become [3, 6] and [8, 2], and then sort them...
Quick sort is almost the same as the other sorting algorithms we have discussed so far as it divides the input array into two sublists, which are the left sublist and the right sublist. In quick sort, the process of dividing the array into two sublists is called partitioning. The partition process will pick an item to become a pivot and it will then use the pivot to divide the input into two sublists. If we are going to sort an array in ascending order, all items that are lower than the pivot will be moved to the left sublist, and the rest will be in the right sublist. After running the partition process, we will ensure that the pivot is in the correct position in the array. Although we can choose the item that will be the pivot, we will always choose the first item of the array as the pivot in this discussion.
Suppose we have an array {25, 21, 12, 40, 37, 43, 14, 28}. We are going to sort the array by using the quick sort algorithm. Please see the following diagram:
First, we choose...
Counting sort is a sorting algorithm that arranges items based on a key. Suppose we have an array containing unsorted items with a range between 0 to 9; we can sort it by counting the number of items based on the range as the key. Let's say we have an array of these items—{9, 6, 5, 6, 1, 7, 2, 4, 3, 5, 7, 7, 9, 6}. In a simple explanation, we just need to count the frequency of the occurrence of each item. We then iterate through the range from 0 to 9 to output the items in a sorted order. Initially, we will have an array containing the following items:
Now, we count the occurrence frequency of each item. Items 1, 2, 3, 4 will occur only once, items 5 and 9 occur twice, items 6 and 7 occur three times, and item 8 never occurs. This can be seen in the following diagram:
Based on this collection, we can reconstruct the array from the lowest item so that we end up with the following result:
Creating C++ code for counting sort is quite simple; we just need to prepare the counterArray...
Radix sort is a sorting algorithm that is used if the items we are going to sort are in a large range, for instance, from 0 to 9999. In this sorting algorithm, we sort from the least significant (rightmost) digit until the most significant digit (leftmost). We are going to involve the Queue data structure we learned in Chapter 3, Constructing Stacks and Queues since we will be putting the equal digit in the queue. This means we need ten queues to represent the digits from 0 to 9. Suppose we have an array with the following elements—{429, 3309, 65, 7439, 12, 9954, 30, 4567, 8, 882} as we can see in the following diagram:
Then, we populate each item based on the least significant digit (the last digit) and store them in their respective queue bucket. The diagram for this is as follows:
Since we put them in the queue, we can dequeue each bucket from 0 to 9. In the preceding diagram, we enqueue the bucket from the top so we dequeue it from the bottom. The diagram should be as follows...
By now, we have understood the sorting algorithms concept and have implemented all common sorting algorithms in C++. We have looked at the slowest sorting algorithms that give the time complexity as O(N2): bubble sort, selection sort, and insertion sort. However, if we are lucky, we can have a time complexity of O(N) for both bubble sort and insertion sort since they can detect whether we pass a sorted list. However, for selection sort, we will still have a time complexity of O(N2) even after the input list is sorted.
Other sorting algorithms that are faster than the three preceding algorithms are merge sort and quick sort. Their time complexity is O(N log N) since they have to divide the input list into two sublists. The last, and the fastest, sorting algorithm, are counting sort and radix sort since their time complexity is O(N).
In the next chapter, we are going to discuss a technique to search for an item in an array or a list by using a sorting algorithm.
For reference purposes, you can refer to the following links:
© 2018 Packt Publishing Limited All Rights Reserved
