• Status: Solved
• Priority: Medium
• Security: Public
• Views: 423

# Random Function & Comparisons

I have a program that should compare the relative performances of 4 different sorting algorithms on the same data set.  Each sort should be modified to include a counter to keep track of the number of comparisons made before integers are sorted.  The data set should use 100 integers that are generated using a random-number generator.  I have already written the programs to perform the four sorting algorithms.  I now have problems with the random number generator and the output.  The four algorithms to be tested are: Selection Sort, Bubble Sort, Merge Sort, and Quick Sort.  The following output should be repeated for each sort:  Name of Sort, Sorted list of 100 Integers, & Number of Comparisons made. Please Help Me!!!!   Here is what I have already:

//Selection Sort//

template<class ItemType>
int MinIndex(ItemType values[], int startIndex, int endIndex)
{
int IndexOfMin = startIndex;
for (int index = startIndex + 1; index <+ endIndex; index++)
if (values[index] < value[IndexOfMin])
IndexOfMin = index;
return IndexOfMin;
}

template<class ItemType>
void SelectionSort(ItemType values [], int numValues)
{
int endIndex = numValues - 1;
for (int current = 0; current <endIndex; current++)
{
int SelComp 0; // comparison counter
Swap(values[current], values[MinIndex(values, current, endIndex)]);
SelComp ++;
}
}

//BubbleSort//

template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex)
{
for (int index = endIndex; index>startIndex; index--)
if (values[index]<values[index-1])
Swap(values[index], values[index-1]);
}

template<class ItemType>
void BubbleSort(ItemType values[], int numValues)
{
int current = 0;
while (current < numValues-1)
{
int BubbleComp = 0 //comparison counter
BubbleUp(values, current, numValues-1);
current++;
BubbleComp++;
}
}

//Merge Sort//

template<class ItemType>
void Merge (ItemType values[], int leftFirst, int leftLast, int rightFirst, int rightLast)
{
ItemType tempArray[size];
int index = leftFirst;
int saveFirst = leftFirst;
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values [leftFirst] < values [rightFirst])
{
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}

while (leftFirst <= leftLast)
{
tempArray[index] = values [leftFirst];
leftFirst++;
index++;
}

while (rightFirst <= rightLast)
{
tempArray[index] = values[rightFirts];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}

template<class ItemType>
void MergeSort(ItemType values[], int first, int last)
{
if (first<last)
{
int MergeComp = 0; //comparison counter
int middle = (first + last)/2;
MergeSort(values, first, middle);
MergeSort(values, middle + 1, last);
Merge(values, first, middle, middle + 1, last);
MergeComp++;
}
}

//QuickSort//

template<class ItemType>
void Split(ItemType values[], int first, int last, int& splitPoint)
{
ItemType splitVal = values[first];
int saveFirst = first;
bool onCorrectSide;

first++;
do
{
onCorrectSide = true;
while (onCorrectSide)
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide)
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectside = (first <= last);
}
if (first < last)
{
Swap(values[first], values[last]);
first++;
last--;
}
}
while (first <= lst);
splitPoint = last;
Swap (values[saveFirst], values[splitPoint]);
}

template<class ItemType>
void QuickSort(ItemType values[], int first, int last)
{
if(first < last)
{
int QuickComp = 0; //comparisons counter
int splitPoint;
Split(values, first, last, splitPoint);
QuickSort(values, first, splitPoitn - 1);
QuickSort(values, splitPoint + 1, last);
QuickComp++;
}
}
0
krissi19
• 4
• 3
• 2
1 Solution

Commented:
So what problems exactly are you having?

You could use

void FillRandomIntArray(int values[], unsigned int nLength) {

srand( (unsigned)time( NULL ) );

for( int i = 0;   i < nLength;i++ )
values[i] =rand();
}

int main () {

int values[100];
const int nSamples = 1000;
int i = 0;
clock_t start, finish;
double  duration;
double  rand_duration;

// measure duration to initialize the array
start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values);

}

