Sorting Method

Hi everyone, my team and I are trying to write a program together which will generate random numbers and display the time taken for each sorting method. We are trying to combine our 3 programs into one since each of us has written a function. I just wanted to know if we were at all close to completion. We just wanted to make sure that the functions we wrote were correct since this is the part we are concentrating on right now. We do not need answers....just a little guidance to make sure that we are on the right track.

Output should resemble the following

Unsorted array:
5 1 6 2

Sorted array (Selection Sort):
1 2 5 6

""
each sorting method
""



Size Time(selection) Time(Heap) "" "" ""
-----------------------------
2000 0 0
4000 0 0
6000 0 0
8000 0 0
10000 0 0
12000 0 0
14000 0 0
16000 0 0
18000 0 0
20000 0 0
22000 0 0
24000 1 0
26000 1 0
28000 1 0
30000 1 0




Thanks in advance for any help that is posted

Code:

---

# include <iostream.h>
# include <conio.h>
# include <iomanip.h>
# include <time.h>
# include <stdlib.h>
# include <fstream.h>
# define Size 30000 //need to remove the definition

void getRandomNumber(int[],int);
void MergeSort(int[], int, int);
void merge(int[], int, int);
void SelectionSort(int[], int); //Remove this
void QuickSort (int[],int);
void HeapSort(int[],int);
void InsertionSort (int[],int); //or remove this


void PrintArray(int[],int);

ofstream outf("c:\\Output.txt",ios::app); //Prints output to the c: drive
main() //Main of the Program
{
int Array[Size];
clock_t start, end;

getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
MergeSort(Array,20,20);
cout<<"Sorted array (Merge Sort): \n";
outf<<"Sorted array (Merge Sort):"<<endl; PrintArray(Array,20);

getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
SelectionSort(Array,20);
cout<<"Sorted array (Selection Sort): \n";
outf<<"Sorted array (Selection Sort):"<<endl; PrintArray(Array,20);

getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
QuickSort(Array,20);
cout<<"Sorted array (Quick Sort): \n";
outf<<"Sorted array (Quick Sort):"<<endl; PrintArray(Array,20);



getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
HeapSort(Array,20);
cout<<"Sorted array (Heap Sort): \n";
outf<<"Sorted array (Heap Sort):"<<endl; PrintArray(Array,20);

getRandomNumber(Array,20);
cout<<"Unsorted array: \n";
outf<<"Unsorted array:"<<endl;
PrintArray(Array,20);
InsertionSort(Array,20);
cout<<"Sorted array (Insertion Sort): \n";
outf<<"Sorted array (Insertion Sort):"<<endl; PrintArray(Array,20);


//**************************
cout<<"Size\tTime(selection)\tTime(Heap)\n";
cout<<"-----------------------------\n";
outf<<"Size\tTime(selection)\tTime(Heap)\n";
outf<<"-----------------------------\n";
//**************Major Editing

for(int i=2000; i<=Size; i=i+2000)
{
  getRandomNumber(Array,i);
  start = clock();
  SelectionSort(Array,i);
  end = clock();

  cout<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
  outf<<i<<"\t\t"<<(end-start)/CLK_TCK<<"\t";
  getRandomNumber(Array,i);
  start = clock();
  HeapSort(Array,i);
  end = clock();
  cout<<(end-start)/CLK_TCK<<endl;
  outf<<(end-start)/CLK_TCK<<endl;
}
getch();
return 0;
}

void getRandomNumber(int array[],int size) { srand(time(0)); for(int i=0; i<size; i++)
  array[i]=rand()%201-100;
}

void PrintArray(int array[],int size)
{
for(int i=0; i<size; i++)
{
  cout<<setw(4)<<array[i]<<((i+1)%10?" ":"\n");
  outf<<setw(4)<<array[i]<<((i+1)%10?" ":"\n"); } cout<<endl; }
