Bubblesorts (C++)

  • Complexity of Bubblesort
  • Complexity of sorting algorithms
  • Simulation of Bubblesort
  • bubbleSorts.cpp

    #include <iostream>
    
    using namespace std;
    
    void input(int array[], const int& N);
    void inputSize(int& N);
    void bubbleSort(int array[], const int& N);
    void bubbleSortImproved(int array[], const int& N);
    void bubbleSortAdvanced(int array[], const int& n);
    void print(int array[], const int& N);
    
    int main() {
        int N;
        inputSize(N);
        int array[N];
        input(array, N);
        //bubbleSort(array, N);
        //bubbleSortImproved(array, N);
        bubbleSortAdvanced(array, N);
        print(array, N);
        return 0;
    }
    
    /**
     * Request size of array.
     * @param N The size of the array.
     */
    void inputSize(int& N)
    {
        do{
            cout << "How many elements do you wish to input?" << endl;
            // Assume that input is numerical.
            cin >> N;
        }while(N <= 0);
    }
    
    /**
     * Fills the array from input.
     * @param array The array to be filled.
     * @param N The size of the array.
     */
    void input(int array[], const int& N)
    {
        cout << "Please, input " << N << " numbers to be sorted." << endl;
        // Assume that input is numerical.
        for(int i = 0 ; i < N ; i++) 
            cin >> array[i]; 
    }
    
    /**
     * Swap the parameters.
     * @param a The first parameter.
     * @param a The second parameter.
     */
    void swap(int& a, int& b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    
    /**
     * Swap the parameters without a temp variable.
     * Warning! Prone to overflow/underflow.
     * @param a The first parameter.
     * @param a The second parameter.
     */
    void swapNoTemp(int& a, int& b)
    {
        a -= b;
        b += a; // b gets the original value of a
        a = (b - a); // a gets the original value of b
    }
    
    /**
     * Bubblesort.
     * @param array The array to be sorted.
     * @param N The size of the array.
     */
    void bubbleSort(int array[], const int& N) 
    {
        for (int i = N-1 ; i > 0 ; --i)
        {
            for (int j = 0 ; j < i ; ++j)
            {
                if (array[j + 1] < array[j])
                    swap(array[j], array[j + 1]);
            }
        }
    }
    
    /**
     * Improved bubblesort.
     * Idea : If no swap happens in the inner loop,
     * then sorting is done.
     * @param array The array to be sorted.
     * @param N The size of the array.
     */
    void bubbleSortImproved(int array[], const int& N)
    {
        bool swapped;
        for (int i = N-1 ; i > 0 ; i--)
        {
            swapped = false;
            for (int j = 0 ; j < i ; j++)
            {
                if (array[j + 1] < array[j])
                {
                    swapNoTemp(array[j], array[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped)
                break;
        }
    }
    
    /**
     * Improved² bubblesort.
     * Idea : After each pass we have moved the
     * highest misplaced item to its correct position.
     * @param array The array to be sorted.
     * @param N The size of the array.
     */
    void bubbleSortAdvanced(int array[], const int& N)
    {
        int i = N-1;
        do{
            int k = 0;
            for(int j = 0 ; j < i ; ++j) {
                if(array[j + 1] < array[j])
                {
                    swap(array[j], array[j + 1]);
                    k = j;
                }
            }
            i = k;
        }while (i > 0);
    }
    
    /**
     * Print array.
     * @param array The array to be printed.
     * @param N The size of the array.
     */
    void print(int array[], const int& N)
    {
        cout << endl << "---------------------------" << endl << endl;
        cout << "The sorted array is : " << endl;
        for(int i = 0 ; i < N ; i++)
            cout << "array[" << i << "] = " << array[i] << endl;
    }
    

    This code was developed by me, G. Samaras.

    Notice, that I used as little C++ as possible, so that one can easy interchange between C and C++.
    I was inspired by the home page of M. Phillips.
    Have questions about this code? Comments? Did you find a bug? Let me know!😀
    Page created by G. (George) Samaras (DIT)

3 thoughts on “Bubblesorts (C++)

  1. Pingback: What is difference between Bubble,selection & insertion sort?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s