Quick synopsis: Program sorts array the user inputs.

IE enter 5,6,78,4,2 and it will sort it in order. Through various algorithms. This works great with quick small lists, but for some reason with one large number or longer lists the program will crash.

Here are the files if you would like to download and compile, just 3 quick ones.

I will also post the full code here.. Thank You for any help.

http://cl.ly/0X231N0Q1I0o2S0l1q0j <-------- to download the three files and run if you would like

MAIN.cpp

//Program By Ryan Brown 83211417
//Necessary libraries needed to run the program
#include <cmath>
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include "Sorting.h"
#include <string.h>
#include <iostream>

using namespace std;


    //Function used to calculate the run time of each sorting algorithm
    long diff_in_micros(timeval finish, timeval start)
    {
        long sec = (finish.tv_sec - start.tv_sec) * 1000;
        long us = (finish.tv_usec - start.tv_usec);
        return sec + us;
        cout << sec + us;
    }

    int main(int argc, char * argv[])

{

    //Pretty Stuff
    cout << "Welcome To The Sorter! V 1.0..." << endl << endl;
    cout << "----------------------------------------------------" << endl;
    cout << "|  Please Enter Numbers That You Would Like Sorted |" << endl;
    cout << "|  Enter Any Letter To Exit Sequence               |" << endl;
    cout << "----------------------------------------------------" << endl;

    //Declare timeval integers, timeval comes from the library sys/time.h
    timeval start;
    timeval finish;
    Sorting derp;

    //Setting up the input and taking user response
    int x = 0;
    int Myarray[x];
    int copied[x];
    char holder[128] = {0};
    while(derp.isnumber(holder) == true)
    {
        cin.getline(holder,256);
        if(derp.isnumber(holder))
        {
            int c = atoi(holder);
            Myarray[x] = c;
            x = x + 1;
            derp.print_array(Myarray,x);
        }

    }
    //Displays after a user inputs a character other than a number
    cout << "----------------------------------" << endl;
    cout << "| Breaking from numerical input  |" << endl;
    cout << "----------------------------------" << endl;

    //Selection sort setup, copy the array, run timing on sort, output time and print the array
    derp.copy_array(Myarray,copied,x);
    gettimeofday(&start, NULL);
    derp.selection_sort(copied,x);
    gettimeofday(&finish, NULL);
    cout << "Time (us): " << diff_in_micros(finish, start) << "n";
    derp.print_array(copied,x);

    //Copy array, display the array after binary insertion sort is complete
    derp.copy_array(Myarray,copied,x);
    gettimeofday(&start, NULL);
    derp.binary_insertion_sort(copied,x);
    gettimeofday(&finish, NULL);
    cout << "Time (us): " << diff_in_micros(finish, start) << "n";
    derp.print_array(copied,x);

    //Copy array and display the list after the linear insertion is complete
    derp.copy_array(Myarray, copied,x);
    gettimeofday(&start, NULL);
    derp.linear_insertion_sort(copied,x);
    gettimeofday(&finish, NULL);
    cout << "Time (us): " << diff_in_micros(finish, start) << "n";
    derp.print_array(copied,x);

    //Setup up for Merge sort, this copies the defualt array into the copy array, prints it after merge sort
    int mid = Myarray[(x-1) / 2];
    int first = Myarray[0];
    int last = Myarray[x-1];
    derp.copy_array(Myarray,copied,x);
    gettimeofday(&start, NULL);
    derp.merge_sort(Myarray,x,first,mid,last);
    gettimeofday(&finish, NULL);
    cout << "Time (us): " << diff_in_micros(finish, start) << "n";
    derp.print_array(copied,x);

    //Sets up the copied array, prints out the new array sort after quicksort has completed
    derp.copy_array(Myarray,copied,x);
    gettimeofday(&start, NULL);
    derp.quick_sort(Myarray,first,last);
    gettimeofday(&finish, NULL);
    cout << "Time (us): " << diff_in_micros(finish, start) << "n";
    derp.print_array(copied,x);
    return 0;
}

