1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
|
// Qsort.h file
#include <vector>
using namespace std;
// Quicksort class
template <typename T>
class Qsort
{
public:
// Constructor
Qsort();
Qsort(vector<T*> &vec, int from, int to);
// partition vector for quicksort
int partition(vector<T*> &vec, int from, int to);
// quicksort function
// int quicksort(vector<T*> &vec, int from, int to);
};
// Constructor
template <typename T>
Qsort<T>::Qsort()
{
//
}
// Partition
// ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
template <typename T>
int Qsort<T>::partition(vector<T*> &vec, int start, int end)
{
int pivot = vec[end];
int bottom = start-1;
int top = end;
bool continue = true;
while (continue)
{
while (continue)
{
bottom += 1;
if (bottom == top)
{
continue = false;
break;
}
if (vec[bottom] > pivot)
{
vec[top] = vec[bottom];
break;
}
}
while (continue)
{
top = top-1;
if (top == bottom)
{
continue = false;
break;
}
if (vec[top] < pivot)
{
vec[bottom] = vec[top];
break;
}
}
}
vec[top] = pivot;
return top;
}
template <typename T>
Qsort<T>::Qsort(vector<T*> &vec, int start, int end)
{
if (start < end)
{
int split = partition(vec, start, end);
Qsort(vec, start, split-1);
Qsort(vec, split+1, end);
}
}
|