krissi19
asked on
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[inde
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++;
}
}
//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[inde
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++;
}
}
Oops,
the line
FillRandomIntArray (values, sizeof(values);
should of course read
FillRandomIntArray (values, sizeof(values));
All of them above, to be precise :o)
the line
FillRandomIntArray (values, sizeof(values);
should of course read
FillRandomIntArray (values, sizeof(values));
All of them above, to be precise :o)
>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.
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.
ASKER
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.
ASKER
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[inde
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;
}
//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[inde
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;
}
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?
ASKER
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)
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)
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
The points should go to jkr.
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;
}