-----------------------------------

JessT0

Thu Mar 25, 2004 5:55 pm


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.


-----------------------------------

Dan

Thu Mar 25, 2004 10:36 pm



-----------------------------------

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


-----------------------------------

wtd

Thu Mar 25, 2004 10:41 pm



-----------------------------------

By "list" does your teacher mean "array" or one of the STL classes, like std::vector or std::list?


-----------------------------------

Dan

Thu Mar 25, 2004 10:47 pm



-----------------------------------

By "list" does your teacher mean "array" or one of the STL classes, like std::vector or std::list?

 :?  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.


-----------------------------------

JessT0

Mon Mar 29, 2004 1:06 pm



-----------------------------------

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...


-----------------------------------

JessT0

Mon Mar 29, 2004 1:08 pm



-----------------------------------

here what i have done for bubble sort:

#include 
#include 
#include 
#include 
#include 
#include 
#include 


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  operator works with.

template 
void bubble_sort(_t [], _t *);

template 
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.

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