Thread: Howz this for improvement!

  1. #1
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124

    Howz this for improvement!

    Everyone should know the bubble sort method of organising an array. I sat down and made some improvements as I can imagine how bad this method of sorting an array is with really large arrays. What do you guys think?

    Code:
    // Enhanced bubble sort
    
    #include <cstdlib>
    using std::rand;
    using std::srand;
    
    #include <iostream> 
    using std::cout;
    using std::cin;
    
    // Prototypes
    void bubblesort( int array[], int );
    
    int main()
    {
       const int arraySize = 100;
       int array[ arraySize ];
       
       srand( time( 0 ) );
       
       // Simply enters random values into the array
       for( int i = 0; i < arraySize; i++)
          array[ i ] = ( 1 + rand() % 1000 );
          
       cout << "Unsorted Array: \n";
       
       // Outputs all elements of the array before being sorted
       for( int i = 0; i < arraySize; i++ )
          cout << array[ i ] << ' ';
          
       bubblesort( array, arraySize );
       cout << "\n\nSorted Array: \n";
       
       // Outputs all elements of the array after being sorted
       for( int i = 0; i < arraySize; i++ )
          cout << array[ i ] << ' ';
       
       cout << "\n\nPress a key to quit . . . ";
       cin.get();
       return 0;
    }
    
    void bubblesort( int array[], int size )
    {
       int hold; // to temporarily hold the variable while sorting
       int reduce = 0; // speeds up the bubble sort by removing comparrisons not needed
       int swaps = 0; // counts how many swaps have been made during execution
       
       // To control number of passes
       for( int pass = 1; pass < size; pass++, reduce++ )
       {
          // Controls number of comparrisons per pass
          for( int j = 0; j < size - 1 - reduce; j++ )
          
             if( array[ j ] > array[ j + 1 ] )
             {
                hold = array[ j ];
                array[ j ] = array[ j + 1 ];
                array[ j + 1 ] = hold;
                swaps++;
             }
          
          // If no swaps have been made then the data must already be in the correct
          // order, so the sorting should terminate 
          if( swaps == 0 )
             pass = size;
       }
    }

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Those are the typical improvements on the bubble sort. In all honesty, it still sucks. Look up quick sort, and implement that, if you want a better algorithm.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I sat down and made some improvements
    Why? No amount of optimization will turn a bad algorithm into a good one. Try shellsort if you want something simple. It is far better than bubblesort and easier to understand and implement than quicksort and mergesort. Or you could use the C qsort, or C++ std::sort functions. They are there for a reason.
    My best code is written with the delete key.

  4. #4
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    Quick sort is part of the standard library.

    Edit: Prelude beat me to that one.
    OS: Windows XP
    Compilers: MinGW (Code::Blocks), BCB 5

    BigAngryDog.com

  5. #5
    Registered User cyberCLoWn's Avatar
    Join Date
    Dec 2003
    Location
    South Africa
    Posts
    124
    Yah I know my improvements are nothing special. I was just impressed that I improved something!

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Quick sort is part of the standard library.
    Maybe for your implementation, but the choice of algorithm is up to the implementation. In fact, because the standard makes no mention of qsort's performance, it could very well be implemented with bubblesort (god forbid). C++ on the other hand requires n log n performance, so you can be sure that it at least sorts efficiently. You can be pretty sure that qsort will as well because most implementors are not completely stupid.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Howz this equality operator working?
    By duffmckagan in forum C Programming
    Replies: 6
    Last Post: 06-23-2007, 08:22 AM