Thread: Bubble Sort... which type?

  1. #1
    Some Guy
    Join Date
    Jul 2004
    Posts
    32

    Bubble Sort... which type?

    Ok, I'm learning the bubble sort from my textbook, and it looks slightly different than the bubble sorts that I've seen online. Then, I read that there are different types of bubble sorts. However, the book doesn't mention any of this. This is what the book has....


    Code:
    void bubbleSort(int array[], int elems)
    {
    	int swap, temp;
    	
    	do{
    		
    		swap = 0;
    		for(int count = 0; count < (elems-1); count++)
    		{
    			if(array[count] > array[count+1])
    			{
    				temp = array[count];
    				array[count] = array[count+1];
    				array[count+1] = temp;
    				swap = 1;
    			}
    		}
    	} while(swap != 0);
    }
    Can someone tell me which bubble sort this is, and if there is a better or a better way of writing the bubble sort, or is this ok?

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I only know of two types of bubble sorts, one that sorts from the front to the back and one that sorts from the back to the front.

    Bubble sort is the slowest style. From a quick scan I can't really tell how well it will work if at all. Quick and dirty bubble sort:
    Code:
    template <typename T>
    void bubbleSortASC ( T* arr, int size )
    {
      for (int i=0; i < size - 1; size++)
        for (int j=0; j < size; size++)
          if ( arr[i] > arr[j] )
          {
            T temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
          }
    }

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Bubble sort refers to the process of swapping one element with another based on comparison. The syntax of how this accomplished can vary, but the process remains the same. All versions I've seen uses two loops. One to control how many times you run the comparisons, the outer loop, and one to control each comparison, the inner loop. In the version posted by gflores the outer loop will terminate whenever there is an inner loop that doesn't do any swaps---because the elements are already in order to why bother to do any more comparisons? Thantos's version looks at all possiblities, even if the last half, or whatever, of the loops don't involve any swaps at all. The first version is therefore a little more sophisticated (optimized) than the second, but both are bubble sorts.

  4. #4
    Some Guy
    Join Date
    Jul 2004
    Posts
    32
    Well, thank you. That clears things up for me. I was just a little confused since the bubble sort in the book uses a do-while loop, and on other sites, I saw 2 for loops. Thank you.

  5. #5
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Thumbs up

    Hello

    One important aspect of the bubble sort that was not mentioned, is that you can terminate the sort as soon as you can detect that no further transactions are being made.

    Here is a bubble sort algorithm I wrote for computer science II.

    Code:
    //Bubble Sort Algorithm
    for(int p = 0; p < (capacity - 1); p++)			//The outter FOR loop will execute the
    {					                //bubble sort "array capacity - 1" times.  
    	
    	int place_holder = 0;
    
    	for(int i = 0; i < (capacity - 1); i++)	        //The inner FOR loop executes an 
    	{						//"element by element" comparison
    		int j = i;						
    
    		if(array[i] > array[++j])		//The "swap" algorithm will "push"
    		{					//larger numbers to the greater 
    			place_holder = array[j];	//end of the array
    
    			array[j] = array[i];
    
    			array[i] = place_holder;
    		}
    		
    	}
    
    	if(place_holder == 0)			//A switch is provided to "break" the  
    						//FOR loop if no swaps are being made.
    		break;
    }

    In this instance, if the variable place_holder remains equal to zero after being ran through the bubble sort algorithm.. then the loop will break.

    Last edited by The Brain; 08-14-2004 at 01:42 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  6. #6
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    Found this, it may (or may not) be useful to you. It discusses different sorting techniques:

    http://www.devarticles.com/c/a/Cplus...-And-C-plus/1/

    In the C library, there is a handy ready made 'qsort' function which I find useful. I understand there are additional and more flexible sort methods in C++ library, but I have never used them.
    OS: Windows XP
    Compilers: MinGW (Code::Blocks), BCB 5

    BigAngryDog.com

  7. #7
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by The Brain
    Hello

    One important aspect of the bubble sort that was not mentioned, is that you can terminate the sort as soon as you can detect that no further transactions are being made.

    Here is a bubble sort algorithm I wrote for computer science II.

    ....................code snipped..................

    In this instance, if the variable place_holder remains equal to zero after being ran through the bubble sort algorithm.. then the loop will break.


    Try it with array[] = {2, 3, 1, 0}, capacity = 3.

    Try it with array[] = {2, 1, 0, 3}

    After the first time through the loop, place_holder == 0 (since that's the last switch that was made).

    Dave

  8. #8
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    oops

    crikey.. didn' t think of that
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  9. #9
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    If it's any consolation.. here is the entire program... as you can see, my method of terminating the sort sequence would work in this program.

    Code:
    
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    
    int main()
    {
    
    system("cls");
    
    int array[11] = {90, 1, 43, 16, 32, 12, 6, 14, 96, 20, 3};
    
    cout << "\nHere is the unsorted array: \n\n";
    
    for(int i = 0; i < 11; i++)
    {
    	cout << " " << array[i] << "  ";
    }
    
    cout << endl << endl;
    system("pause");
    
    
    
    //Bubble Sort Algorithm
    for(int p = 0; p < 10; p++)			//The outter FOR loop will execute the
    {									//bubble sort "array capacity - 1" times.  
    	
    	int place_holder = 0;
    
    	for(int i = 0; i < 10; i++)			//The inner FOR loop executes an 
    	{									//"element by element" comparison
    		int j = i;						
    
    		if(array[i] > array[++j])		//The "swap" algorithm will "push"
    		{								//larger numbers to the greater 
    			place_holder = array[j];	//end of the array
    
    			array[j] = array[i];
    
    			array[i] = place_holder;
    		}
    		
    	}
    
    	if(place_holder == 0)			//A switch is provided to "break" the  
    									//FOR loop if no swaps are being made.
    		break;
    }
    
    
    cout << "\n\nHere is the sorted array: \n\n";
    
    for(int i = 0; i < 11; i++)
    {
    	cout << " " << array[i] << "  ";
    }
    
    cout << endl << endl;
    system("pause");
    
    int search_key = 0;
    cout << "\n\nEnter an integer type search key: ";
    cin >> search_key;
    
    
    
    
    //Binary Search 
    	
    	int low = 0;
    	int high = 10;	
    	int middle = 0;
    	
    	while( low <= high )
    	{
    		middle = ( low  + high ) / 2;
    		
    		if( search_key == array[middle] ) //match
    		{	
    			cout << "\nYour search key '" << search_key << "' was found in array element [" 
    				 << middle << "]\n\n"
    				 << "\nThank you for viewing my sort and search demonstration.";
    				 
    				 exit(0);
    		}		
    		
    		else if( search_key < array[middle] )
    			
    			high = middle - 1;		//search low end of array
    		
    		else
    			
    			low = middle + 1;		//search high end of array
    	}
    
    	cout << "\nYour search key << search_key << is not part of the array.\n\n"
    		 << "Better luck next time.";
    
    return EXIT_SUCCESS;
    
    }


    I think my previous example may have been to ambiguous. If array[] was restricted to a non-zero domain would work.
    Last edited by The Brain; 08-15-2004 at 05:04 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Script errors - bool unrecognized and struct issues
    By ulillillia in forum Windows Programming
    Replies: 10
    Last Post: 12-18-2006, 04:44 AM
  2. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM
  3. bubble sort not working with struct...
    By Jenica in forum C++ Programming
    Replies: 1
    Last Post: 10-12-2004, 12:54 PM
  4. gcc problem
    By bjdea1 in forum Linux Programming
    Replies: 13
    Last Post: 04-29-2002, 06:51 PM
  5. bubble sort and structures?
    By bluebob in forum C Programming
    Replies: 7
    Last Post: 03-15-2002, 11:16 PM