( 6 pts, 3 pts each)



Sorting Hands-on70 pts, Due May 21 (along with programming)Contents TOC \o "1-3" \h \z \u ( 6 pts, 3 pts each) PAGEREF _Toc40223175 \h 1(20 pts, 2 pts each PAGEREF _Toc40223176 \h 1(3 pts) PAGEREF _Toc40223177 \h 2(15 pts, 5 pts each) Identify the sorts and output: PAGEREF _Toc40223178 \h 2(7 pts) MergeSort PAGEREF _Toc40223179 \h 4(7 pts) RadixSort: PAGEREF _Toc40223180 \h 5(12 pts) Average Running Time (from MiniProject programming results): PAGEREF _Toc40223181 \h 5Aside: You know in job interviews you’re going to get at least one question on sorting and running times!!!Answer the following questions:( 6 pts, 3 pts each)List two things that are much easier with sorted data than with unsorted data:Why is radixSort considered a non-comparison based sorting algorithm?(20 pts, 2 pts each (2 pts) Which sorting algorithm that we learned about runs in-order, in reverse order, and completely random order is all run in o(nlogn) ___________________________Which algorithm that we learned about might perform better (run faster) if we took the ordered list and completely randomized it first? ___________________________Which algorithm we learned about runs in O(1) when the list is already in order? ____________________________Which algorithm that we learned about’s running time depends on its largest number? ________________________Which algorithm we learned about takes twice the space when it is sorting? ___________________________Which of the algorithms we learned about sorts an ordered list , a reverse ordered list, and a random list (all three) in 0(n2)? ____________________________Which of the 3 traversal methods would we use to print out a binary search tree as sorted?10.Stability is when you’re sorting data and two values that are equal would, after all the data is sorted, still be in the same order in which they came in. Think of it this way (this is an analogy!!): In the ER waiting room, if a doctor walks in, he’s going to take the worst cases first. So the patients in the waiting room would be sorted by worst case to best case. But what if there are two patients with exactly the same level injury – both were bitten by zombies, and in the process of running away tripped and fell down a ravine where they broke two ribs, their pinkie finger and lost a toenail. Which patient should the doctor take first? The one who came in first. So, when sorting, sometimes Stability matters. Would quicksort preserve stability? ________________Would mergesort preserve stability? ____________________Would selectionsort preserve stability? _______________________(3 pts) Why would sorting the following sequence with radixSort be a bad idea?324, 186, 18, 429, 367, 32893864735235763, 945, 310, 72, 694********************************************************************************Note that for the following sorting algorithms, I asked you to only do a limited number of passes (some partial run of the sorting algorithm). If I asked you what are the results of running a sorting algorithm – any sorting algorithm – the results would always be a sorted list, so that doesn’t really show me that you understand anything about the process of how the particular sort works. My point (and I do have one) is pay attention to how many passes the algorithm requires in order to get the correct output.(15 pts, 5 pts each) Identify the sorts and output:Given the following Code:void aSort (char arr[], int length){int j= 0;string temp = arr[0];for (int i = 1; i < length; i++) {j = i;temp = arr[j];j--;while (j >= 0 && temp < arr[j]){ arr[j+1] = arr[j]; j--; } arr[j+1] = temp;}return ;} (2 pts) Identify the above sorting algorithm: ____________________char arr[] = {'v','r','g','i','a','s','m','y','p','h','u','b','s','l'}; (3 pts) Assuming:the above array is the input array,The algorithm makes three passes (i<3)Every other value of the resulting array is printed outWhat is printed out when the above algorithm is called with the following code (note the 4 as an input parameter): ____________________*********************************************************************************.Given the following code:int main() { char arr [] = {'m','s','d','y','g','r','p','a','t','o','c','e','j','h','l'}; x->partition2(0,14,arr);//PRINTED HERE???cout<<arr [11]<<arr [13]<<arr [4]<< arr [8]<<arr [13]<<" "<<arr[14]<< arr[1]<<arr[9]<< arr[10]<<arr[3]<< endl;}int help(int beg,int end, char arr[],) {int x = beg;int y = end;string tmp;string j = arr[x++];while (x <= y) {while (arr[x] < j) x++;while (arr[y] > j) y--;if (x <= y) { tmp = arr[x]; arr[x] = arr[y]; arr[y] = tmp; x++; y--;}}arr[beg] = arr[y];arr[y] = j;return y;}void Sort1(char arr[], int beg, int end) {int m = help(beg,end, arr);if (m-1 > beg) {Sort1(arr,beg,m-1);}if (m+1 < end) {Sort1(arr,m+1,end);}}(2 pts) What sort is this? _______________________________________(3 pts) Show what is printed out in main ___________________________________________*********************************************************************************Given the following sort code:void aSort3(char arr[], int len, int loops) {for(int i = 0; i < loops; i++) {int m = i;for (int j = i+1; j < len; j++) {if (arr[j] < arr[m]) {m = j;}}char tmp = arr[m];arr[m] = arr[i];arr[i] = tmp;}}(2 pts) Identify the above sorting algorithm: _________ _______________(3 pts) What is printed out when the above algorithm is called with the following code (note the 6 as an input parameter): ____ _____________char arr3[16] = {'u','c','g','m','i','n','v','p','t','h','w','a','l','i','r','k'};aSort3(arr3,16,6); //note the 6 herefor (int i = 1; i < 16; i+=2) { //every other value, starting at 1cout << arr3[i];}cout << endl;*********************************************************************************(7 pts) MergeSortFill in the blanks in the merge algorithm to merge 2 lists:void mergeSort(int arr[],int l1,int l2){int k; if(l1<l2) { k=(l1+l2)/2; mergeSort(arr,l1,k); mergeSort(arr,k+1,l2); merge(arr,l1,k,l2); }}void merge(int arr[], int le, int m, int r) { // the helper function for the above sorting algorithm int i, j, k; int lenL = m - le + 1; int lenR = r - m; int leftArr[lenL] // the sorted left array int rightArr[lenR]; // the sorted right array for(i = 0; i < lenL; i++) { leftArr[i] = arr[le + i]; } for(j = 0; j < lenR; j++) { rightArr[j] = arr[m + 1+ j]; } i = 0; j = 0; k = le; while (i < lenL && j < lenR) { if (_____________________________) { ___________________________; ___________________________; } else { ___________________________; ___________________________; } k++; } while (i < lenL) { arr[k] = leftArr[i]; i++; k++; } while (j < lenR) { arr[k] = rightArr[j]; j++; k++; }}Part C: given the following array:string alpha[] = {"g","f","l","v","s","a","m","h","i","j","p","n","h","o","g","v"};assume mergesort has been modified so that the merge portion only happens twice. Show the output of the following:for (int i = 0; i < 15; i+=2) {cout << alpha[i] << ", ";}___________________________________***************************************************************************************************(7 pts) RadixSort: How many “bins” in your radixSort array (note that I don’t mean how many numbers you’re sorting, I mean how many bins, each of which can hold more than one of the numbers you’re trying to sort). (2 pts) __________________(5 pts) Show each pass of a radixSort with the following list of numbers:799, 545,197, 68,16, 470, 623, 181, 175,473, 307, 279, 114, 246, 713, 493(12 pts) Average Running Time (from MiniProject programming results):What is the average running time of:SelectionSort__________________InsertionSort___________________QuickSort ________________MergeSort __________________MinMaxSelection ___________________TimSort ___________________ ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download