Page 131 [131]
OCR
130 11 MULTIDIMENSIONAL EXPANSION OF THE ALGORYTHMICS... (The input seguence is already sorted in increasing/decreasing order; it is plausible to assume that students will be able to comprehend this intuitive fact.) If students possess the necessary mathematical knowledge, the following guestions can be discussed for arbitrary length seguences (n), otherwise for a specific length (for example: 10, the length of the dancer seguence). Complexity analysis can be supported by introducing the concept of problem decomposition (another key ability regarding CT; see the ISTE/CSTA definition of CT): sorting by successive selections/bubbling/insertions. — How many comparison and swapping operations does the selection, bubble, and insertion sort algorithm imply (for a list with n elements) in the “best case”? — How many comparison and swapping operations does the selection, bubble, and insertion sort algorithm imply (for a list with n elements) in the “worst case”? — The best case time complexity of the selection sort algorithm is O(n’). Why? (It is probably enough to transmit the idea that the number of the needed basic operations (only comparisons) is (n(n-1))/2, which is a second-degree function.) — The worst case time complexity of the selection sort algorithm is O(n’). Why? (The number of the needed basic operations (each comparison is followed by swapping) is (n(n-1)), which is also a second-degree function.) — The best case time complexity of the bubble and insertion sort algorithm is O(n). Why? — The worst case time complexity of the bubble and insertion sort algorithm is O(n’). Why? The teacher should guide students in realizing why some “best case” complexity values differ and why the “worst case” ones do not. Before analysing the time complexity of merge sort algorithm, the concept of divide and conquer should be introduced. This approach will guide students again to a binary tree. To simplify the calculus, we suggest that n = 2*. — How many comparison operations does the merge sort algorithm imply (for a list with n elements) in the “best case”? — How many comparison operations does the merge sort algorithm imply (for a list with n elements) in the “worst case”? Students only need to understand that at each level of the log(n) height binary tree the merging processes assume O(n) basic operations. After these introductory analyses, even the complexity analysis of shell, quick, and heap sort algorithms can be addressed in the same manner. Besides this complexity analysis, the parallel simulation of the algorithms (as they are working side by side on different colour scale bars; see Figure 7.7.f) also supports students in realizing the relative value of them (skill 5).
