I am requesting Neha for this assignment. I need consistency and having Neha helps with this... Thank you.
Lecture 4: CS 511 Lecture 1 : CS 425 More on Sorting Quick Sort Selection Sort C++ Programming Quick Sort Algorithm Quick sort is based on dividing the array into two parts using Partition Algorithm, not necessarily into same size. The Partition algorithm arranges all the data about a special data (called the Pivot) in such a way that all the data smaller than the pivot are placed to the left of the pivot and data larger than the pivot are placed to the right of the pivot. Once the data set are divided into two arrays, recursive method is applied to continue further until each sub-problem has only one data left. In general if after each partition, about x*n amount of data go to left and (1-x)*n amount of data go to right, (where x is a fraction less than 1), then the run time T(n) is governed by the following recurrence relation: T(n) = T(x*n) + T((1-x)*n) + Θ(n) Partition Algorithm There are many versions of the Partition algorithms depending on which element in the array is used as the Pivot. In the current lesson, will use Hoare Partition Algorithm where the last data (n-th data) is used as pivot. Take pivot = A[n] Start from I = 1, and check if A[I] > pivot. If no, then increase I = I + 1, i.e. I = 2, and check again if A[I] > pivot. Keep on doing this until the condition that A[I] > pivot is satisfied. This process is called Left Scan. Now starting from the right end, take J = n-1. And check if A[J] < pivot,="" if="" not="" then="" j="J-1" and="" repeat="" the="" same="" comparison,="" continue="" until="" the="" condition="" of="" a[j]="">< pivot="" is="" met.="" this="" process="" is="" called="" right="" scan.="" once="" a="" pair="" of="" elements="" a[i]="" and="" a[j]="" are="" found="" from="" left="" and="" right="" scan,="" then="" check="" if="" i="">< j,="" i.e.="" check="" the="" position="" of="" larger="" element="" (i-th="" element)="" and="" smaller="" element="" (j-th="" element)="" if="" larger="" is="" on="" left="" and="" smaller="" is="" on="" right,="" and="" if="" so,="" then="" only="" swap="" a[i]="" with="" a[j].="" repeat="" left="" scan="" starting="" from="" i="I+1," until="" a[i]=""> pivot Repeat right scan starting from J = J-1, until A[J] < pivot="" check="" again="" if="" i="">< j="" and="" swap="" a[i]="" with="" a[j]="" the="" above="" process="" is="" terminated="" when="" (a)="" either="" i=""> J, then swap A[I] with Pivot or (b) if no smaller element is found, then also swap A[I] with pivot or (c) if no larger element is found from left scan, in that case put a partition around pivot. In the next two pages a pseudocode is given for quick sort and partition algorithm Pseudocode from Quick Sort QUICKSORT(A, p, r) if(p < r)="" q="" ="" partition(a,="" p,="" r)="" q="" index="" for="" part="" quicksort(a,="" p,="" q-1)="" recursive="" call="" quicksort(a,="" q+1,="" r)="" recursive="" call="" the="" partition="" algorithm="" is="" used="" to="" partition="" all="" the="" data="" about="" the="" pivot,="" and="" returns="" the="" index="" of="" the="" new="" place="" where="" the="" pivot="" moves="" to.="" this="" divides="" the="" entire="" array="" into="" two="" halves,="" on="" which="" the="" recursive="" algorithm="" is="" applied="" to="" continue.="" the="" runtime="" of="" quick="" sort="" depends="" not="" only="" on="" number="" of="" data,="" but="" also="" how="" the="" partitioning="" is="" being="" done.="" partition="" algorithm="" there="" are="" many="" different="" partition="" algorithms,="" based="" on="" choice="" of="" pivot.="" hoare="" partition="" uses="" the="" last="" element="" in="" the="" array="" as="" the="" pivot.="" the="" pseudocode="" is="" given="" as="" below:="" partition(a,="" p,="" r)="" pivot="" ="" a[r]="" i="" ="" p="" -1="" j="" ="" r="" while="" true="" repeat="" i="" ="" i="" +="" 1="" until="" a[i]=""> pivot repeat j j -1 until A[j] < pivot="" if="" i="">< j="" exchange="" a[i]="" with="" a[j]="" else="" return="" i="" illustration="" of="" quick="" sort="" given="" the="" following="" data:="" 37,="" 44,="" 21,="" 1,="" 71,="" 16,="" 51,="" 20,="" 30="" i="" 1="" 2="" 3="" 4="" 5="" 6="" 7="" 8="" 9="" runtime="" algorithm="" a[i]="" 37="" i="1" 44="" 21="" 1="" 71="" 16="" 51="" 20="" j="8" 30="" piv="" 2="" left="" scan,="" stopped="" at="" i="1," as="" a[1]=""> pivot Similarly right scan. I < j,="" swap="" a[i]="" with="" a[j]="" 20="" 44="" i="2" 21="" 1="" 71="" 16="" j="6" 51="" 37="" 30="" piv="" 3="" 20="" 16="" 21="" 1="" j="4" 71="" i="5" 44="" 51="" 37="" 30="" piv="" 5="" i=""> J, swap A[I] with pivot 20 I=116211 piv3044 513771 piv4 + 3Completes partition 11621 piv2044 I5137 piv712 + 3 1 116 Piv 16 213751 4444 Piv 511+2Total runtime 25 Runtime Analysis of Quick Sort Partition algorithm takes n number of comparisons in general. Runtime for Quicksort depends on initial data arrangements With the partition algorithm using pivot as the last element, for data already in sorted arrangement or in reversely given arrangement, will be T(N) = N(N-1)/2 = ϴ(N2) For random data, on an average, runtime, T(N) = NlgN Other Sorting Algorithms Selection Sort I = 1 Step1:Find data A[min] that is lowest from all the values from A[I] to A[N] if min != I, then swap A[I] with A[min] Step2: I = I + 1 Repeat step1, until I = N Pseudocode: SelectionSort(A,N) for I = 1 to N-1 min Min(A, I, N) if min != I swap A[I] A[min] Min(A, I, N) returns the index of the minimum data. Selection Sort: Illustration using data Sort the following data using selection sort 25, 41, 16, 30, 6, 34, 10 I1234567RuntimeAlgorithm A[I]254116706 min34106Find min of all data from I = 1 to I = N 6411670253410 min5 6 1016 min702534414 61016 7025 min34413 61016257034 min412 6101625347041 min1Formula 6101625344170Total =21= N(N-1)/2 = 7*(7-1)/2 = 21 Bubble Sort Given a set of data, Bubble sort is based on the following For each pass (I) = 1 to N-1 For J = 1 to N-I if A[J] > A[J+1] swap A[J] A[J+1] Illustration Unsorted Data: 23, 2, 14, 9, 8, 18 J123456runtimeAlgorithm A[J]232149818 Pass 12149818235 Pass 229814184 Pass 3289143 Pass 4 Pass52 28 892 1Total = 15 Bubble Sort Function void BubbleSort(Data A[], int N) { int i, j; for(i = 1; i <= n-1;="" i++)="" {="" for(j="1;"><= n-i;="" j++)="" if(a[j]="">A[j+1])swap(A[j], A[j+1]); } } HOMEWORK 2: CS 425 (THEORY OF ALGORITHMS) Due date: Wednesday, 09/16/2020 1. Illustrate Merge Sort using the following data, also compute the runtime. 34, 3, 14, 12, 7, 25, 11, 0 2. Explain the Partition algorithm of Quick sort using the following data. 34, 3, 14, 12, 7, 2, 11, 10 3. Compute runtime for each of the following cases (Use relevant formula) a) 1024 random data using Quicksort b) 500 data given in reverse order using Insertion sort algorithm c) 512 data given in any order using Merge Sort d) 500 data given in any order using Selection sort. e) 500 data given in any order using Bubble sort. 4. Give the array position after each pass, using Bubble sort. Original Data: 34, 3, 12, 70, 0, 15 5. Illustrate Selection sort using the following data. 71, 9, 40, 0, 49, 23 Also determine the runtime at each step, and compute the total runtime,