# Bubble Sort... which type?

• 08-14-2004
gflores
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?
• 08-14-2004
Thantos
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;       } }```
• 08-14-2004
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.
• 08-14-2004
gflores
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.
• 08-14-2004
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:

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

:)
• 08-14-2004
Davros
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.
• 08-14-2004
Dave Evans
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
• 08-14-2004
The Brain
oops
crikey.. didn' t think of that :eek:
• 08-15-2004
The Brain
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.