6.2: Sorting Algorithms
Notice that the structure for a Saylor course is a tree. The following subunits in the Unit 6 sub-tree describe sort algorithms.
Whereas searching takes a data structure as input and outputs an element of the data structure, sorting is more complex, in that it takes a data structure as input and returns a data structure of the same type, but with the elements rearranged. There are a few search algorithms: linear for a list, depth or breadth traversal for a tree, and binary search. There are several sorting algorithms; unit 6.2 presents a number of them.
6.2.1: Merge and Insertion Sort
You watched these videos earlier, but take some time to review the merge sort discussion at the beginning of the first lecture. Again, focus on recognizing abstraction, decomposition, and composition. Rewatch the second lecture, focusing on the bubble and selection sorts.
The following lectures step through the programming life-cycle process for sorting. The programming process comprises requirements, design, implementation of the design in a programming language, and verification/validation. The last lecture adds maintenance, extending the process to a programming life-cycle process. Please realize that the states of the process overlap and do not have to be performed sequentially.
6.2.2: Quick Sort
This lecture explains the details of the working of quick sort, which is on average 3 times faster than merge sort. The lecture has 3 parts: the first 20 minutes approximately, or first third, gives the explanation -- watch that part of the lecture. You should revisit the second third, or second and third parts of the lecture when you are in unit 6.2.5, later in our course.
6.2.3: Radix Sort
The radix sort does not compare values of the elements to be sorted; it uses the digits (in some radix, e.g. base 2) of integer keys and sorts the keys by sorting, first on the first digit (either the least significant or most significant digit), then on the next significant digit, and so on, up to the last digit. This decomposes the problem into n smaller sorting problems, namely, sorting, all the values that have the same digit in the same radix position of the key. Read this article on the Radix sort. Carefully study the discussion on efficiency and note that the complexity depends on the assumptions made regarding the primitive steps and the data structures used in a program.
6.2.4: Analysis
Understanding the complexity of an algorithm helps us decide whether or not we should use it as the design of a program to solve a problem. Complexity is usually measured in terms of the average number of steps in the computation of a program. The steps can be used to estimate an average bound, lower bound, and upper bound of the amount of time and for the amount of storage space needed for the computation. The lecture explains Big O notation and concept and, using recurrence relations, develops the Big O value for several types of computations. The steps of interest are the primitive steps of an algorithm and the operations that are intrinsic to the data structure used in the program implementation of the algorithm.
Big O estimates are usually associated with the algorithm -- its primitive operations and data structure. Algorithms are grouped into classes associated with linear, n log n, quadratic, and exponential Big O bounds: O(n), O(n times log n), O(n**2), and O(2**n), respectively. For a given value of n, the lecturer gives the values of n, n x log n, n**2, and 2**n, to show the dramatic growth as n grows. If a problems grows by a factor of n an algorithm that grows too fast, e.g. has quadratic or exponential growth, would not be a good choice for the design of a program to solve it.
Note that the details of complexity analysis require a strong mathematical background, and you should focus on the main ideas or 'big picture' first before delving into the details.
The video gives a concise definition of Big O, which is popular for bounding the running time for search and sort algorithms. Additionally, if you feel comfortable with your math background, you should watch the second and third parts of the video.