SORTING.CPP

    #include "Sorting.h"
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <sys/time.h>

    using namespace std;

    Sorting::Sorting()
    {
        //ctor
    }

    Sorting::~Sorting()
    {
        //dtor
    }

    void Sorting::print_array(const int array[], int size)
    {
        cout <<"The Array Contains : " << endl;
        cout << "{ ";
        for(int i = 0; i < size; i++)
        {
            cout << array[i] << " ";
        }
        cout << "}" << endl;
    }

    void Sorting::copy_array(const int initial[], int copied[], int x)
    {
        for(int i = 0; i < x; i++)
        {
            copied[i] = initial[i];
        }
    }

    void Sorting::selection_sort(int array[], int size)
    {
       for (int i = size - 1; i >= 1; i--)
        {
            int index = 0;
        for (int j = 1; j < i + 1; j++)
            {
                if(array[j] >= array[index])
                index = j;                           // 1 move
            }
        swap(array[index], array[i]);     // 3 moves
        } // end outer for
        cout << "After Selection Sort " << endl;
    }

    bool Sorting::isnumber(char *str)
    {
        for(int i = 0; str[i];i++)
        {
            if(!isdigit(str[i]))
            {
                return false;
            }
        }
        return true;
    }

    void Sorting::linear_insertion_sort(int array[], int n)
    {
        for(int i = 1; i < n; i++)
        {
        int next = array[i];
        int j = i; // insertion index
        while(j > 0 && array[j-1] > next)
            {
                array[j] = array[j-1]; // shift
                j = j-1;
            } // end inner for
        array[j] = next;
      } // end outer for
        cout << endl << endl;
        cout << "After Linear Insertion Sort " << endl;
    }



    void Sorting::binary_insertion_sort(int array[], int n)
    {
        Sorting derp;
        int i, m;
        int hi, lo, tmp;

        for (i = 1; i < n; i++) {
            lo = 0, hi = i;
            m = i / 2;

            do {
                if (array[i] > array[m]) {
                    lo = m + 1;
                }
                else if (array[i] < array[m]) {
                    hi = m;
                }
                else
                    break;

                m = lo + ((hi - lo) / 2);
            }
            while (lo < hi);

            if (m < i) {
                tmp = array[i];
                memmove (array + m + 1, array + m, sizeof (int) * (i - m));
                array[m] = tmp;
            }
        }
        cout << endl << endl;
        cout << "After Binary Insertion Sort " << endl;
    }

    void Sorting::merge_sort(int theArray[],int n,int first, int mid, int last)
    {
        int tmpArray[n];
        int first1 = first, first2 = mid + 1, i = first1;
        for(; first1 <= mid && first2 <= last; i++)
         {
        if(theArray[first1] < theArray[first2])
        tmpArray[i] = theArray[first1++];
        else
        tmpArray[i] = theArray[first2++];
        }
       for(; first1 <= mid; i++, first1++)   // copy remaining from ?rst half
          tmpArray[i] = theArray[first1];
       for(; first2 <= last; i++, first2++)  // copy remaining from sec. half
          tmpArray[i] = theArray[first2];
       for(int j = first; j <= last; j++)   // copy tmpArray to the array
          theArray[j] = tmpArray[j];
          cout << endl << endl;
          cout << "After Merge Sort " << endl;
    }


    int Sorting::quick_sort(int array[],int first, int last)
    {
        int pivot = array[first];        // pivot value
        int lastP1 = first;  // last index of first partition
        for(int i = first + 1;i <= last; i++)
        {
            if(array[i] < pivot)
            {
                lastP1++;
                int z = array[i];
                array[i] = array[lastP1];
                array[lastP1] = z;
            }
        }

        int r = array[first];
        array[first] = array[lastP1];
        array[lastP1] = r;
        cout << endl << endl;
        cout << "After Quick Sort " << endl;
        return lastP1;
    }

Recommended Answers

All 3 Replies

alright do you know where the error takes place?

Maby narrow it does to a function?

Everything looks pretty well done allthough it feels slightly unneccessary here and there :?

Regardless, you deserve some credit for at least trying...

now, first thing... as a programmer, a sad truth about life is that you are going to spend a LOT of time searching for and resolving errors, a quick tip to assist, enter debug comments... what I mean is while testing enter an output message at the start and end of each major functionality with the possibility of crashing, even at the start and end of every method if you want to

these you can later remove (even add in an if statement which references a singal variable that sets your application to debug mode)

Im sorry but I really dont have the time to compile your code and alter and search and try to replicate the error... find it, show it, and lets see what we can do

I just ran it and the program gets to linear insertion.. which means that merge is the problem.. or something about it. The error I get is a Windows error... like the porgram is not responding do you want to close. Not a compiler error.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.