Class Notes (835,117)
Canada (508,937)
CMPT 225 (60)
John Edgar (28)
Lecture

CMPT 225 Week 7 Lecture 3

3 Pages
101 Views
Unlock Document

Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
Summer

Description
void merge(arr[], low1, high1, low2, high2) { i1 = low1; i2 = low2; itemp = 0; temp = new [high2 - low1 + 1]; // temp array to store everything while(i1 <= high1 && i2 <= high2) { // only when still processing data in BOTH subarrays if (arr[i1] < arr[i2]) { itemp = arr[i1]; i1++ } else { itemp = arr[i2]; i2++ } itemp++; } // only one of these while loops will be true while(i1 <= high1) { temp[itemp++] = arr[i1++]; } while(i2 <= high2) { temp[itemp++] = arr[i2++]; } // still need to write over contents of original array for (itemp = 0; itemp < (high2 - low1 + 1); itemp++) { arr[low1 +itemp] = temp[itemp]; } delete[] temp; } Nothing in here varies based on order of data; always same amount of work. This makes it very useful for external sorting and parallel processing. External sorting: common in databases. Normally sorting data: read in main memory, sort. What happens when file doesn't fit in main memory because it is too big? External sorting - external storage. Mergesort allows us to chop up the pieces and put them back together. Same for parallel processing. Want to break up file between number of different processes to deal with faster. SortingAlgorithms we have looked at so far: Algorithm | (Avg) Time Complexity | (Avg) Space Complexity | Stable Selection | O(n^2) | O(1) | No Insertion | O(n^2) | O(1) | Yes Quicksort | O(nlogn) | O(logn) | No Mergesort | O(nlogn) | O(n) | Yes Heapsort | O(nlogn) | O(1) | No Quicksort - recursive invocations pushed onto callstack. logn recursive invocations. Heapsort - as long as they implement bubble up and down iteratively, do everything in place. What is stable? How common is it, really, to sort giant files of integers? Much more likely to be sorting complex data types. Data with more than one attribute. Student records, etc. Can be sorted by multiple values. Examp
More Less

Related notes for CMPT 225

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit