Computer Science Canada

Hard proplem for C++!!!
Author:  JessT0 [ Thu Mar 25, 2004 5:55 pm ]
Post subject:  Hard proplem for C++!!!
hi everyone

I have a hard time to working on this proplem,If anyone have any idea? ,i would appreciate alot:
Here is the original proplem:

Create the bubble sort function .Make sure that it is an efficient bubblesort, i.e., the outer loop is exited as soon as it is determined that the list is sorted and the elemnts which are placed in their correct postition in each pass are ignored on subsequent passes .
Time your sort using the following three test case:
1. best case( already in ascending order)
2. worst case(descending order)
3. average case (in random oder)

Create three seperate function to generate the above list.Use the rand()function to generate a list of random numbers.Function rand() can be used to generate a sequence of pseudo-radom numbers.It returns an interger between 0 and RAND_MAX. Seed or initialize this function with srand(time(0)), which will then ensure a diffence sequence of random numbers for each run of the program .You will need to include the header file cstdlib.

Use the clock() function to time the sort .Function clock() approximates the amount of time the current program has been running. It returns a value of type clock_t, which is the elapsed time in number of clock ticks. To transform this value into second ,divide it by the constant CLOCK_PER_SEC which is the number of sustem clock ticj per second. You may need to cast either th edivisor or the divided to double to ensure that the results will be floating point , rather that integral. You will need to include the header file ctime.

note:
1. Output using a small list size, e.g., 20- run time may not be very different for lists this size.
2. Out put using a large list size, e.g., probably something in the range 10000- 50000.
Author:  Dan [ Thu Mar 25, 2004 10:36 pm ]
Post subject: 
well i could be reading it wrong but it sounds like all u have to do is make a buble sort algrithm. the code for that (witch may not be in c++) should be on this site some where. (i know for a fact i made a java tutorial on buble sort, witch is very close to c++).

for the clock() stuff just put put clock / CLOCK_PER_SEC
Author:  wtd [ Thu Mar 25, 2004 10:41 pm ]
Post subject: 
By "list" does your teacher mean "array" or one of the STL classes, like std::vector or std::list?
Author:  Dan [ Thu Mar 25, 2004 10:47 pm ]
Post subject: 
wtd wrote:
By "list" does your teacher mean "array" or one of the STL classes, like std::vector or std::list?


Confused i did not think of that i aussmed he ment array. but i whould think that the basick bubble sort method that can be found around here could be easly moded to fit that.
Author:  JessT0 [ Mon Mar 29, 2004 1:06 pm ]
Post subject: 
hi everyone
can anyone give me a couple examples of them?i'm looking for some codes which tell me the time after i run the bubble sort.Thanks alot

note: my bouble sort will use to sort a array which have few hundred number,thousand of numbers...
Author:  JessT0 [ Mon Mar 29, 2004 1:08 pm ]
Post subject: 
here what i have done for bubble sort:
code:

#include <iostream.h>
#include <cstdlib>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>


int main()
{
   int const ArrayVal = 20;
   int vu[ArrayVal];
   int i,j;
   clock_t  clock(void);
   typedef long int clock_t;
   clock_t start, finish;
   double duration;

  //Generate array of random integer numbers
   srand( (unsigned)time( NULL ) ); //May sure random every time
   for (i = 0; i <ArrayVal; i++)
   {
      vu[i] = rand();
   }

   //Output unsort array
   cout<< "Before sort : \n";
   for (i = 0; i < ArrayVal; i++)
   {
      cout << vu[i] << "\t";
   }
   cout << "\n";
   start= clock();

   //Bubble sort
   int current;
   for (i = ArrayVal; i >= 0; i--)
   {
     for (j = 0; j < i -1; j++)
     {
        if (vu[j] > vu[j+1])
        {
           current = vu[j+1];
           vu[j+1] = vu[j];
           vu[j] = current;
        }
     }
   } //End Bubble sort

   finish = clock();
   duration = static_cast<double>(finish - start) / CLOCKS_PER_SEC;

   //Output
   cout <<"After sorted : \n";
   for (i = 0; i < ArrayVal; i++)
   {
      cout << vu[i] << "\t";
   }
   cout << "Total Time is :\n" << duration;
   system("pause");
   return 0;
}

note: the clock() doesn't work yet, need something to make it work,please help, thanks first
note
Author:  wtd [ Mon Mar 29, 2004 1:48 pm ]
Post subject: 
Looks good. I just cleaned it up a bit. Not sure about clock(), though.

