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);

}

}