I have been writing some quicksort code and testing it on integers and all seems to be going well. Now I'm trying to use my code to read in words from a file and quicksort them. I tried using my quicksort on an array of strings but that did not work and I don't really know where to start to get it to work for strings. The following is my code so far.
#include <iostream> // For NULL
#include "time.h"
using namespace std;
int pickPivot = 0;
int comparisons = 0;
//quicksort
template< typename Type >
void quickSort1( Type* array, int low, int high)
{
int pivotPosition = 0;
int length = high;
if (length < 11)
{
insertionSort (array, length);
}
else
{
if (low < high)
{
switch (pickPivot)
{
case 1:
pivotPosition = median(array, low, high);
break;
case 2:
pivotPosition = random(array, low, high);
break;
case 3:
pivotPosition =partition(array, low, high);
break;
case 4:
pivotPosition = medianOfnine(array, low, high);
break;
default:
break;
}
quickSort1(array, low, pivotPosition-1);
quickSort1(array, pivotPosition+1, high);
}
}
}
//insertion sort
template< typename Type >
void insertionSort( Type* array, int length)
{
for (int i = 1; i<length; i++)
if (array[i]<array[i - 1])
{
Type temp = array[i];
int location = i;
do
{
array[location] = array[location - 1];
location--;
}
while (location > 0 && array[location - 1] > temp);
array[location] = temp;
}
}
//medain as pivot
template< typename Type >
const Type &median( Type* array, int low, int high )
{
int middle = (low+high)/2;
if ( array[low] > array[middle] )
swap( array[middle], array[low] );
if ( array[low] > array[high] )
swap( array[low], array[high] );
if ( array[middle] > array[high] )
swap( array[high], array[middle] );
swap(array[middle], array[low]);
return partition(array, low, high);
}
//random pivot
template< typename Type >
const Type &random (Type* array, int low, int high)
{
srand(time(NULL));
array[low] = low+(rand()%(high-low));
return partition (array, low, high);
}
//median of nine
template< typename Type >
const Type &medianOfnine (Type* array, int low, int high)
{
high = low + 9;
return median(array, low, high);
}
//partition
//also first elm as pivot
template< typename Type >
const Type &partition( Type* array, int low, int high )
{
int left, right;
Type pivot;
left = low;
right = high;
pivot = array[low];
while ( left < right )
{
while ( array > pivot )
right--;
comparisons++;
while ( (left < right) && (array <= pivot) )
left++;
comparisons++;
if ( left < right )
swap(array, array );
comparisons++;
}
array[low] = array;
array = pivot;
return right;
}This is what I tried unsuccessfully in main:
#include "Quicksort.h"
#include <string>
#include <fstream>
using namespace std;
int main()
{
string array[10];
ifstream fin;
fin.open("sample.txt");
if (!fin)
{
cerr<<"File could not be opened"<<endl;
exit(1);
}
for (int i = 0; !fin.eof(); i++)
{
fin>>array[i];
}
for(int i=0; i<10; i++)
{
cout <<array[i] <<endl;
}
pickPivot = 1;
quickSort1(array, 1, 10);
}Does anyone have any suggestions?
