16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] 16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Run time typically depends on: How long things take to set up How many operations there are in each step How many steps there are Insertion sort can be faster than merge sort One array, one operation per step But N*log(N) eventually beats N^2 for large N And once it does, the advantage increases rapidly16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Fast, able to handle any data But can’t be done in place View the array as a set of small sorted arrays Initially only the 1-element “arrays” are sorted Merge pairs of sorted arrays Repeatedly choose the smallest element in each This produces sorted arrays that are twice as long Repeat until only one array remains16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort90 11 27 37111631 4901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort90 11 2727 3137111631 4901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort90 11 2727 31 4 1637111631 4901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort90 11 2727 31 4 16 11 3737111631 4901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort11 27 3127 31 4 16 11 3790901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort11 27 3127 31 4 16 11 3737161190 4901116.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Sort11 27 3111 16 27 31 37 9037161190 411416.070 — March 06/2003 — Jayakanth Srinivasan, [email protected]Statement Effort So T(n) = Θ(1) when n = 1, and 2T(n/2) + Θ(n) when n > 1 So what (more succinctly) is T(n)? MergeSort(A, lower_bound, upper_bound)begin T(n)if (lower_bound < upper_bound) ΘΘΘΘ(1)mid = (lower_bound + upper_bound)/ 2 ΘΘΘΘ(1)MergeSort(A, lower_bound, mid) T(n/2)MergeSort(A, mid+1, upper_bound) T(n/2)Merge(A, lower_bound, mid,upper_bound) ΘΘΘΘ(n)end16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] The expression:is a recurrence. Recurrence: an equation that describes a function in terms of its value on smaller functions >+==1221)(ncnTncnT16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Each array size requires N steps But 8 elements requires only 3 array sizes In general, 2 elements requires k array sizes So the complexity is N*log(N) No faster sort (based on comparisons) exists Faster sorts require assumptions about the data There are other N*log(N) sorts, though Merge sort is most often used for large disk filesk16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] Split a problem into simpler subproblems Keep doing that until trivial subproblems result Solve the trivial subproblems Combine the results to solve a larger problem Keep doing that until the full problem is solved Merge sort illustrates divide and conquer But it is a general strategy that is often helpful16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] The visibility rules determine which declarations are visible and directly visible at each place within a program. The visibility rules apply to both explicit and implicit declarations Direct Visibility immediate visibility use-visibility16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] In general, a subprogram call involves:1. save execution status of the calling program unit2. parameter passing3. pass return address to subprogram4. transfer control to subprogrampossibly: allocate local variables, provide access to non-locals in general, a subprogram return involves:1. if out-mode parameters or return value, pass back value(s)2. deallocate parameters, local variables3. restore non-local variable environment4. transfer control to the calling program unit16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] No Information Flow (No Parameters)procedure <procedure name> is <procedure name> - the name of the procedure.With Information Flow (With Parameters)procedure <procedure name> ( <formal parameter name> : <mode> <data type>;<formal parameter name> : <mode> <data type>;. . . ) is <procedure name> - the name of the procedure. <formal parameter name> - the name of a parameter. <mode> - the mode (in, out, or in out) of the parameter. <data type> - the data type for the parameter.16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected]! Implementation method is determined by the compilerin → by-valueout → by-resultin out → by-value-result (for non-structured types)→ by-value-result or by-reference (for structured types) choice of in out method for structured types is implementation dependent16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected]! ! By Value Parameter is treated as local variable Initialized to argument value By Result Parameter is treated as a local variable with no initialization When the function terminates, the value of the parameter is passed to the argument By Value Result (In Out) Combination of by-value and by-result methods Treated as local variable, initialized to argument, passed back when done16.070 — March 06/2003 — Jayakanth Srinivasan, [email protected] If the subprogram is independent of invocation (e.g., constants, instructions) => store in static code segment If info is dependent upon the particular invocation (e.g., return value, parameters, local variables ) =>must store an activation record for each invocationActivation
View Full Document
Unlocking...