Designs and Analysis of Algorithms Assignment # 3 Fall 2023 Submitted By: Eeman ljaz 211-1381 DSM Submitted To: Dr. Ramoza AhsanQUESTION 1: [30 points] a) How can you improve the best case efficiency in bubble sort? (The input is already sorted) > Aboolean variable ‘swapped’ determines whether any swapping has happened in a particular iteration, if no swapping has occurred, then the given array is sorted and no more iterations are required. b) What is the best case efficiency of bubble sort in the improvised version? > Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n). ©) The given array is input_array = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with an improvised version? > 4, Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array. d) Whatis the primary difference between merge sort and quicksort in terms of their stability as sorting algorithms? > Quicksort is an unstable sorting technique i.e. it might change the occurrence of two similar elements in the array while sorting. Whereas merge sort is a stable algorithm ie. it doesn't change the occurrence of similar elements(i.e. “equal” elements are ordered in the same order in the sorted list.) €) Define the concept of an “in-place” sorting algorithm and provide an example. Mention which sorting techniques are “in-place” > In-place means that the algorithm does not use extra space for manipulating the input but may require a small though non-constant extra space for its operation. Usually, this space is O(log n), though sometimes anything in O(n) (Smaller than linear) is allowed. Examples of in-place Sorting Algorithms:- Bubble Sort. Is the heap sort always better than the quick sort? Heapsort's runtime is always O(nlogn), but it is generally considered slower than quicksort. In practice, it is used in combination with quicksort: if quicksort picks a wrong pivot several times in sequence, the sorting switches to heapsort VwQUESTION 2 : [20 points] (Codes in notebook) In mergeSort() use count variable to store final answer ‘Add the answer returned from mergeSort() of the left half, mergeSort() of the right half, and merge() to the count. Retum count from mergeSort() © initialize count to 0 1 O(n’) © Innitialize array A 1 © Loop iO to N-1 nt © Inner Loop j=i+1 to N nx (nt) © if Ali] > Al] then 1x1nx/(n-1) © count++ 1 xnx(n-1) © print count 1xnx(n-1) 1 (n-1) + 4n(n-1) +3 n-1+4n?-4n+3 4n?-3n+2 © initialize count to 0 inside merge() mergeSort(): O(nlogn) © while comparing alleft] and alright] in| nLog.n the 3rd step of merge() © if afleft] > afright] then merge(): © count+= mid-left#1 4n2 © return this count from merge() to mergeSort() nLog,n + 4n/2QUESTION 3: [10 Points] (Code in notebook) © Initialize array A * Call heapSort(A): 200000000 For loop staring from end of array Call heapify(A, n) to maintain max-heap Create an empty "sorted" array for the sorted values. Start from the end of the array. Get max element from heap (root) Place in sorted_array and heapify. Repeat until all elements are sorted and stored in “sorted” array Duplicates remain in original order Retum © Display “sorted” arrayQuestion & - S /\ | © 6® i o8 ean m nf ON» f 3 BR rs © aD jh ah lex ee aE eeeQUESTION 5: [25 points] (In Notebook)