Need help with a Design and Analysis of Algorithms question: Professor Larry sug
ID: 3881409 • Letter: N
Question
Need help with a Design and Analysis of Algorithms question:
Professor Larry suggests changing the quicksort algorithm to
quicksort(a,i,j) {
if (i < j) {
p = partition(a,i,j)
quicksort(a,i,p)
quicksort(a,p,j)
}
}
Does this algorithm correctly sort a? If so, what is its worst-case time?
Given an array a[i],...,a[j], with j-i >= 2, let k = (i+j)/2, and choose as the partition element the median among a[i],, a[k], a[j], (i.e., the value that would be in the middle if a[i], a[k], a[j] was sorted). Median-of-three partitioning uses as the partition element the median among a[i], a[k], a[j].
Extra Info:
The original quicksort algorithm is as follows:
Input Parameters: a, i, j
Output Parameter: a
quicksort(a,i,j) {
if (i < j) {
p = partition(a,i,j)
quicksort(a,i,p - 1)
quicksort(a,p + 1,j)
}
}
The partition algorithm used above is as follows:
Partition: This algorithm partitions the array a[i],...,a[j] by inserting val = a[i] at the index h where it would be if the array was sorted. When the algorithm concludes, values at indexes less than h are less than val, and values at indexes greater than h are greater than or equal to val. The algorithm returns index h.
Input Parameters: a, i, j
Output Parameters: a
partition(a,i,j) {
val = a[i]
h = i
for k = i + 1 to j
if (a[k] < val) {
h = h + 1
swap(a[h],a[k])
}
swap(a[i],a[h])
return h
}
Explanation / Answer
No, this will not correctly sort array a .
Let a be { 1 , 4 , 3, 2}
Now in the first iteration of quick sort i = 0 and j = 3,that is quicksort(a,0,3) is called.
Since (i<j)
p = 0;//returned by partition function partition(a,0,3)
quicksort(a,0,0);
quicksort(a,0,3); //Now this line keeps on iterating again and again infinitely
So this version of quicksort will fail for those type af array whose first elemenr is the minimum of all the elements present in the array.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.