For this part of the assignment you will write a number of C++ template function

Question

For this part of the assignment you will write a number of C++ template functions to sort a list of items using the recursive quick sort algorithm.

Program

Add the following template functions to your sorts.h file. The header file should contain both the prototypes and definitions for these functions.

template <class T>
bool lessThan(const T& item1, const T& item2)

This function should return true if item1 is less than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

template <class T>
bool greaterThan(const T& item1, const T& item2)

This function should return true if item1 is greater than item2 and false if not. You may assume that the data type T can be compared using the standard relational operators.

Implement the following template functions in a header file called quicksort.h. This header file should have header guards (as usual) and should contain both the prototypes and definitions for the functions.

template <class T>
void quickSort(vector<T>& set, bool (*compare)(const T&, const T&))

This function should sort the items in the vector set using the quick sort algorithm. The first argument to this function is a reference to a vector object containing the list of items to sort. The second argument is a pointer to a comparison function that can be used to compare two items of the template type.

This function should call the recursive quick sort function, passing it the vector, the subscript of the first vector element (which is 0), the subscript of the last vector element (which is set.size() - 1), and the pointer to the comparison function (compare), e.g.:

template <class T>
void quickSort(vector<T>& set, int start, int end, bool (*compare)(const T&, const T&))

This function performs the recursive calls to implement the quick sort algorithm. The logic is:

template <class T>
int partition(vector<T>& set, int start, int end, bool (*compare)(const T&, const T&))

This function selects a pivot element and then partitions the vector around the pivot. The logic is:

Explanation / Answer

*The following C++ Program code performs the Quick Sorting Algorithm on an array which is being entered by the user. The function part() is user to partition the array as per the pivot value & function quick() performs the Quick Sort. The user is asked to enter the elements, which is then stored in array & displayed. Program performs quick sorting displays the sorted result.*/

#include<iostream>
#include<conio.h>
using namespace std;

//Function for partitioning array
int part(int low,int high,int *a)
{
     int i,h=high,l=low,p,t;  //p==pivot
     p=a[low];
     while(low<high)
     {
                    while(a[l]<p)
                    {
                                   l++;
                    }
                    while(a[h]>p)
                    {
                                   h--;
                    }
                    if(l<h)
                    {
                                t=a[l];
                                a[l]=a[h];
                                a[h]=t;
                    }
                    else
                    {
                        t=p;
                        p=a[l];
                        a[l]=t;
                        break;
                    }
     }
     return h;    
}

void quick(int l,int h,int *a)
{
int index,i;
if(l<h)
{
          index=part(l,h,a);
          quick(l,index-1,a);
          quick(index+1,h,a);
}
}

int main()
{
      int a[100],n,l,h,i;
      cout<<"Enter number of elements:";
      cin>>n;
      cout<<"Enter the elements (Use Space As A Separator):";
      for(i=0;i<n;i++)
      cin>>a[i];
      cout<<" Initial Array: ";
      for(i=0;i<n;i++)
      {
                      cout<<a[i]<<" ";
      }   
      h=n-1;
      l=0;
      quick(l,h,a);
      cout<<" After Sorting: ";
      for(i=0;i<n;i++)
      {
                cout<<a[i]<<" ";
      }
      getch();
      return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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