Solved
Sorting, Integers/Int Strings
Posted on 2003-10-29
This is basically what im working with.
So far:
It takes a file name in from the command line.
Inserts it into an array.
Runs the array through various sorts.
End Result:
I'm wanting to be able to count the number of comparisons that take place in each sort function and output them to the user. Some functions I have tried to implement a comparison counter but I dont think im doing this right??
I also want to output the sorted array to a file. However im wanting to use the input filename + a suffix. Could this be done in a seperate output() function by passing the sorted array, I guess i dont know how to keep track of the input filename to use it in the output name??
I am planning on using integer data files but inserting them into an array once as integers and then a second time as integers as strings. Then performing sort on both, I guess this mean I need to change the sorting algorithms and use compare() where needed??
Here is what I have so far... any design tips, hints, points, anything would be appreciated. There is no specific question here, just a little collaboration on how I am doing so far. Thanks.
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
void compare(int a, int b) {
// will compare the integers here and return result
}
void compare(char* a, char* b) {
// will compare here also, except as integer strings
}
template <class T>
void InsertionSort(T A[], int size)
{
int compares = 0;
for(int j=1; j<size; j++)
{
T key = A[j];
int i = j - 1;
while ((i >= 0) && (A[i] > key))
{
A[i+1] = A[i];
i -= 1;
compares++;
}
A[i+1] = key;
}
}
template <class T>
void mergesort(T A[], int left, int right)
{
if(left<right)
{
int mid=(left + right)/2;
mergesort(A, left, mid);
mergesort(A, mid+1, right);
merge(A,left,right);
}
}
template <class T>
void merge(T A[],int left, int right)
{
int size=right-left+1,
mid=(left+right)/2;
T *b=new T[size];
int count=0;
for(int x=left;x<=mid;x++,count++)
{
b[count]=A[x];
}
for(int x=right;x>=mid+1;x--,count++)
{
b[count]=A[x];
}
for(int x=0,y=size-1,put=left;x<=y;put++)
{
if(b[x]<=b[y])
{
A[put]=b[x];
x++;
}
else
{
A[put]=b[y];
y--;
}
}
delete[] b;
}
template <class T>
void quicksort(T A[], int left, int right, int pivot)
{
int left_side, right_side;
left_side = left;
right_side = right;
do
{
while (A[right_side] > pivot)
right_side--;
while (A[left_side] < pivot)
left_side++;
if (left_side <= right_side)
{
swap(A[left_side], A[right_side]);
left_side++;
right_side--;
}
}
while (right_arrow >= left_arrow);
if (left < right_arrow)
quick_sort(A, left, right_arrow);
if (left_arrow < right)
quick_sort(A, left_arrow, right);
}
template <class T>
void Heapsort(T A[], int size)
{
BuildHeap(A, size);
for(i=size; i>1; i--)
{
int tmp = A[0];
A[0] = A[i-1];
A[i-1] = tmp;
size--;
Heapify(A, 1, size);
}
}
template <class T>
void BuildHeap(T A[], int size)
{
for(i=size/2; i>0; i--)
Heapify(A, i, size);
}
template <class T>
void Heapify(T A[], int i, int size)
{
int l = 2 * i;
int r = 2 * i + 1;
int largest = 0;
if(l <= heapsize && A[l-1] > A[i-1])
largest = l;
else
largest = i;
if(r <= heapsize && A[r-1] > A[largest-1])
largest = r;
if(largest != i)
{
int tmp = A[i-1];
A[i-1] = A[largest-1];
A[largest-1] = tmp;
Heapify(A, largest, heapsize);
}
}
int main(int argc, char* argv[])
{
ifstream input; // initializes input
int dataLength;
if(argc > 1)
{
string inData = argv[1];
input.open(inData);
if (!input) {
cerr << "Unable to open file." << endl;
exit (1);
}
input >> itemCount;
arraySize=itemCount-1;
int Array[arraySize];
int arrayCount = 0;
while(input >> x) {
Array[arrayCount] = x;
arrayCount++;
}
intertionsort(Array, arraySize);
mergesort(Array, 0, arraySize);
int lastPivot = Array[arraySize];
int middlePivot = Array[arraySize]/2;
quicksort(Array, 0, arraySize, lastPivot);
quicksort(Array, 0, arraySize, middlePivot);
heapsort(Array, arraySize);
}
}