A 16 element array stores the integers 81, 16, 2, 89, 54, 23, 76, 25, 37, 107, 1

Question

A 16 element array stores the integers 81, 16, 2, 89, 54, 23, 76, 25, 37, 107, 1, 74, 45, 16, 31, and 58 in elements 0 through 15, respectively. They are to be sorted using the Quicksort.

a. How many passes will be performed to complete the sort?

b. Show the contents of the array at the beginning of the sort and after the first two passes.

c. How many partitions will there be after pass three?

d. Give the total number of comparisons and swaps performed by the algorithm using the formulas presented in Table 8.6.

Table 8.6 Performance of the Quicksort Algorithm Memory Overhead Range Bytes Speed Range Effort Algorithm Binary Tree fast/slow Comments high 8n Fast for random data, slow for already sorted data (n+1)[log2(n + 1)-2]

Explanation / Answer

#include <iostream.h>
#include <conio.h>

void main()
{
    void srt(int[],int,int);
    int a[16]={81, 16, 2, 89, 54, 23, 76, 25, 37, 107, 1,

74, 45, 16, 31, 58};
   int count=16,n;
    clrscr();
   
    n=0;
    clrscr();
    srt(a,n,count-1);
    clrscr();
    cout<<" The Sorted order is : ";
    for (n=0;n<16;n++)
    {
       cout<<" position : "<<(n

+1)<<" "<<a[n]<<" ";
    }
    getch();
}

void srt(int k[16],int lb,int ub)
{
    int i,j,key,flag=0,temp;
    clrscr();
    if (lb<ub)
   {
        i=lb;
        j=ub+1;
        key=k[i];
        while(flag!=1)
       {
            i++;
            while(k[i]<key)
           {
                i++;
           }
            j--;
            while(k[j]>key)
           {
                j--;
           }
            if (i<j)
           {
                temp=k[i];
                k[i]=k[j];
                k[j]=temp;
           }
            else
           {
                flag=1;
                temp=k[lb];
                k[lb]=k[j];
                k[j]=temp;
           }
       }
        srt(k,lb,j-1);
        srt(k,j+1,ub);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.