finish = clock();

rand_duration = (double)(finish - start) / CLOCKS_PER_SEC;

// measure duration for each algorithm

// QuickSort
printf ("Testing QuickSort()\n");

start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values);

QuickSort<int>(values, 0, 99);
}

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf ("QuickSort() took %fs\n", duration - rand_duration);

// MergeSort
printf ("Testing MergeSort()\n");

start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values);

MergeSort<int>(values, 0, 99);
}

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf ("MergeSort() took %fs\n", duration - rand_duration);

// and so on...

return 0;
}

0

Commented:
Oops,

the line

FillRandomIntArray (values, sizeof(values);

FillRandomIntArray (values, sizeof(values));

All of them above, to be precise  :o)
0

Commented:
>on the same data set.

Use jkr's code.Just fill the int array randomly once and store it in a temp array.Copy it to the array 'values' and use it to call the sorting functions.

You'll have to use the temp array since arrays are passed by reference.

BTW,if you are working on this,right now you are doing the average case.
You could also measure the best and the worst case also.

0

Author Commented:
My main problem isinserting the random number function into what I already have.  I do no want to start all over with a new program.  I just need to know where to go from where I am and how to get the specified output.
0

Author Commented:
This is my revised program.  Can you PLEASE help me fix it to do exactly what I need it to do?  I have tried but I just do not understand it.  I need help IMMEDIATELY for this assignment is due in the next couple of hours.  PLEASE HELP!!

//Selection Sort//

template<class ItemType>
int MinIndex(ItemType values[], int startIndex, int endIndex)
{
int IndexOfMin = startIndex;
for (int index = startIndex + 1; index <+ endIndex; index++)
if (values[index] < value[IndexOfMin])
IndexOfMin = index;
return IndexOfMin;
}

template<class ItemType>
void SelectionSort(ItemType values [], int numValues)
{
int SelComp = 0;
int endIndex = numValues - 1;
for (int current = 0; current <endIndex; current++)
{
Swap(values[current], values[MinIndex(values, current, endIndex)]);
SelComp ++;
}
cout<<"These integers were sorted using Selection Sort and the number of comparisons made were "<<SelComp<<"."<<endl;

}

//BubbleSort//

template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex)
{
for (int index = endIndex; index>startIndex; index--)
if (values[index]<values[index-1])
Swap(values[index], values[index-1]);
}

template<class ItemType>
void BubbleSort(ItemType values[], int numValues)
{
int BubbleComp = 0;
int current = 0;
while (current < numValues-1)
{
BubbleUp(values, current, numValues-1);
current++;
BubbleComp++;
}
cout<<"These integers were sorted using Bubble Sort and the number of comparisons made were "<<BubbleComp<<"."<<endl;
}

//Merge Sort//

template<class ItemType>
void Merge (ItemType values[], int leftFirst, int leftLast, int rightFirst, int rightLast)
{
ItemType tempArray[size];
int index = leftFirst;
int saveFirst = leftFirst;
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values [leftFirst] < values [rightFirst])
{
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}

while (leftFirst <= leftLast)
{
tempArray[index] = values [leftFirst];
leftFirst++;
index++;
}

while (rightFirst <= rightLast)
{
tempArray[index] = values[rightFirts];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}

template<class ItemType>
void MergeSort(ItemType values[], int first, int last)
{
int MergeComp = 0;
if (first<last)
{
int middle = (first + last)/2;
MergeSort(values, first, middle);
MergeSort(values, middle + 1, last);
Merge(values, first, middle, middle + 1, last);
MergeComp++;
}
cout<<"These integers were sorted using a Merge Sort and the number of comparisons made were "<<MergeComp<<"."<<endl;
}

//QuickSort//