//*****************************************************************************
void MergeSort(int 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);
        }
}


void merge(int a[],int left, int right)
{
        int        size=right-left+1,
                mid=(left+right)/2;
        int y, put;
        int *b=new int[size];
        int count=0;
        for(int x=left;x<=mid;x++,count++)
        {
                b[count]=a[x];
        }
        for(x=right;x>=mid+1;x--,count++)
        {
                b[count]=a[x];
        }
        for(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;
}



//*********************************************************************************
void SelectionSort(int b[], int s)
{
  int k,x,i,j;
 for(i = 0; i < s-1 ; i++)
  {
    k = i;
      x = b[i];
      for(j = i+1; j< s; j++)
      if(b[j] < x)
        {
          k=j;
            x=b[j];
        }
      b[k]=b[i];
      b[i]=x;
  }
}
//******************************************************************************************

void choosePivot(int c[], int first, int last){
{
        int  pivotIndex;
        int mid = (first + last) / 2;

    if( c[ first ] <= c[ mid ] )
    {    if( c[ mid ] <= c[ last ] )  pivotIndex = mid;
          else  pivotIndex = ( c[ first ] <= c[ last ] ? last : first );
    }
    else if( c[ last ] <= c[ mid ] )  pivotIndex = mid;
    else  pivotIndex = ( c[ first ] <= c[ last ] ? first : last );
      swap( c[ first ],  c[ pivotIndex ] );
}
}

void partition(int c[], int first, int last, int& pivotIndex)
{
                choosePivot(c, first, last);
                int pivot = c[first];

                int lastS1 = first;
                int firstUnknown = first + 1;

                for (; firstUnknown<=last;++firstUnknown)
                {
                        if (c[firstUnknown]<pivot)
                        {
                                ++lastS1;
                                swap(c[firstUnknown],c[lastS1]);
                        }
                }
                swap(c[first], c[lastS1]);
                pivotIndex = lastS1;
}

void quicksort(int c[], int first, int last)
{
        int pivotIndex;

        if (first<last)
        {
                partition(c, first, last, pivotIndex);

                quicksort(c, first, pivotIndex-1);
                quicksort(c, pivotIndex+1, last);
        }
}

//*******************************************************************************
void HeapSwap(int d[], int l, int k)
{
 int temp;
 temp = d[l];
 d[l] = d[k];
 d[k] = temp;
}

void Shift(int d[], int first, int last) {  int largest = 2*first+1;
  while(largest <= last)
 {
  if(largest < last)
  if(d[largest] < d[largest+1])
    largest++;

  if(d[first] < d[largest])
  {
  HeapSwap(d, first,largest);
  first = largest;
  largest = 2*first+1;
      }
  else
  largest = last+1;
  }
}

void HeapSort(int d[], int size)
{
 register int i;
 for(i = size/2-1; i >=0; --i)
    Shift(d,i,size-1);
  for(i = size-1; i > 1; --i)
 {
  HeapSwap(d, 0, i);
  Shift(d,0,i-1);
  }
 if(d[0] > d[1])
  HeapSwap(d, 0, 1);
}
//**************************************************************************
void insertionSort(int e[], int n)
{
        for (int unsorted=1;unsorted<n;++unsorted)
        {
                int nextItem = e[unsorted];
                int loc = unsorted;

                for (;(loc>0) && (e[loc-1]>nextItem);--loc)
                        e[loc] = e[loc-1];

                e[loc] = nextItem;
        }
}

---

not to pounce on ya, but that merge sort function looks very very much, infact exactly like one ive seen on a tutorial: http://www.halcy0n.com/docs/doc.php?id=2 looks like you or your partners just copyed the template and changed it to a function, try coming up with it on your own its much more rewarding.

on a side note, you might want to stick with new headers and not use old ones, for example <iostream> instead and use: using namespace std; also you can change the define to a constant integer,

Code:

---

const int SIZE = 30000;

---