Please help me...

[shiniboy]

You are supplied with a group of implemented sorting algorithms (posted file sortTest.cpp). You may not change the prototypes or any of the provided code.

You will add a main program to use the functions you are given. You will also add one additional function VerirySorted. This function will take the array, inArray[], and verify if all numbers in location 0 to L-1 in the array are in descending order. If the numbers in locations 0 to L-1 are all in descending order the function returns true, otherwise it returns false. The prototype of this function should be

bool VerifySorted( int inArray[ ], int L );

The prototypes of the functions you are give nn the provided file are
void InsertionSort(int inArray[], int N, int M, int L);
void DoubBubbleSort(int inArray[], int N, int M, int L);
void SelectionSort(int inArray[], int N, int M, int L);
void QuickSort(int inArray[], int N, int M );

For these functions L is the number of elements of the array to be sorted (inArray). The elements from element N (InArray[N] to element M (InArray[M]) will be sorted. Both N and M must be between 0 and L-1 inclusive. You are also provided with a function whose purpose is to check the internal consistantcy between the N,M, and L provided to any one of the above functions. This function is used by the sorting functons.
bool limitTest( int N, int M, int L);

When you call the sorting functions above to sort the first K elements in an array set N=0 and M=L-1 and L=K.
MAIN PROGRAM:

Write a program that generates a specified number of random integers between (and including) minValue and maxValue. These random integers will be stored in a dynamic array. Your program will then sort the list of random integers into descending order. Your program will measure the time taken by each method to sort the array of integers. You will then compare and comment upon the efficiency of each sorting method. Your main program should check for valid input and should deal with any special cases that arise. It is the responsibility of your main program to assure that the data passed into the sorting functions is valid and correct data for the sorting algorithms. Your main program should

· Prompts the user for the number of integers to be sorted

· Reads the user supplied number of integers into the integer variable numOfIntegers

· Prompt the user for a value of the seed for the generation of random integers

· Read the user supplied seed into the integer variable seed

· Prompt the user for the minimum integer that will be an acceptable random integer in the array

· Read the user supplied minimum value into the integer variable minValue

· Prompt the user for the maximum integer that will be an acceptable random integer in the array

· Read the user supplied maximum value into the integer variable maxValue

· Prompt the user for the name of an output file

· Read the user supplied output file name into the character array outFileName[32]

· For each of the sorting algorithms (Insertion sort, Selection Sort, Double Bubble sort, Quick Sort)

o Initialize the random number generator with the supplied seed (so all methods sort the same sequence of integers)

o Dynamically allocates an array of integers that can hold numOfIntegers integers, the identifier of the array should be randomArray.

o Fill the newly allocated array with random integers in the desired range

o Open the output file to append additional information (check to assure file is opened correctly)

o Print a title indicating array size and sorting method into the output file

o Print the unsorted array, 10 integers per line, into the output file. Each integer should be printed in a field 10 characters wide

o Call the appropriate function and sort the integers in the dynamic array

o Measure how long it took to sort the data (see instructions below)

o Print three blank lines to the output file

o Print the sorted array, 10 integers per line, into the output file. Each integer should be printed in a field 10 characters wide

o Close the output file, and clear the flags associated with the output file

o Verify that the data has been correctly sorted using your verifySorted function (see below for description of this function)

§ Print an error message and terminate the program if the integers are not correctly sorted

o Delete the dynamic array

§ Print the table shown below, filling in the values that were calculated above

Method Execution Time

______________________________________________
Insertion sort 0
Selection sort 0
Double Bubble sort 0
Quick sort 0

To measure how long it takes to sort the data use the following procedures:

· Define two integers called startTime and endTime at the beginning of you main program.

· Be sure to #include <ctime>. The include file ctime includes prototypes and other information defining functioins that can be used to measure the amount of time a program takes to execute.

· Using the functions developed in parts 1 through 5, and the int clock(void); function from <ctime>, measure the time used to complete each of your sorts. Do not include the time required to read the files, or to write out the sorted data. To measure the time used to complete a sort, complete each of the following actions:

o Call clock() at the start of your sort (after reading in the data, directly before calling your sort function) by inserting a statement startTime = clock(); before the statement in which you call the sort function.

o Call clock() again after your sort is complete by inserting the statement endTime = clock(); immediately after the statement in which you call the sort function.

o The length of time your sort took to order the data is given (in milliseconds) by (endTime – startTime).

The following functions from the C++ standard library, cstdlib, will also be useful (Remember to #include <cstdlib>)

void srand ( unsigned int seed ); This function initializes the starting point in the pseudo random sequence

Pseudo random numbers are sequences of numbers that are deterministically generated (you will always get the same sequence if you start with the same number or seed). These sequences have the property that any part of the sequence (any list of n numbers generated using the pseudo random number generator) has the statistical properties of a group of uniformly distributed random integers, uniformly distributed in the range 0<=generated number<=RAND_MAX. The sequence of numbers will have a fixed (long) length. To get different group of random numbers we select different parts of the overall sequence. To select a particular part of the sequence we initialize the random number generator with an unsigned integer called a seed to tell us where in the long sequence to select out first number. NOTE: do not initialize the seed to be an integer <=1

int rand(void); Generates a pseudo random integer between 0 and RAND_MAX (after initialization), each successive call to rand returns the next integer in the pseudo random sequence.

Run your program for array sizes of 1000, 10000, and 50000. Comment on which algorithms are fastest and why this is consistent with what we know about the algorithms used. The first three sorting methods are Big 0 N2 , Quick sort is Big O NlogN

This is the question that I must write code to. So far, I have been having problems with random sequence. I am not sure how the random sequence works. I understand that seed number represents where to psuedo series is going to start so I can have same random number if I have the seed number. But code wise, I don't understand how I can use the seed and how I can set the seed and how I can generate random numbers and put those numbers in to array. Please someone help...

[freudian_slip]

Well, upon searching google....

http://www.cprogramming.com/tutorial/random.html

I think it shows good examples of using random number generator using seed and stuffs.

[shiniboy]

Well, upon searching google....
I think it shows good examples of using random number generator using seed and stuffs.

Thanks for the info but I am still confused.

#include <fstream>
#include <iostream>
#include <cmath>
#include <cstdlib>


bool VerifySorted( int inArray[ ],  int L );
void InsertionSort(int inArray[], int N, int M, int L);
void DoubBubbleSort(int inArray[], int N, int M, int L);
void SelectionSort(int inArray[], int N, int M, int L);
void QuickSort(int inArray[], int N, int M );


using namespace std;


int main()
{
int numOfIntegers, seed, minValue, maxValue;
char outFileName[32];


cout <<"Enter number of integers to be sorted ";
cin  >>numOfIntegers;
cout <<"Enter value of the seed for the generation of random integers ";
cin  >>seed;
cout <<"Enter the minimum integer that will be an acceptable random integer in the array ";
cin  >>minValue;
cout <<"Enter the maximum integer that will be an acceptable random integer in the array ";
cin  >>maxValue;
cout <<"Enter the name of an output file ";
cin  >>outFileName[32];


srand((unsigned int) seed);
int rand();

So far, I have up to here. When I try to run the program, I receive error. What I am trying to do is create random number series with seed number promted by user and store those numbers to an array. Could you help me?

[freudian_slip]

Go look up reference manual or something. http://www.cplusplus.com/reference/clibrary/cstdlib/srand.html

Can you actually compile the code? Because I see that underneath

srand((unsigned int) seed);
int rand();

you probably want to take int out and make it

srand((unsigned int) seed);
rand();

and you put the above code into a loop.

[shiniboy]

Go look up reference manual or something. http://www.cplusplus.com/reference/clibrary/cstdlib/srand.html

Can you actually compile the code? Because I see that underneath

srand((unsigned int) seed);
int rand();

you probably want to take int out and make it

srand((unsigned int) seed);
rand();

and you put the above code into a loop.

#include <fstream>
#include <iostream>
#include <cmath>
#include <cstdlib>

bool VerifySorted( int inArray[ ], int L );
void InsertionSort(int inArray[], int N, int M, int L);
void DoubBubbleSort(int inArray[], int N, int M, int L);
void SelectionSort(int inArray[], int N, int M, int L);
void QuickSort(int inArray[], int N, int M );

using namespace std;

int main()
{
int numOfIntegers, seed, minValue, maxValue, i, counter;
char outFileName[32];
numOfIntegers = 0;

cout <<"Enter number of integers to be sorted ";
cin >>numOfIntegers;
cout <<"Enter value of the seed for the generation of random integers ";
cin >>seed;
cout <<"Enter the minimum integer that will be an acceptable random integer in the array ";
cin >>minValue;
cout <<"Enter the maximum integer that will be an acceptable random integer in the array ";
cin >>maxValue;
cout <<"Enter the name of an output file ";
cin >>outFileName[32];

srand((unsigned int) seed);
int randArray[numOfIntegers];

for(i=0; i<numOfIntegers; i++)
{
randArray[rand() % (maxValue - minValue + 1) + minValue];
}
}

So far, I have it up to here. But the problem is that I can't compile it because it's keep saying that randArray's size is undefined though user is going to type in the number when the code asks you to. Any solution to this?

[mrboolf]

You have to allocate dynamically the array if you want its dimension to be chosen by the user. You can't do that the way you tried to.

Use something like this for allocation:

int *myarray;
int mydimension;
cout << "Insert dimension:" << endl;
cin >> mydimension;
myarray = new int[mydimension];

and this for deallocation:

delete [] myarray;

Summary: new to allocate, delete to release the memory :)
If you google there's plenty of tutorial on how to use these ^^

[heerokeno]

To generate the random number and inserting that number into an array is not exactly as what Janice Regan wrote.. (since her assignments are always so f**king confusing and contradicting..)

but here is what you'd do..
you write

void srand (unsigned int seed);

to declare this function outside your program

and then you call this function in your program to generate numbers by writing

srand (seed);

After this, you need to create a loop to assign each number into your randomArray

ex.

for (i = 0; i < numOfIntegers; i++)
{ randomArray = rand(); }

that's all you need to do to create random numbers and placing them into your dynamic array..

Sources:
Me; i'm in your class and i finished this lab.

Enjoy the rest of your program.. the sorting functions are given so dont worry that much..

PS. good luck on the final, you know she'll screw us over..
Cheers