Quick Sort With Template

[pepstein]

In this program I am attempting to create the quicksort algorithm using a template so that I can sort both ints and whatever I please. Here is the current code:

  // This program demonstrates the Quicksort algorithm.
#include <iostream>
#include <algorithm>            //needed for swap() function
using namespace std;

// Function prototypes
template <class T>
T quickSort(T [], int, int);

template <class T>
T partition(T [], int, int);

int main()
{
    // Array to be sorted.
    const int SIZE = 10;
    int array[SIZE] = {100, 35, 7, 21, 89, 10, 148, 983, 33, 29};

    // Echo the array to be sorted.
    for (int k = 0; k < SIZE; k++)
        cout << array[k] << " ";
    cout << endl;

    // Sort the array using Quicksort.
    quickSort(array, 0, SIZE-1);

    // Print the sorted array.
    for (int k = 0; k < SIZE; k++)
        cout << array[k] << " ";
    cout << endl;

    return 0;
}

//************************************************
// quickSort() uses the QuickSort algorithm to   *
// sort arr from arr[start] through arr[end].    *
//************************************************
T quickSort(T arr[], int start, int end)
{
    if (start < end)        //test for base case start == end
    {
        // Partition the array and get the pivot point.
        int p = partition(arr, start, end);

        // Sort the portion before the pivot point.
        quickSort(arr, start, p - 1);

        // Sort the portion after the pivot point.
        quickSort(arr, p + 1, end);
	}
	return;                 //base case
}

//***********************************************************
// partition() rearranges the entries in the array arr from *
// start to end so all values greater than or equal to the  *
// pivot are on the right of the pivot and all values less  *
// than are on the left of the pivot.                       *
//***********************************************************
T partition(T arr[], int start, int end)
{
    // The pivot element is taken to be the element at
    // the start of the subrange to be partitioned.
    T pivotValue = arr[start];
    T pivotPosition = start;

    // Rearrange the rest of the array elements to
    // partition the subrange from start to end.
    for (int pos = start + 1; pos <= end; pos++)
    {
        if (arr[pos] < pivotValue)
        {
            // arr[pos] is the "current" item.
            // Swap the current item with the item to the
            // right of the pivot element.
            swap(arr[pivotPosition + 1], arr[pos]);
            // Swap the current item with the pivot element.
            swap(arr[pivotPosition], arr[pivotPosition + 1]);
            // Adjust the pivot position so it stays with the
            // pivot element.
            pivotPosition ++;
        }
	}
    return pivotPosition;
}

In lines '39' and '61' it's giving me the error, "'T' Does not name a type". How do I define these correctly? Thanks.

[booradley60]

You should put template <class T> before the definitions, similar to how you've done the declarations. However, I don't know if returning T from either of those functions is actually what you want to do. You return T from partition, but shouldn't this always be an int in your implementation? You're returning an array position, not an actual object being kept in the array. And the quicksort function itself doesn't return anything. You could have void there instead of T.

[pepstein]

wow such a simple solution, all I needed was to put the template <class T> in front of both and it worked. I had only switched around the return types of the functions since I was trying different things to make it work. You fixed it very simply, thanks for the help.