CHAPTER 11
Sorting Algorithms (Part 1)
By Prof. Rafael Orta, M.S.
NOTE: The material in this presentation is a compilation from C++ for Dummies by Stephen Randy Davis and the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
This week agenda
Sorting is the process of converting a list of elements into ascending (or descending) order.
The challenge of sorting is that a program can't "see" the entire list to know where to move an element. Instead, a program is limited to simpler steps, typically observing or swapping just two elements at a time. So sorting just by swapping values is an important part of sorting algorithms.
You can also sort strings by comparing ascii values.
Sorting Introduction
Selection sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.
Selection Sort
3 Steps
Selection Sort
Swap numbers
Initialize indexes
Swap numbers
Initialize indexes
Identify the smallest
Identify the smallest
Swap numbers
Initialize indexes
Unsorted array
Initialize indexes
Identify the smallest
Swap numbers
Identify the smallest
Any volunteer for sorting the array below using selection sort for 2 extra points in your final test ?.
The professor will help !
Let’s examine the program
Selection sort may require a large number of comparisons. The selection sort algorithm runtime is O(N2). If a list has N elements, the outer loop executes N - 1 times. For each of those N - 1 outer loop executions, the inner loop executes an average of 𝑁2 times. So the total number of comparisons is proportional to (𝑁−1)⋅𝑁2, or O(N2). Other sorting algorithms are more complex but have faster execution times.
Insertion Sort
Insertion sort is a sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.
Unsorted array
Compare sorted and next unsorted
Recursively compare and swap
Assume the first element is sorted
Compare sorted and next unsorted
Recursively compare and swap
Compare sorted and next unsorted
Recursively compare and swap
Compare sorted and next unsorted
Any volunteer for sorting the array below using insertion sort for 2 extra points in your final test ?.
The professor will help !
Insertion Sort
Insertion sort's typical runtime is O(N2). If a list has N elements, the outer loop executes N - 1 times. For each outer loop execution, the inner loop may need to examine all elements in the sorted part. Thus, the inner loop executes on average 𝑁2 times. So the total number of comparisons is proportional to (𝑁−1)⋅(𝑁2), or O(N2). Other sorting algorithms involve more complex algorithms but faster execution.
Nearly sorted lists
For sorted or nearly sorted inputs, insertion sort's runtime is O(N). A nearly sorted list only contains a few elements not in sorted order. Ex: (4, 5, 17, 25, 89, 14) is nearly sorted having only one element not in sorted position.
Insertion sort for nearly sorted list
…....
Shell Sort
Shell sort's interleaved lists
Shell sort is a sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. Shell sort uses gap values to determine the number of interleaved lists. A gap value is a positive integer representing the distance between elements in an interleaved list. For each interleaved list, if an element is at index i, the next element is at index i + gap value.
Shell sort begins by choosing a gap value K and sorting K interleaved lists in place. Shell sort finishes by performing a standard insertion sort on the entire array. Because the interleaved parts have already been sorted, smaller elements will be close to the array's beginning and larger elements towards the end. Insertion sort can then quickly sort the nearly-sorted array.
Any positive integer gap value can be chosen. In the case that the array size is not evenly divisible by the gap value, some interleaved lists will have fewer items than others.
Shell Sort
If a gap value of 3 is chosen, shell sort views the list as 3 interleaved lists. 56, 12, and 75 make up the first list, 42, 77, and 91 the second, and 93, 82, and 36 the third.
Shell sort will sort each of the 3 lists with insertion sort.
The result is not a sorted list, but is closer to sorted than the original. Ex: The 3 smallest elements, 12, 42, and 36, are the first 3 elements in the list.
Sorting the original array with insertion sort requires 17 swaps.
Sorting the interleaved lists required 4 swaps. Running insertion sort on the array requires 7 swaps total, far fewer than insertion sort on the original array.