Description

[CSE10100] Introduction to Computer Engineering ( 컴퓨터공학개론 ) Chapter 7 Seungkyu Lee Assistant Professor, Dept. of Computer Engineering Kyung Hee University Mid-term Exam Date: Apr. 22 (Tuesday), in class

Information

Category:
## Business & Finance

Publish on:

Views: 57 | Pages: 23

Extension: PDF | Download: 0

Share

Transcript

[CSE10100] Introduction to Computer Engineering ( 컴퓨터공학개론 ) Chapter 7 Seungkyu Lee Assistant Professor, Dept. of Computer Engineering Kyung Hee University Mid-term Exam Date: Apr. 22 (Tuesday), in class 10 Problems Scope: Ch.1~Ch.7 You can use English, Korean or Both! 2 Selection Sort Figure 7.11 Example of a selection sort (sorted elements are shaded) 3 Selection Sort Selection Sort Set firstunsorted to 0 WHILE (current length 1) Find smallest unsorted item Swap firstunsorted item with the smallest Set firstunsorted to firstunsorted + 1 4 Selection Sort Find smallest unsorted item Set indexofsmallest to firstunsorted Set index to firstunsorted + 1 WHILE (index = length 1) IF (data[index] data[indexofsmallest]) Set indexofsmallest to index Set index to index + 1 Set index to indexofsmallest 5 Selection Sort Swap firstunsorted with smallest Set tempitem to data[firstunsorted] Set data[firstunsorted] to data[indexofsmallest] Set data[indexofsmallest] to tempitem 6 7 Bubble Sort Bubble Sort Bubble Sort Set firstunsorted to 0 Set index to firstunsorted + 1 Set swap to TRUE WHILE (index length AND swap) Set swap to FALSE Bubble up the smallest item in unsorted part Set firstunsorted to firstunsorted + 1 8 Bubble Sort Bubble up Set index to length 1 WHILE (index firstunsorted + 1) IF (data[index] data[index 1]) Swap data[index] and data[index 1] Set swap to TRUE Set index to index - 1 9 Insertion Sort The item being added to the sorted portion can be bubbled up as in the bubble sort 10 Insertion Sort InsertionSort Set current to 1 WHILE (current length) Set index to current Set placefound to FALSE WHILE (index 0 AND NOT placefound) IF (data[index] data[index 1]) Swap data[index] and data[index 1] Set index to index 1 ELSE Set placefound to TRUE Set current to current Subprogram Statements We can give a section of code a name and use that name as a statement in another part of the program When the name is encountered, the processing in the other part of the program halts while the named code is executed Remember? 12 Subprogram Statements What if the subprogram needs data from the calling unit? Parameters Identifiers listed in parentheses beside the subprogram declaration; sometimes called formal parameters ex) int myfun (int a); Arguments Identifiers listed in parentheses on the subprogram call; sometimes called actual parameters 13 ex) myfun (4); Subprogram Statements 14 Figure 7.14 Subprogram flow of control 15 Subprogram Statements Recursion Recursion The ability of a subprogram to call itself For example, the factorial of a number is defined as the number times the product of all the numbers between itself and 0: N! = N * (N 1)! Base case: Factorial(0) = 1 (0! is 1) General Case: Factorial(N) = N * Factorial(N-1) 16 Recursion Write Enter n Read n Set result to Factorial(n) Write result + is the factorial of + n Factorial(n) IF (n equals 0) RETURN 1 ELSE RETURN n * Factorial(n-1) 17 Recursion BinarySearch (first, last) IF (first last) RETURN FALSE ELSE Set middle to (first + last)/ 2 IF (item equals data[middle]) RETURN TRUE ELSE IF (item data[middle]) BinarySearch (first, middle 1) ELSE BinarySearch (middle + 1, last) 18 Quicksort Ordering a list using the Quicksort algorithm It is easier to sort a smaller number of items: Sort A F, G L, M R, and S Z and A Z is sorted 19 Quicksort algorithm With each attempt to sort the stack of data elements, the stack is divided at a splitting value, splitval, and the same approach is used to sort each of the smaller stacks (a smaller case) Process continues until the small stacks do not need to be divided further (the base case) The variables first and last in Quicksort algorithm reflect the part of the array data that is currently being processed 20 Quicksort Quicksort(first, last) IF (first last) // There is more than one item Select splitval Split (splitval) // Array between first and // splitpoint 1 = splitval // data[splitpoint] = splitval // Array between splitpoint + 1 // and last splitval Quicksort (first, splitpoint - 1) Quicksort (splitpoint + 1, last) 21 22 Quicksort Quicksort - split Split(splitVal) Set left to first + 1 Set right to last WHILE (left = right) Increment left until data[left] splitval OR left right Decrement right until data[right] splitval OR left right IF(left right) Swap data[left] and data[right] Set splitpoint to right Swap data[first] and data[splitpoint] Return splitpoint 23

Related Search

Computer EngineeringElectrical and Computer Engineering (ECE)Electrical and Computer EngineeringHod of computer engineeringTell us about your research so that we can shComputer Science and EngineeringCOMPUTER SCIENCE \u0026 ENGINEERING COMPUTER Audio Engineering/ Computer ArtsElectrical Engineering and Computer ScienceComputer Systems Engineering

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks