Solved

Random Function & Comparisons

Posted on 2004-04-25
12
383 Views
Last Modified: 2008-02-01
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
Comment
Question by:krissi19
  • 4
  • 3
  • 2
12 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 10914548
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
 
LVL 86

Expert Comment

by:jkr
ID: 10914556
Oops,

the line

       FillRandomIntArray (values, sizeof(values);

should of course read

       FillRandomIntArray (values, sizeof(values));

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

Expert Comment

by:ankuratvb
ID: 10917613
>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 Comment

by:krissi19
ID: 10923226
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:krissi19
ID: 10930701
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
 
LVL 86

Expert Comment

by:jkr
ID: 10930826
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 Comment

by:krissi19
ID: 10931518
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
 
LVL 86

Accepted Solution

by:
jkr earned 500 total points
ID: 10931728
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
 
LVL 9

Expert Comment

by:ankuratvb
ID: 11194383
The points should go to jkr.
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now