4 Non-comparison sorting algorithms
These lectures covers the concept of decision trees for sorting algorithms and the worst-case time complexity of comparison sorts, followed by the introduction of non-comparison sorting algorithms such as counting sort, radix sort, and bucket sort. The lecture includes a review of the pseudocode for counting sort and a simulation of its execution with a small input, as well as an explanation and implementation challenge for radix sort using provided pseudocode. The lecture concludes with an overview of bucket sort, including a high-level pseudocode and worst and best case complexity analysis.
4.1 Introduction
This topic discusses the maximum number of comparisons a sorting algorithm must make to find the correct arrangement among all the different arrangements of an unsorted array of N elements, which is visualized as a decision tree. The length of the longest path in the decision tree is equal to the maximum number of comparisons made by a sorting algorithm, and it is proven that no comparison sort algorithm can be better than NlogN in the worst case. Then, three sorting algorithms that do not use comparisons in their core processing and have linear running times in the worst case are introduced: Counting sort, Radix sort, and Bucket sort.
4.2 Counting sort
Counting sort is a non-comparison sorting algorithm that has a linear running time in the worst case. It sorts an array by counting the frequency of each number in the set and using that information to create a sorted array. The algorithm works by first creating an array C with the correct number of elements based on the maximum value stored in A plus 1, then counting the frequency at which the elements in A appear and storing that information in C, and finally, creating the resulting sorted array R by visiting every position in C and copying the corresponding elements as many times as required. Counting sort can only sort integer numbers and requires extra memory proportional to the maximum number in the set of numbers to sort plus one.
In this lecture, the pseudocode for the counting sort algorithm was reviewed and the execution of the algorithm was simulated with a specific small input. The pseudocode initializes variables, counts the number of times every number appears in the input array, and fills in the content of the sorted array. The time complexity of counting sort is O(n+k), where n is the size of the input array and k is the range of the input numbers. The lecture concludes by asking the viewer to calculate the time complexity of counting sort.
4.3 Radix sort
In this lecture, you will learn about Radix sort, which is a non-comparison sort that sorts numbers by dividing them into digits and sorting them starting from the least significant digit. The numbers are sorted in passes, and the algorithm used for sorting each digit must be stable. Radix sort has a linear worst-case running time and can be used with decimal numbers. The time complexity of Radix sort is d times the complexity of counting sort, which is equal to (N + k), where d is the number of digits, N is the length of the array to be sorted, and k is the maximum value of any digit. A challenge is given to implement Radix sort using the pseudocode provided and modify counting sort to work inside Radix sort.
4.4 Bucket sort
The lecture introduces bucket sort, a non-comparison sorting algorithm that uses buckets to sort an array of numbers. The algorithm works by placing each number in its corresponding bucket and then sorting the contents of each bucket before copying them back to the original array. The algorithm assumes that the numbers in the original array are uniformly distributed, as otherwise, it may result in a worst-case scenario where all numbers go to the same bucket, which would result in a time complexity that depends on the sorting algorithm used. Bucket sort can be classified as either a non-comparison sort or a comparison sort, depending on the sorting algorithm used to sort the contents of each bucket. The lecture provides a high-level pseudocode of bucket sort, and the worst and best case complexity analysis of the algorithm.