sort an array of 10,000 elements using the quick sort algorithm as follows: a- s
ID: 3622741 • Letter: S
Question
sort an array of 10,000 elements using the quick sort algorithm as follows:a- sort the array using pivot as the middle element of the array.
b- Sort the using pivot as the median of the fist,last and middle elements of the array .
c- sort the array using pivot as the middle element of the array.However ,what the size of any sub list reduces to less than 20 ,sort the sublist using an insertion sort .
d-Sort the using pivot as the median of the fist,last and middle elements of the array .When the size of any sublist reduces to less than 20 ,sort the sublist using an insertion sort.
e-Calculate the print the CPU time for each of the preceding four steps .
To find the current CPU time , declare a variable say x, of the type clock_t . The statement x= clock(); store the current CPU time in x .You can check the current CPU time before and after a particular phase of the program , subtract the before time from the after time .Moreover you must include the header file ctime to use the date type clock_t and the function clock . use a random generator to initially fill the array.
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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.