template<class ItemType>
void Split(ItemType values[], int first, int last, int& splitPoint)
{
ItemType splitVal = values[first];
int saveFirst = first;
bool onCorrectSide;

first++;
do
{
onCorrectSide = true;
while (onCorrectSide)
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide)
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectside = (first <= last);
}
if (first < last)
{
Swap(values[first], values[last]);
first++;
last--;
}
}
while (first <= lst);
splitPoint = last;
Swap (values[saveFirst], values[splitPoint]);
}

template<class ItemType>
void QuickSort(ItemType values[], int first, int last)
{
int QuickComp = 0;
if(first < last)
{
int splitPoint;
Split(values, first, last, splitPoint);
QuickSort(values, first, splitPoitn - 1);
QuickSort(values, splitPoint + 1, last);
QuickComp++;
}
cout<<"These integers were sorted using a Quick Sort and the number of comparisons made were "<<QuickComp<<"."<<endl;
}

#include <iostream.h>
#include <stdlib.h>

int main()
{
int i;
for (i=0;i<=99;i++)
{
const RanNum[i]=int (1000*rand());
}
int Values;
int x;
int y;
SelectionSort(RanNum[i], Values);
BubbleSort(RanNum[i], Values);
MergeSort(RanNum[i], x, y);
QuickSort(RanNum[i], x, y);
return 0;
}
0

Commented:
Once your arrays are sorted, sorting them again makes no sense at all - try my suggestion. Furthermore, 'Swap()' is undefined and 'onCorrectSide' is misspelled several occasions in 'Split()'. Have you tried feeding the above to a compiler?
0

Author Commented:
jkr,

I saw your suggestion, but my C++ is not very strong and I do not understand it at all.  Can you possibly give me suggestions that refer to and utilize my program and variables that I have used.  Secondly, I did feed the program to the compiler, and here are my errors:

Compiling...
Sorting Algorithms.cpp
A:\Sorting Algorithms.cpp(169) : error C2057: expected constant expression
A:\Sorting Algorithms.cpp(169) : error C2466: cannot allocate an array of constant size 0
A:\Sorting Algorithms.cpp(169) : error C2440: 'initializing' : cannot convert from 'int' to 'const int []'
There are no conversions to array types, although there are conversions to references or pointers to arrays
A:\Sorting Algorithms.cpp(174) : error C2065: 'RanNum' : undeclared identifier
A:\Sorting Algorithms.cpp(174) : error C2109: subscript requires array or pointer type
A:\Sorting Algorithms.cpp(174) : error C2784: 'void __cdecl SelectionSort(ItemType [],int)' : could not deduce template argument for ' []' from 'int'
A:\Sorting Algorithms.cpp(175) : error C2109: subscript requires array or pointer type
A:\Sorting Algorithms.cpp(175) : error C2784: 'void __cdecl BubbleSort(ItemType [],int)' : could not deduce template argument for ' []' from 'int'
A:\Sorting Algorithms.cpp(176) : error C2109: subscript requires array or pointer type
A:\Sorting Algorithms.cpp(176) : error C2784: 'void __cdecl MergeSort(ItemType [],int,int)' : could not deduce template argument for ' []' from 'int'
A:\Sorting Algorithms.cpp(177) : error C2109: subscript requires array or pointer type
A:\Sorting Algorithms.cpp(177) : error C2784: 'void __cdecl QuickSort(ItemType [],int,int)' : could not deduce template argument for ' []' from 'int'
Error executing cl.exe.

Sorting Algorithms.obj - 12 error(s), 0 warning(s)
0

Commented:
OK, the following compiles, but I kinda suggest going through your sort algorithms again:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

//Selection Sort//

template<class ItemType>
int MinIndex(ItemType values[], int startIndex, int endIndex)
{
int IndexOfMin = startIndex;
for (int index = startIndex + 1; index <+ endIndex; index++)
if (values[index] < value[IndexOfMin])
IndexOfMin = index;
return IndexOfMin;
}

template<class ItemType>
void SelectionSort(ItemType values [], int numValues)
{
int endIndex = numValues - 1;
for (int current = 0; current <endIndex; current++)
{
int SelComp 0; // comparison counter
Swap(values[current], values[MinIndex(values, current, endIndex)]);
SelComp ++;
}
}