code:
#include <iostream>
#include <stdlib.h>
#include <string>
#include <ctime>

template <typename _t>
void swap(_t &, _t &);

template <typename _t>
void bubble_sort(_t [], _t *);

template <typename _t>
void print_array(std::ostream &, _t [], _t *);

void fill_array_with_random_ints(int [], int *);

class timer
{
        private:
                double start_time, finish_time;
                double duration_ticks() const;
        public:
                timer();
                void start();
                void finish();
                double duration() const;
};

int main()
{
        const int ARRAY_LENGTH = 20;
        int * vu = new int[ARRAY_LENGTH];
        int * vu_end = vu + ARRAY_LENGTH;

        //Generate array of random integer numbers
        //May sure random every time
        srand( (unsigned)time( NULL ) );
        fill_array_with_random_ints(vu, vu_end);

        // Output unsorted array
        std::cout << "Before sort:" << std::endl;
        print_array(std::cout, vu, vu_end);

        timer time;
        time.start();

        bubble_sort(vu, vu_end);

        time.finish();

        // Output sorted array
        std::cout << "After sorted:" << std::endl;
        print_array(std::cout, vu, vu_end);

        std::cout << "Total Time is:" << std::endl
                          << time.duration()  << std::endl;

        system("pause");
        return 0;
}

template <typename _t>
void swap(_t & a, _t & b)
{
        _t f = a;
        _t s = b;

        a = s;
        b = f;
}

template <typename _t>
void bubble_sort(_t arr[], _t * end)
{
        // Repeat inner sorting loop this many times
        int times = end - arr;

        for (int i = 0; i < times; i++)
        {
                for (_t * iter(arr); iter != end; iter++)
                {
                        if (*iter > *(iter + 1))
                        {
                                swap(*iter, *(iter + 1));
                        }
                }
        }
}

template <typename _t>
void print_array(std::ostream & out, _t arr[], _t * end)
{
        for (_t * iter(arr); iter != end; iter++)
        {
                out << *iter << std::endl;
        }
}

void fill_array_with_random_ints(int arr[], int * end)
{
        for (int * iter(arr); iter != end; iter++)
        {
                *iter = rand();
        }
}

timer::timer() : start_time(0.0), finish_time(0.0) { }

void timer::start()
{
        start_time = clock();
}

void timer::finish()
{
        finish_time = clock();
}

double timer::duration_ticks() const
{
        return finish_time - start_time;
}

double timer::duration() const
{
        return duration_ticks() / CLOCKS_PER_SEC;
}
Author:  JessT0 [ Wed Mar 31, 2004 1:58 pm ]
Post subject: 
Thank to wtd, the way u did it's so complicated(for advance peoples) ,i just wanna go with easy way .but your code was help me alot

Here what i did:
code:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
int main()
{
   int const ArrayVal = 5000;
   int vu[ArrayVal];
   int i;
   typedef long int clock_t;
   clock_t start, finish ;
   double duration;
   void print(const int ArrayVal[],int vu =5000);
   void sort(const int ArrayVal[], int vu =5000);


  //Generate array of random integer numbers
   srand( (unsigned)time( NULL ) ); //May sure random every time
   for (i = 0; i <ArrayVal; i++)
   {
      vu[i] = rand();
   }

   //Output unsort array
   cout<< "Before sort : \n";
   print(vu);

   cout << "\n";
   start= clock(); //start the time

   sort(vu);


   finish = clock();  //finish the time
   duration = static_cast<double>(finish - start) / CLOCKS_PER_SEC;

   //Output
   cout <<"After sorted : ";
   print(vu);

   cout << "\nTotal Time is : " << duration <<endl;
   system("pause");
   return 0;
}

void print(const int ArrayVal[],int vu =5000)
{
   int i;
   for (i = 0; i < vu; i++)
   {
      cout << ArrayVal[i] << "\t";
   }
   cout << "\n";
}

void sort(const int ArrayVal[], int vu =5000)
{
   int current;
   int i,j;
   for (i = vu; i >= 0; i--)
   {
     for (j = 0; j < i -1; j++)
     {
        if (ArrayVal[j] > ArrayVal[j+1])
        {
           current = ArrayVal[j+1];
           ArrayVal[j+1] = ArrayVal[j];
           ArrayVal[j] = current;
        }
     }
   }
}//End Bubble sort


It still has error .it said " assigmnet read only localtion",Please correct me ,thanks
Author:  wtd [ Wed Mar 31, 2004 7:47 pm ]
Post subject: 
Let me see if I can explain, because I don't think it's nearly as complicated as it looks. Smile

