Sort an array of 10,000 elements using quicksort as follows: a. Sort the array u
ID: 3689242 • Letter: S
Question
Sort an array of 10,000 elements using quicksort as follows:
a. Sort the array using pivot as the middle element of the array.
b. Sort the array using pivot as the median of the first, last, and middle
elements of the array.
c. Sort the array using pivot as the middle element of the array. However,
when the size of any sublist reduces to less than 20, sort the sublist using
insertion sort.
d. Sort the array using pivot as the median of the first, last, and middle
elements of the array. When the size of any sublist reduces to less than
20, sort the sublist using insertion sort.
e. Calculate and print the CPU time for each of the preceding four steps.
Explanation / Answer
a)we can use following algorithm
A = array of elements
p = starting index of array
r = end index of array
Quicksort(A,p,r)
{
if p < r
then q <- (p+r)/2
Quicksort(A,p,q-1)
Quicksort(A,q+1,r)
}
b)we can use the following algorithm
A = array of elements
p = starting index of array
r = end index of array
Quicksort(A,p,r)
{
if p < r
then q <- median(A,p,r)
Quicksort(A,p,q-1)
Quicksort(A,q+1,r)
}
median(A,p,r)
{
if A[p] > A[(p+r)/2] exchange A[p] <-> A[(p+r)/2]
if A[p] > A[r] exchange A[p] <-> A[r]
if A[(p+r)/2] > A[r] exchange A[(p+r)/2] <-> A[r]
for i <- 1 to r
do if A[i] == A[(p+r)/2]
then return i
}
c)we can use the following algorithm
A = array of elements
p = starting index of array
r = end index of array
Quicksort(A,p,r)
{
if p < r
then q <- (p+r)/2
if q-p >=20
then Quicksort(A,p,q-1)
else insertionsort(A,p,q-1)
if q-p >=20
then Quicksort(A,q+1,r)
else insertionsort(A,q+1,r)
}
insertionsort(A,p,r)
{
for j <- 2 to (r-p+1)
do key <- A[j]
insert A[j] into the sorted sequence A[1.....j-1]
i <- j-1
while i>0 and A[i] > key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key
}
d)we can use the following algorithm
A = array of elements
p = starting index of array
r = end index of array
Quicksort(A,p,r)
{
if p < r
then q <- median(A,p,r)
if q-p >=20
then Quicksort(A,p,q-1)
else insertionsort(A,p,q-1)
if q-p >=20
then Quicksort(A,q+1,r)
else insertionsort(A,q+1,r)
}
median(A,p,r)
{
if A[p] > A[(p+r)/2] exchange A[p] <-> A[(p+r)/2]
if A[p] > A[r] exchange A[p] <-> A[r]
if A[(p+r)/2] > A[r] exchange A[(p+r)/2] <-> A[r]
for i <- 1 to r
do if A[i] == A[(p+r)/2]
then return i
}
insertionsort(A,p,r)
{
for j <- 2 to (r-p+1)
do key <- A[j]
insert A[j] into the sorted sequence A[1.....j-1]
i <- j-1
while i>0 and A[i] > key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.