Consider the following code for a Bubble Sort application: ------------------- #

Question

Consider the following code for a Bubble Sort application:

-------------------

#include <iostream>

#include <iomanip>

using namespace std;

using std::setw;

using std::cout;

using std::endl;

using std::size_t;

int main() {

const short arraySize = 10;

short arr [ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };

     short hold;

     cout << "Data items in original order:" << endl;

     for ( size_t i = 0; i < arraySize; ++i ) {

       cout << setw ( 4 ) << arr [ i ];

     } // for i

     for ( size_t pass = 0; pass < arraySize; ++pass ) {

       for ( size_t j = 0; j < arraySize; ++j ) {

              if ( arr [ j ] > arr [ j + 1 ] ) {

                     hold = arr [ j ];

                     arr [ j ] = arr [ j + 1 ];

                     arr [ j + 1 ] = hold;

              } // if

       } // for j

     } // for pass

cout << endl << "Data items in ascending order:" << endl;

for ( size_t i = 0; i < arraySize; ++i ) {

       cout << setw ( 4 ) << arr [ i ];

     } // for i

cout << endl;

return 0;

} // BubbleSort

--------------------

1. Rewrite this code, using modular programming style, and correcting any errors if necessary. [50]

2. Optimize the algorithm by making the following modifications:

(a) After the first pass, the largest number is guaranteed to be in the highest-numbered element in the array; after the second pass, the two highest numbers are “in place,” and so on. Instead of comparing every pair on every pass, modify the algorithm to make as few comparisons as necessary on each pass. [10]

(b) Modify the algorithm to check at the end of each pass if any swaps have been made. If none have been made, the data must already be in the proper order, so the program should terminate. Observe the single-exit point rule when making this modification. [10]

3. Insert appropriate statements in your code to output the state of the array after every pass. [30]

4. Submit: (i) both hardcopy and softcopy of your source code; (ii) output of the program.

Explanation / Answer

Copy this code in file name BubbleSort.java and then run and execute.

/*
* Optimzation 1
* BubbleSort class have main function and
* sorting is done in it!
*/
public class BubbleSort {

   public static void main(String[] args) {
       short arraySize = 10;
       short arr[] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
       short hold;
      
       /*
       * Optimization point 2.b
       * this variable is set to true at begining of each pass
       * if some elements are swapped it is set to false
       * at the end of each pass if variable is still true =>
       * no swaps happened => already sorted => break the pass and print the result
       */
       boolean isAlreadySorted;
      
       System.out.println( "Data items in original order:" );

       for ( int i = 0; i < arraySize; ++i ) {
           System.out.printf("%4d", arr[ i ]);                //in place of setw(n)
       }

       for ( int pass = 0; pass < arraySize; ++pass ) {
           isAlreadySorted = true;
          
           /*
           * optimization 2.a
           * for each pass we need to see elements upto
           * arraySize - pass - 1
           * for pass 0 - see upto (arraySize - 1)th element(assuming array elements are number 0 to 9)
           * for pass 1 - see upto (arraySize - 2)th element
           * ..............
           * for pass 9 - see upto (arraySize - 10)th element
           */
           for ( int j = 0; j < arraySize - 1 - pass ; ++j ) {
               if ( arr [ j ] > arr [ j + 1 ] ) {
                   hold = arr [ j ];
                   arr [ j ] = arr [ j + 1 ];
                   arr [ j + 1 ] = hold;
                   isAlreadySorted = false;
               } // if
           } // for j
           if(isAlreadySorted)break;
          
           /*
           * Optimazation 2.c
           * prints state of array after each pass untill it is sorted
           */
           System.out.println( " Data items after "+(pass+1)+" pass:");
           for ( int i = 0; i < arraySize; ++i ) {
               System.out.printf("%4d", arr[ i ]);
           }
       } // for pass

       System.out.println( " Data items in ascending order:");
       for ( int i = 0; i < arraySize; ++i ) {
           System.out.printf("%4d", arr[ i ]);
       } // for i

   }
}

Run and execute:

Output:

Data items in original order:
   2   6   4   8 10 12 89 68 45 37
Data items after 1 pass:
   2   4   6   8 10 12 68 45 37 89
Data items after 2 pass:
   2   4   6   8 10 12 45 37 68 89
Data items after 3 pass:
   2   4   6   8 10 12 37 45 68 89
Data items in ascending order:
   2   4   6   8 10 12 37 45 68 89

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.