Insertion Sort and Comb Sort

[NerdPC]

I have googled this and I see how to do the clock function with insertion and I was pretty sure I implemented it right but the insertion sort never shows any time. I am not sure if I am not waiting long enough but I have had the program up for atleast 20 minutes and stil nothing has happened. I do not know if it is my computer in anyway. I just wanted to see if anyone saw an error that I am overlooking.

#include <iostream>
#include <fstream>
#include <ctime>
#include <math.h>


using namespace std;

//array size
const int CAPACITY = 500000;

void ReadFile(int*);

void InsertionSort(int*);

void CombSort(int*, size_t size);

int main()
{
    //Variables

    int* info = NULL;
    info = new int[CAPACITY];

    int* temp = NULL;
    temp = new int[CAPACITY];

    int t = 0;
    int z;
    int k;
    clock_t end;
    clock_t start;

    double times = 0;


                        for(z = 0; z < 1; z++)
                            {
                                ReadFile(info);

                                start = clock();
                                cout << "Insertion Sort: ";
                                InsertionSort(int* info);
                                end = clock();
                                times = ((end-start)/(double)CLOCKS_PER_SEC)
                            }


                            cout << times << endl;
                            times=0;


                        }



                            for(z = 0; z < 1; z++)
                            {
                                ReadFile(info);
                                start = clock();
                                CombSort(info, (size_t)CAPACITY);
                                end = clock():
                                times = ((end-start)/(double)CLOCKS_PER_SEC)
                            }

                            cout << "Comb Sort: ";
                            cout << times << endl;
                            times = 0;

                            break;
            }
        }
    return 0;
}

void ReadFile(int* info)
{
    //Read in the file
    fstream datafile("numbers.txt", ios::in |ios::out);

    //Test for file open
    if(!datafile.is_open()) 
        {
            cout<<"Error opening file"<<endl;
            system("pause");
            exit(-1);
        }

    //places data from the file into string array
    for(int i = 0; !datafile.eof(); i++)
        {
            datafile >> info[i];
        }

}

void InsertionSort(int* info)
{
    //variables
    int t, z;
    int temp;

    //cycles through the array
      for (t = 1; t < CAPACITY; t++) 
      {


            //sets j to current element in the array, i.
            z = t;

            //cycles the element down as long as the previous
            //element is bigger
            while( (z > 0) && (info[z] < info[z - 1] )) 
            {

                //stores current element
                  temp = info[z];
                //places previous element into current element spot
                  info[z] = info[z - 1];
                //places previous element as temp (the old current elemnt)
                  info[z - 1] = temp;
                //moves z down
                  z--;

            }
      }
}

void CombSort(int* info, size_t size)
{
    //variables
    size_t Gap = size;
    bool swap_b = false;


    while ((Gap > 1) || swap_b) 
    {

    //calculates the gaps used for the sort
      if (Gap > 1) 
        {
          Gap = (size_t)((double)Gap / 1.5); //
        }

      //keeps cycles from ending prematurely
        swap_bool = false;


        for (size_t t = 0; Gap + t < size; t++) 
        {
            //determiens if the current element is bigger than the 
            //element located by the gap
            if (info[t] - info[t + Gap] > 0) 
            {
                //if so, it swaps the elements and sets swap_b
                //to true
                int swapval = info[t];
                info[t] = info[t + Gap];
                info[t + Gap] = swapval;
                swap_bl = true;
            }
        }
    }
}

[BobS0327]

Well, your code might actually run if you fixed all the syntax errors in the above code.

[rubberman]

Also, the way you are reading the file, you are reading each word separately. Is that what you want to do? What about duplicates? Anyway, I implemented an insertion sort for C++ years ago (about 20 years ago) that used a modified bsearch() routine to find the insertion point in the array (these days you should use a vector), pushed the values from that position to the end down one in the array, and set the insertion point element to the new value. Some optimizations included head and tail insertions, which sped up inserting sorted data tremendously. Since this is an in-memory operation, you may need to limit the size (we handled over 100K items very efficiently, with key sizes of 40-50 bytes).

Other issues to decide. When you need to grow the array, don't grow by just one element - waaay too slow! So, have a settable size increment member (or class static) variable. Also, you need to decide if you want duplicates!