creating a template for quick sort algorithm

[neekforjesusmir]

Hello, I am trying to create a template for the quicksort algorithm so I can use it for any data type(such as int). Whenever I run it I get these errors on line 26:undefined reference to `int quickSort<int>(int*, int, int)
error: ld returned 1 exit status. Here's is my code:




#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]. *
//************************************************
template<class 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. *
//***********************************************************
template<class 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;
}

[Moschops]

Your quicksort function returns nothing, but it declares that it returns T. You've screwed up return types in three places.

T quickSort(T [], int, int); should be
void quickSort(T [], int, int);

template<class T> quickSort(T arr[], int start, int end) should be
template<class T> void quickSort(T arr[], int start, int end)

template<class T> partition(T arr[], int start, int end) should be
template<class T> T partition(T arr[], int start, int end)

[neekforjesusmir]

Wow, I can't believe I didn't see that. I understand what I did wrong now. That makes total sense. Thank you.