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