Question

2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Gi pseudocode for an algorithm that will solve the following problem an array A[1..n] that contains every number between 1 and n +1 in Given sorted order, except that one of the numbers is missing. Find the missing ive number. Your algorithm should run in time θ(log n). (Hint: Modify Binary search). A pseudocode means an algorithm with if statements and loops, etc. Don't just write a paragraph. Also, if your algorithm is unclear, please explain what it does

Answer 1

1.

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 1C++ prog #inelude iostream> tation of Heap Sort ran for sing namespace std 6 To heapify a subtree rooted vith node i which is // an index in arr [], n is size of heap 8 void heapify (int arr],int n, int i) int largest : 1 Initialiae largest as root l 10 Int 1-2+1 + 1; // left-2*ǐ + 1 12 int r一2+ī + 2; // right-2-ǐ + 2 13 14 I left child is larger than root 15 i1 (1<n&&arr[l] arr[largest]) largest-l 16 17 18 / r right child is larger than largest so far 1 (r<n&arrr] arr[largest]) largest-r 19 20 21 I largest is not root 23 1 (largest!-1) 24 25 swap (arri, arr [largest]) 26 27 Recursively heapify the affected sub-tree heapify(arr, n largest) 28 29 30 L 31 32 main Eunction to do heap sort , Con piler % Resources db compile Log V Debug @ Find Results Line: 10 Col: 52 Sel: 0 Lines: 68 Length: 1494 Done parsing Insert all 7:04 AM 5/22/2019

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 31 32 / main function to do heap sort 33 void heapSort (int arr,int n) 34 E 35 // Build heap (rearrange array) 36 37 heapify (arr, n, 1) 38 39 7 One by one extract an elenent from heap for (int i-n-1: 1-0: 1--) 40 41 Nove current root to end 42 43 swap (arr [O],arr[i]) 49 45 cal1 max heapify on the reduced heagp heapify(arr, i, 0) 46 ร์7 48 49 S0 A utility function to print array of size n / 51 void printArray (int arz[], int n) 53 for 1nt 1-0: 1<n: ++1) cout << arri]<" 54 cout <<"n" 56 1 57 S8 int main 60 int arr [] = 17,3,9,4,2,5,6,1,8); int n-s1zeof (arr) /sizeof (arro1) 61 62 㗊Compiler % Resources dih Compile Log V Debug @ Find Results e Log Debug Find Result Line: 10 Col: 52 Sel: 0 Lines: 68 Length: 1494 Done parsing Insert all 7:05 AM 5/22/2019

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 37 heapify (arr, , i) 38 39 One by one extract an element from heap for int i-n-1: i-0: i--) 40 41 42 Move current root to end 43 swap (arrfo, arr [i]) 45 call max heapity on the reduced heap 46 heapify (arr, 1, 0) 48 L 49 50 A utility function to print array of sizen 51 void printArray (int arr, int n) 52曰{ 53 for (int i-0: i<n: ++i) cout < arr[i]<<" cout <<"" 54 56 57 58 int main ) 60 int arr]-17,3,9,4,2,5,6,1,8) int nsizeof (arr)/sizeof (arr [ 61 62 63 heapSort (arr, n) 64 65 cout << "Sorted array is \n" printarray (arr, n): 67 68 88 compiler % Resources dh compile Log Debug ⑥ Find Results Line: 10 Col: 52 Sel: 0 Lines: 68 Length: 1494 Done parsing Insert all 7:05 AM 5/22/2019

Dev-C+ 5.2.0.2 File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 37 heapify (arr, , i) 38 CAProgram Files auser.exe orted array is 2 3 45689 Process exited nornally Press any key to cont inue 59 E 60 int arr [] _ {7,3,9,4,2,5,6,1,8); int nsizeof (arr)/sizeof (arr [ 61 62 63 heapSort (arr, n) 64 65 cout << "Sorted array is \n" printarray (arr, n): 67 68 Resources dh compile Log Debug B Find Results 88 Compiler e Log Debug Find Result Line: 10 Col: 52 Sel: 0 Lines: 68 Length: 1494 Done parsing Insert all 7:05 AM 5/22/2019

2.

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes | ν.cpp 1C progran for Merge Sort/ # inelude<stdlib. h> # include<stdio. h> 5 Merges tvo subarrays of arr 6 First subarray is arrri.mJ 7 11Second subarray is arrm+ir 8 void merge(int arr[], int 1, int m, int r) 10 int i, int nim1 1 12 int n2 13 14 /create temp arrays 15 16 17 Copy data to temp arrays Lj and Rr*/ 19 し[1] -arr [1 1]; 0: j < n2: j++) + 20 for (j 21 23 Merge the tenp arrays back into arril..rJ/ i- 0: / Initial index of first subarray 24 25 -0: 7 Initial index of second subarray k-l: 7 Initial index of merged subarray 26 27 28 29 if (L[4] R[j]) <= 30 arr [k]-LI1 31 32 88 compiler % Resources dh compile Log Debug ⑥ Find Results Line: 88 Col: 1 Sel: 0 Lines: 103 Length: 1953 Done parsing Insert re 7:12 AM 5/22/2019

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes | ν.cpp 27 while (i < ni && j < n2) 28 29 30 31 arr [k] L[41: = 32 34 elsc 35 36 37 38 39 41 Copy the renaining elements of L, f there are any while (1 < ni) 42 ร์3 45 46 arrk] -Li] 47 4 8 49 50 51 Copy the renaining elements of Rr there 52 are any while (j < n2) 53 54 arr [k] R[j]; = 56 57 58 88 compiler % Resources dh compile Log Debug ⑥ Find Results Line: 88 Col: 1 Sel: 0 Lines: 103 Length: 1953 Done parsing Insert L all 4) 7:12 AM 5/22/2019 re ▲

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 56 57 58 59 60 61 1 is tor lert index and r is right index of the 62 sub-array of arr to be sorted 63 void mergeSort (int arr],int 1, int r) 64日{ 65 if (1< r) 67 Same as (1+)/2, but avoids overflov or /large 1 and h intm-1+(-1)/2 68 69 70 71 Sort first and second halves 72 mergeSort (arr, l, ) 73 mergesort (arr, +,r) 74 75 1, r); mたrge (arr , m, 76 77 L 78 79 &UTILITY FUNCTIONS/ 80 Function to print an array / 81 Void printArray (int A[,int size) 82 E int i 83 84 85 printf("sd",A1]) printt("n" 86 87 , Con piler % Resources nh compile Log V Debug 14 Find Results Line: 88 Col: 1 Sel: 0 Lines: 103 Length: 1953 Done parsing Insert re all 4) 7:12 AM 5/22/2019 ▲ 'i

File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes | ν.cpp 72 mergeSort (arr, l, ) 73 mergesort (arr, +,r) 74 75 1, r); mたrge (arr , m, 76 77 L 78 79 &UTILITY FUNCTIONS/ 80 Function to print an array / 81 Void printArray (int A[,int size) 82日{ 83 84 int i 85 printf("sd",A1]) printt("n" 86 89 int main) 90曰{ 91 int arr-17,3,9,4,2,5,6,1,8) int arr sizesizeof (arr)/sizeof (arr[o]) 92 93 printt("Given array 1s n" 94 printArray (arr, arr size) 95 96 97 mergesort (arr,, arr size - 1) 98 printf("nSorted array is \n" printArray (a,arr size) return o 100 101 102 103 Resources dh compil 88 Compiler e Log Debug Find Results Line: 88 Col: 1 Sel: 0 Lines: 103 Length: 1953 Done parsing Insert L all 4) 7:12 AM 5/22/2019 re ▲

Dev-C+ 5.2.0.2 File Edit Search View Project Execute Debug Tools CVS Window Help globala) Project Classes V.cpp 72 mergeSort (arr, l, ) 73 mergeSort (arr,+1,r) CAProgram Files auser.exe 394 25 6 1 8 orted array is 2 3 45689 Process exited nornally Press any key to continue. . printt("Given array 1s n") printArray (arr, arr size) 95 96 97 mergesort (arr,, arr size - 1) 98 printf("nSorted array is \n" printArray (a,arr size) return o 100 101 102 103 88 compiler % Resources dh compile Log Debug ⑥ Find Results Line: 88 Col: 1 Sel: 0 Lines: 103 Length: 1953 Done parsing Insert l 712 AM 5/22/2019 re

3.

File Edit Format View Help The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases 1) Array is already sorted in same order. 2) Array is already sorted in reverse order 3) All elements are same (special case of case 1 and 2) Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot. The reason for this worst case performance is that, after partitioning, one partition will be of size 1, and the other will be of size n-1 So, the Time to quick sort ‘n' elements T(n) = Time it takes to partition "n. elements 0(n) + Time to quick sort ·n-1. elements T(n-1) So, T(n) -T(n-10(n) T(n)(n 2) quicksort Partition Algorithm There can be many ways to do partition, The logic is simple, we start from the leftmost element and keep track of index of Sort and Heap Sort, QuickSort is faster in practice, because its inner loop can be the extra space used for merge sort increases the running time of the algorithm. re 7:28 AM

4.

File Edit Format View Help METHOD 1(Use sum formula) Algorithm 1. Get the sum of numbers totaln(n+1)/2 2. Subtract all the numbers from sum and you will get the missing number : truct the n nyau vill get the aistng umber METHOD 2(Use XOR) 1) XOR all the array elements, let the result of XOR be X1 2) XOR all numbers from 1 to n, let XOR be X2. XOR of X1 and X2 gives the missing number. For both time complexity is 0(n) re ll 7:36 AM