swap

The swap function takes two references and swaps the values in them. To do this it first gets the values in the two variables, then assigns the first value to the second variable, and the second value to the first variable.

The fact that it's defined as a template means it can work with any data type, and not just simple little ints. Smile

code:
template <typename _t>
void swap(_t &, _t &);

template <typename _t>
void swap(_t & a, _t & b)
{
   _t f = a;
   _t s = b;

   a = s;
   b = f;
}


A simple example of this would be:

code:
int first_int  =  5,
    second_int = 12;

std::cout << first_int << second_int << std::endl;

swap(first_int, second_int);

std::cout << first_int << second_int << std::endl;


The first prints out "512" and the second prints out "125".

print_array

This function (and others) make use of the fact that arrays in C++ (and C and Objective-C) are simply pointers to the address in memory where they start, and the elements are after that address in order. So we point our "iterator" at the beginning of the array, then increase the memory address until the iterator is pointing at the end of the array. The iterator can then be dereferenced to get each "thing" in the array. For iterating we pass in the beginning of the array and the end of the array.

Again, the fact that print_array is a templated function so it can be used with arrays filled with any type of data.

So that it can be used to output to something other than standard output (cout) we pass in a reference to an output stream.

code:
template <typename _t>
void print_array(std::ostream &, _t [], _t *);

template <typename _t>
void print_array(std::ostream & out, _t arr[], _t * end)
{
   for (_t * iter(arr); iter != end; iter++)
   {
      out << *iter << std::endl;
   }
}


fill_array_with_random_ints

Again we use the fancy iterating trick. Smile

This time there are no templates involved though. Instead we're simply dealing with ints. This function is fairly simple. It iterates over an array (the beginning and end of the array are passed in) and stores the result of rand() in each element of the array. For simplicity sake, the function doesn't handle seeding the random number generator with srand().

code:
void fill_array_with_random_ints(int [], int *);

void fill_array_with_random_ints(int arr[], int * end)
{
   for (int * iter(arr); iter != end; iter++)
   {
      *iter = rand();
   }
}


timer

The handling of time in this program is done with timers (instances of the timer class). Internally the timer keeps track of a start time and a finish time. Also internally, it's able to calculate the ticks between those times.

The external interface has a constructor which simply initializes the start and finish times to zero, and functions to set the start and finish times to the value returned by clock(). The duration() function returns the ticks between start and finish divided by the number of clock ticks in a second.

The implementstions of these functions is so simple it needn't be repeated again.

code:
class timer
{
   private:
      double start_time, finish_time;
      double duration_ticks() const;
   public:
      timer();
      void start();
      void finish();
      double duration() const;
};


bubble_sort

This is the meat of the program. It makes use of the iterating scheme I've used in previous functions. It uses your logic, but uses the swap function to switch elements of the array. Also, it's templated so it'll sort arrays of any data type. Well, any data type that the > operator works with.

code:
template <typename _t>
void bubble_sort(_t [], _t *);

template <typename _t>
void bubble_sort(_t arr[], _t * end)
{
   // Repeat inner sorting loop this many times
   int times = end - arr;

   for (int i = 0; i < times; i++)
   {
      for (_t * iter(arr); iter != end; iter++)
      {
         if (*iter > *(iter + 1))
         {
            swap(*iter, *(iter + 1));
         }
      }
   }
}


main

And the main function just makes use of everything else we've defined. The only new thing here is using the "new" keyword to create an array. I've also created a variable to point to the end of the vu array.

Oh, and in C++ you don't need to declare all of your variables at the beginning of a function. You can define them when you first need them.

code:
int main()
{
   const int ARRAY_LENGTH = 20;
   int * vu = new int[ARRAY_LENGTH];
   int * vu_end = vu + ARRAY_LENGTH;

   //Generate array of random integer numbers
   //May sure random every time
   srand( (unsigned)time( NULL ) );
   fill_array_with_random_ints(vu, vu_end);

   // Output unsorted array
   std::cout << "Before sort:" << std::endl;
   print_array(std::cout, vu, vu_end);

   timer time;
   time.start();

   bubble_sort(vu, vu_end);

   time.finish();

   // Output sorted array
   std::cout << "After sorted:" << std::endl;
   print_array(std::cout, vu, vu_end);

   std::cout << "Total Time is:" << std::endl
           << time.duration()  << std::endl;

   system("pause");
   return 0;
}

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy