Write an industrial-strength quicksort function with the followingenhancements:

Question

Write an industrial-strength quicksort function with the followingenhancements:
After sorting the first, middle, and last elements (usingbubblesort), use the median as a pivot, instead of swapping themedian with the first element. (Save this value in Pivot_val).Because the first and last elements are in the correct partitions,it is not necessary to test them before advancing up and down. Thisis also the case after each exchange, so increment up and decrementdown at the beginning of the do…while loop. Also, it is notnecessary to test whether up is less than last before incrementingup, because the condition pivot_val < *up is false when upequals last-1 (the median must be >= the last element in thearray).

note
i all ready did the bubblesort part all i need help with thepartitions part this is what i have so far

#ifndef QUICKSORT3_H_
#define QUICKSORT3_H_
#include <algorithm>
#include <functional>
#include <iterator>
#include "BubbleSort3.h"
#include "InsertionSort3.h"


namespace Meep {


template<typename RI>
void quick_sort3(RI first, RI last) {
/** Quicksort on arrays with more than 20 elements
    Params:
    first: An iterator that references
           thefirst element in the sequence to be sorted
    last: An iterator that references
           1 pastthe end of the sequence
**/
     int length;           // finding the length
    length = last-first;
    RI up;
    up = first+1;
    RI down;
    down = last-2;
   

    if (length <= 20)       // if length is <= 20 call insertionsort
    insertion_sort3(first, last);
    else {               // length > 20 useboubblesort
    Bubble_sort3(first, first+(length/2), last);
    cout<<"Begin: ";
         for(RI x = first;x != last; ++x)
           cout<< *x <<" ";
    cout<<endl<<endl;
    partition(first, last, up, down);
    }
   
    cout<<" END ";
         for(RI x = first;x != last; ++x)
          cout<<*x <<" ";
        cout<<endl;

} // End of quick sort

template<typename RI>
void partition(RI first, RI last, RI& up, RI& down){
    RI pivot = (up+((down-up)/2));
    RI i = up;
    RI j = down;
while(i <= j){
    while(*(i) < *(pivot))
        i++;
    while(*(j) > *(pivot))
        j--;
    if(i <= j){
std::swap(*(i), *(j));
        i++;
        j--;

    }
    };


         for(RI x = first;x != last; ++x)
           cout<< *x <<" ";
        cout<<endl;

        while(i <= j);
               if(up < j)
                   partition(first, last,up, j);
               if(i < down)
                    partition(first, last,i, down);

}; // End Partition
} // End namespace Meep

#endif

Explanation / Answer

Dear, /*C++ program to sort given n elements usingquicksort */

#include<iostream.h>
#include<conio.h>
void quick_sort(int a[],int,int);
void main(void)
{
   clrscr();
   int n,l,r;
   int a[20];
   cout<<"Please enter n value"<<endl;
   cin>>n;
   l=1;r=n;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   quick_sort(a,l,r);
   cout<<"Sorted Array is"<<endl;
   for(int j=1;j<=n;j++)
   cout<<a[j]<<" ";
}

void quick_sort(int a[],int m,int n)
{
   int k,temp,i,j;
   if(m<n)
   {
      k=a[m];
      i=m;j=n+1;
    do
    {
      do {
      i++;
      }while(a[i]<k);
      do
      {
      j--;
      }while(a[j]>k);
      if(i<j)
      {
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      }
    }while(i<=j);
      temp=a[m];
      a[m]=a[j];
      a[j]=temp;
      quick_sort(a,m,j-1);
      quick_sort(a,j+1,n);
   }//if
}//function

I hope this will helpful foryou......... /*C++ program to sort given n elements usingquicksort */

#include<iostream.h>
#include<conio.h>
void quick_sort(int a[],int,int);
void main(void)
{
   clrscr();
   int n,l,r;
   int a[20];
   cout<<"Please enter n value"<<endl;
   cin>>n;
   l=1;r=n;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   quick_sort(a,l,r);
   cout<<"Sorted Array is"<<endl;
   for(int j=1;j<=n;j++)
   cout<<a[j]<<" ";
}

void quick_sort(int a[],int m,int n)
{
   int k,temp,i,j;
   if(m<n)
   {
      k=a[m];
      i=m;j=n+1;
    do
    {
      do {
      i++;
      }while(a[i]<k);
      do
      {
      j--;
      }while(a[j]>k);
      if(i<j)
      {
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      }
    }while(i<=j);
      temp=a[m];
      a[m]=a[j];
      a[j]=temp;
      quick_sort(a,m,j-1);
      quick_sort(a,j+1,n);
   }//if
}//function

I hope this will helpful foryou.........

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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