Sorting Luong The Nhan, Tran Giang Son Chapter 10 Sorting Sorting concepts Insertion Sort Straight Insertion Sort Data Structures and Algorithms Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Luong The Nhan, Tran Giang Son Bubble Sort Faculty of Computer Science and Engineering Devide-and- Conquer University of Technology, VNU-HCM Quick Sort Merge Sort 10.1 Sorting Outcomes Luong The Nhan, • L.1 - Depict the working steps of sorting Tran Giang Son algorithms step-by-steps.2 - Describe sorting algorithms by using pseudocode.3 - Implement sorting algorithms using C/C++ .4 - Analyze the complexity and develop Insertion Sort experiment (program) to evaluate sorting algorithms. Straight Insertion Sort Shell Sort • L.5 - Use sorting algorithms for problems in Selection Sort Straight Selection Sort real-life. Heap Sort Exchange Sort • L.4 - Develop recursive implementations for Bubble Sort methods supplied for the following structures: list, tree, Devide-and- Conquer heap, searching, and graphs. Quick Sort Merge Sort • L.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).2 Sorting Contents Luong The Nhan, Tran Giang Son 1 Sorting concepts 2 Insertion Sort Straight Insertion Sort Shell Sort Sorting concepts Insertion Sort 3 Selection Sort Straight Insertion Sort Shell Sort Straight Selection Sort Selection Sort Heap Sort Straight Selection Sort Heap Sort Exchange Sort 4 Exchange Sort Bubble Sort Bubble Sort Devide-and- Conquer Quick Sort 5 Devide-and-Conquer Merge Sort Quick Sort Merge Sort 10.3 Sorting Luong The Nhan, Tran Giang Son Sorting concepts Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.4 Sorting Sorting Luong The Nhan, Tran Giang Son One of the most important concepts and common applications in computing.
Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.5 Sorting Sorting Luong The Nhan, Tran Giang Son Sort stability: data with equal keys maintain their relative input order in the output. Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.6 Sorting Sorting Luong The Nhan, Tran Giang Son Sorting concepts Sort efficiency: a measure of the relative Insertion Sort Straight Insertion Sort efficiency of a sort = number of comparisons + Shell Sort Selection Sort number of moves. Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.7 Sorting Sorting Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.8 Sorting Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.9 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son • The list is divided into two parts: sorted and unsorted. • In each pass, the first element of the Sorting concepts unsorted sublist is inserted into the sorted Insertion Sort Straight Insertion Sort sublist.
Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.10 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.11 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.12 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.13 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.14 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.15 Sorting Straight Insertion Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.16 Sorting Straight Insertion Sort Luong The Nhan, Algorithm InsertionSort() Tran Giang Son Sorts the contiguous list using straight insertion sort. if count > 1 then current = 1 while current < count do Sorting concepts temp = data[current] Insertion Sort walker = current - 1 Straight Insertion Sort Shell Sort while walker >= 0 AND temp.key < Selection Sort data[walker].key do Straight Selection Sort Heap Sort data[walker+1] = data[walker] Exchange Sort walker = walker - 1 Bubble Sort end Devide-and- Conquer data[walker+1] = temp Quick Sort Merge Sort current = current + 1 end end End InsertionSort 10.17 Sorting Shell Sort Luong The Nhan, Tran Giang Son • Named after its creator Donald L. • Given a list of N elements, the list is Sorting concepts Insertion Sort divided into K segments (K is called the Straight Insertion Sort Shell Sort increment). Selection Sort Straight Selection Sort • Each segment contains N/K or more Heap Sort Exchange Sort elements.
Bubble Sort Devide-and- • Segments are dispersed throughout the list. Conquer Quick Sort Merge Sort • Also is called diminishing-increment sort.18 Sorting Shell Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.19 Sorting Shell Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort • For the value of K in each iteration, sort Selection Sort Straight Selection Sort the K segments. Heap Sort Exchange Sort Bubble Sort • After each iteration, K is reduced until it is Devide-and- Conquer 1 in the final iteration. Quick Sort Merge Sort 10.20 Sorting Example of Shell Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.21 Sorting Example of Shell Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.22 Sorting Choosing incremental values Luong The Nhan, Tran Giang Son • From more of the comparisons, it is better when we can receive more new information.
Sorting concepts Insertion Sort • Incremental values should not be multiples Straight Insertion Sort Shell Sort of each other, other wise, the same keys Selection Sort Straight Selection Sort compared on one pass would be compared Heap Sort Exchange Sort again at the next. Bubble Sort Devide-and- Conquer • The final incremental value must be 1. Quick Sort Merge Sort 10.23 Sorting Choosing incremental values Luong The Nhan, Tran Giang Son • Incremental values may be: 1, 4, 13, 40, 121,. kt = 1 Sorting concepts ki−1 = 3 ∗ ki + 1 Insertion Sort t = | log3 n| − 1 Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort • or: Heap Sort Exchange Sort 1, 3, 7, 15, 31,.
Bubble Sort Devide-and- kt = 1 Conquer Quick Sort ki−1 = 2 ∗ ki + 1 Merge Sort t = | log2 n| − 1 10.24 Sorting Shell Sort Luong The Nhan, Tran Giang Son Algorithm ShellSort() Sorts the contiguous list using Shell sort. k = first_incremental_value Sorting concepts while k >= 1 do Insertion Sort segment = 1 Straight Insertion Sort Shell Sort while segment <= k do Selection Sort Straight Selection Sort SortSegment(segment) Heap Sort Exchange Sort segment = segment + 1 Bubble Sort end Devide-and- Conquer Quick Sort k = next_incremental_value Merge Sort end End ShellSort 10.25 Sorting Shell Sort Algorithm SortSegment(val segment <int>, val k Luong The Nhan, Tran Giang Son <int>) Sorts the segment beginning at segment using insertion sort, step between elements in the segment is k. current = segment + k Sorting concepts while current < count do Insertion Sort temp = data[current] Straight Insertion Sort Shell Sort walker = current - k Selection Sort while walker >=0 AND temp.key < Straight Selection Sort Heap Sort data[walker].key do Exchange Sort data[walker + k] = data[walker] Bubble Sort Devide-and- walker = walker - k Conquer end Quick Sort Merge Sort data[walker + k] = temp current = current + k end End SortSegment 10.26 Sorting Insertion Sort Efficiency Luong The Nhan, Tran Giang Son • Straight insertion sort: Sorting concepts 2 f (n) = n(n + 1)/2 = O(n ) Insertion Sort Straight Insertion Sort Shell Sort Selection Sort • Shell sort: Straight Selection Sort Heap Sort 1.25 O(n ) (Empirical study) Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.27 Sorting Luong The Nhan, Tran Giang Son Sorting concepts Selection Sort Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.28 Sorting Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort In each pass, the smallest/largest item is Shell Sort Selection Sort selected and placed in a sorted list. Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.29 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son • The list is divided into two parts: sorted and unsorted.
• In each pass, in the unsorted sublist, the Sorting concepts smallest element is selected and exchanged Insertion Sort Straight Insertion Sort with the first element. Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.30 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.31 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.32 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.33 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.34 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.35 Sorting Straight Selection Sort Luong The Nhan, Tran Giang Son Sorting concepts Insertion Sort Straight Insertion Sort Shell Sort Selection Sort Straight Selection Sort Heap Sort Exchange Sort Bubble Sort Devide-and- Conquer Quick Sort Merge Sort 10.36 Sorting Straight Selection Sort Luong The Nhan, Algorithm SelectionSort() Tran Giang Son Sorts the contiguous list using straight selection sort. current = 0 while current < count - 1 do smallest = current Sorting concepts walker = current + 1 Insertion Sort Straight Insertion Sort while walker < count do Shell Sort Selection Sort if data [walker].