fork download
copy 
  1. //Ryan Shahriyarpour   CS1A  Chapter 8   Question 9
  2. /*****************************************************************************
  3.  * 
  4.  * Sorting Benchmarks
  5.  * 
  6.  *********************
  7.  * 
  8.  * This program uses two identical arrays of 20 integers. One is sorted with
  9.  * a bubble sort and the other with a selection sort. Each sort counts the
  10.  * number of exchanges (swaps) it makes so the two methods can be compared.
  11.  * 
  12.  * *******************
  13.  *  Bubble sort    - swaps neighboring elements that are out of order and
  14.  *                   repeats until a full pass makes no swaps.
  15.  *  Selection sort - each pass finds the smallest unsorted value and swaps
  16.  *                   it into place (only counted if it actually moves).
  17.  * 
  18.  * INPUT
  19.  *  None (the arrays are stored in the program)
  20.  * 
  21.  * OUTPUT    
  22.  *  The sorted array
  23.  *  The number of exchanges made by the bubble sort
  24.  *  The number of exchanges made by the selection sort
  25.  * 
  26.  ****************************************************************************/
  27.  
  28. #include <iostream>
  29. using namespace std;
  30.  
  31. // Constant for the number of array elements
  32. const int SIZE = 20;
  33.  
  34. // Function prototypes (the sorts return the number of exchanges made)
  35. int bubbleSort(int array[], int size);
  36. int selectionSort(int array[], int size);
  37. void displayArray(const int array[], int size);
  38.  
  39. int main()
  40. {
  41.     // data dictionary
  42.     int bubbleArray[SIZE] = {       // Array sorted with the bubble sort
  43.         45, 12, 89, 3, 67, 24, 91, 8, 56, 33,
  44.         72, 19, 5, 98, 41, 27, 60, 14, 83, 38
  45.     };
  46.     int selectArray[SIZE] = {       // Identical array for the selection sort
  47.         45, 12, 89, 3, 67, 24, 91, 8, 56, 33,
  48.         72, 19, 5, 98, 41, 27, 60, 14, 83, 38
  49.     };
  50.     int bubbleExchanges;            // Exchanges made by the bubble sort
  51.     int selectExchanges;            // Exchanges made by the selection sort
  52.  
  53.     // Sort both arrays
  54.     bubbleExchanges = bubbleSort(bubbleArray, SIZE);
  55.     selectExchanges = selectionSort(selectArray, SIZE);
  56.  
  57.     // Display the results
  58.     cout << "Sorted array: ";
  59.     displayArray(bubbleArray, SIZE);
  60.     cout << "\nBubble sort exchanges:    " << bubbleExchanges << endl;
  61.     cout << "Selection sort exchanges: " << selectExchanges << endl;
  62.  
  63.     return 0;
  64. }
  65.  
  66. // Bubble sort in ascending order; returns the number of exchanges
  67. int bubbleSort(int array[], int size)
  68. {
  69.     // data dictionary
  70.     int index;                      // Loop counter comparing neighbors
  71.     int temp;                       // Holds a value during a swap
  72.     int exchanges = 0;              // Number of swaps made
  73.     bool swapped;                   // True if a swap happened this pass
  74.  
  75.     do
  76.     {
  77.         swapped = false;
  78.         for (index = 0; index < size - 1; index++)
  79.         {
  80.             if (array[index] > array[index + 1])
  81.             {
  82.                 temp = array[index];
  83.                 array[index] = array[index + 1];
  84.                 array[index + 1] = temp;
  85.                 swapped = true;
  86.                 exchanges++;
  87.             }
  88.         }
  89.     } while (swapped);
  90.  
  91.     return exchanges;
  92. }
  93.  
  94. // Selection sort in ascending order; returns the number of exchanges
  95. int selectionSort(int array[], int size)
  96. {
  97.     // data dictionary
  98.     int startScan;                  // Position being filled on this pass
  99.     int index;                      // Loop counter that scans for the smallest
  100.     int minIndex;                   // Index of the smallest value found
  101.     int minValue;                   // The smallest value found
  102.     int exchanges = 0;              // Number of swaps made
  103.  
  104.     for (startScan = 0; startScan < size - 1; startScan++)
  105.     {
  106.         minIndex = startScan;
  107.         minValue = array[startScan];
  108.         for (index = startScan + 1; index < size; index++)
  109.         {
  110.             if (array[index] < minValue)
  111.             {
  112.                 minValue = array[index];
  113.                 minIndex = index;
  114.             }
  115.         }
  116.         if (minIndex != startScan)
  117.         {
  118.             array[minIndex] = array[startScan];
  119.             array[startScan] = minValue;
  120.             exchanges++;
  121.         }
  122.     }
  123.     return exchanges;
  124. }
  125.  
  126. // Prints the array on one line
  127. void displayArray(const int array[], int size)
  128. {
  129.     // data dictionary
  130.     int index;                      // Loop counter
  131.  
  132.     for (index = 0; index < size; index++)
  133.         cout << array[index] << " ";
  134.     cout << endl;
  135. }
Success #stdin #stdout 0s 5348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sorted array: 3 5 8 12 14 19 24 27 33 38 41 45 56 60 67 72 83 89 91 98 

Bubble sort exchanges:    90
Selection sort exchanges: 18
https://ideone.com/PGu7YM
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!