Write a program to improve the performance of the bubble sort program | MindTap Computing for Malik's C++ Programming 8th Edition

Introduction:

a. It was remarked in this chapter that the performance of bubble sort can be improved if we stop the sorting process as soon as we find that in an iteration no swapping of elements takes place. Write a function that implements bubble sort algorithm using this fact. (2)

b. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, 95. (2)

Write a program to test the function you designed in the above Exercise to improve the performance of bubble sort.

Source: MindTap Computing for Malik's C++ Programming From Problem Analysis to Program Design, 8th Edition, [Instant Access] (8th)-Malik, chapter 16, programming exercises 17.

Solved!

The objective of this program is to improve the performance of the bubble sort function. And test that function.

Program Plan:

· Define the header section.

· Define int bubbleSort(int arr[], int n)

o Declare int countIter = 0

o Use for loop i from 0 to n-2.

§ Declare bool swapped = false

§ Use for loop j from 0 to n-2-i.

· If arr[j] > arr[j + 1] is ture.

o Set swapped = true

o Swap element at index j and j+1 using swap(arr[j], arr[j + 1])

§ If still swapped == false

· Break the loop using break;

· Define int main() function.

o Declare array size int n;

o Take using input using cin >> n;

o Declare array int arr[n];

o Take input for array using for loop with statement cin >> arr[i];

o Declare int countIter = bubbleSort(arr, n)function call.

o Print sorted array using for loop with statement cout << arr[i] << ", "

o Print countIter

Program:

// Object of this program is to improve the performance of the bubbleSort function.

#include <iostream>

using namespace std;

// bubbleSort().
int bubbleSort(int arr[], int n)
{
    // counter for iteration.
    int countIter = 0;
    // use for loop i from 0 to n-2.
    for (int i = 0; i < n - 1; i++)
    {
        // set swapped bool value to false.
        bool swapped = false;
        // increment Iteration counter.
        countIter++;
        // for loop j from 0 to n-2-i.
        for (int j = 0; j < n - 1 - i; j++)
        {
            // check if jth element is greater than j+1th element.
            if (arr[j] > arr[j + 1])
            {
                // set swapped true.
                swapped = true;
                // and swap element.
                swap(arr[j], arr[j + 1]);
            }
        }

        // if swapped is still false.
        if (swapped == false)
        {
            // break the loop.
            break;
        }
    }
    // retrun countIter.
    return countIter;
}

// driver code.
int main()
{
    // take array size as input.
    int n;
    cout << "Enter array size:";
    cin >> n;
    // fill array with n user input.
    int arr[n];
    cout << "Enter " << n << " integers:";
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // call to bubbleSort() and store countIter.
    int countIter = bubbleSort(arr, n);
    // print sorted array.
    cout << "Array is sorted:" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ", ";
    }
    cout << endl;
    // print needed iteration after to sort array improvement .
    cout << "Number of iteration required to sort array using bubble sort:" << countIter << endl;

    // end.
    return 0;
}