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?

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;
      }
}

---

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.

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.

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.

:)

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.

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

crikey.. didn' t think of that :eek:

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.