//BubbleSort//

template<class ItemType>
void BubbleUp(ItemType values[], int startIndex, int endIndex)
{
for (int index = endIndex; index>startIndex; index--)
if (values[index]<values[index-1])
Swap(values[index], values[index-1]);
}

template<class ItemType>
void BubbleSort(ItemType values[], int numValues)
{
int current = 0;
while (current < numValues-1)
{
int BubbleComp = 0 //comparison counter
BubbleUp(values, current, numValues-1);
current++;
BubbleComp++;
}
}

//Merge Sort//

template<class ItemType>
void Merge (ItemType values[], int leftFirst, int leftLast, int rightFirst, int rightLast)
{
int size = rightLast - leftFirst;
ItemType* tempArray = new ItemType[size];
int index = leftFirst;
int saveFirst = leftFirst;
while ((leftFirst <= leftLast) && (rightFirst <= rightLast))
{
if (values [leftFirst] < values [rightFirst])
{
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}

while (leftFirst <= leftLast)
{
tempArray[index] = values [leftFirst];
leftFirst++;
index++;
}

while (rightFirst <= rightLast)
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];

delete [] tempArray;
}

template<class ItemType>
void MergeSort(ItemType values[], int first, int last)
{
if (first<last)
{
int MergeComp = 0; //comparison counter
int middle = (first + last)/2;
MergeSort(values, first, middle);
MergeSort(values, middle + 1, last);
Merge(values, first, middle, middle + 1, last);
MergeComp++;
}
}

//QuickSort//

template<class T>
void Swap ( T r, T l) {

T tmp;
tmp = r;
r = l;
l = tmp;
}

template<class ItemType>
void Split(ItemType values[], int first, int last, int& splitPoint)
{
ItemType splitVal = values[first];
int saveFirst = first;
bool onCorrectSide;

first++;
do
{
onCorrectSide = true;
while (onCorrectSide)
if (values[first] > splitVal)
onCorrectSide = false;
else
{
first++;
onCorrectSide = (first <= last);
}
onCorrectSide = (first <= last);
while (onCorrectSide)
if (values[last] <= splitVal)
onCorrectSide = false;
else
{
last--;
onCorrectSide = (first <= last);
}
if (first < last)
{
Swap(values[first], values[last]);
first++;
last--;
}
}
while (first <= last);
splitPoint = last;
Swap<ItemType> (values[saveFirst], values[splitPoint]);
}

template<class ItemType>
void QuickSort(ItemType values[], int first, int last)
{
if(first < last)
{
int QuickComp = 0; //comparisons counter
int splitPoint;
Split(values, first, last, splitPoint);
QuickSort(values, first, splitPoint - 1);
QuickSort(values, splitPoint + 1, last);
QuickComp++;
}
}

void FillRandomIntArray(int values[], unsigned int nLength) {

srand( (unsigned)time( NULL ) );

for( int i = 0;   i < nLength;i++ )
values[i] =rand();
}

int main () {

int values[100];
const int nSamples = 10000;
int i = 0;
clock_t start, finish;
double  duration;
double  rand_duration;

// measure duration to initialize the array
start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values));

}

finish = clock();

rand_duration = (double)(finish - start) / CLOCKS_PER_SEC;

// measure duration for each algorithm

// QuickSort
printf ("Testing QuickSort()\n");

start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values));

QuickSort<int>(values, 0, 99);
}

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf ("QuickSort() took %fs\n", duration - rand_duration);

// MergeSort
printf ("Testing MergeSort()\n");

start = clock();

for (i = 0; i < nSamples; ++i) {

FillRandomIntArray (values, sizeof(values));

MergeSort<int>(values, 0, 99);
}

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

printf ("MergeSort() took %fs\n", duration - rand_duration);

// and so on...

return 0;
}
0

Commented:
The points should go to jkr.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 4
• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.