#include<iostream>

using namespace std;

// Function to perform Selection Sort
void selection_sort(int n, int arr[])
{
   // Display the sorting method being used
   cout << "selection sort" << endl;

   // Variables to count comparisons and swaps
   int cnt_comp = 0, cnt_sw = 0;

   // Move the boundary of the unsorted portion one step at a time
   for(int j = 0; j < n - 1; j++)
   {
      // Assume the current position contains the smallest element
      int smallest = j;

      // Search for the smallest element in the remaining unsorted array
      for(int i = j + 1; i < n; i++)
      {
         // Compare current element with the current smallest element
         if(arr[i] < arr[smallest])
            smallest = i; // Update index of the smallest element found
      }

      // Swap the smallest element with the first unsorted element
      int tmp = arr[j];
      arr[j] = arr[smallest];
      arr[smallest] = tmp;

      // Increment swap counter
      cnt_sw++;
   }

   // Display the number of comparisons performed
   // (Note: cnt_comp is declared but not incremented in this code)
   cout << "Number of comparisons: " << cnt_comp << endl;

   // Display the number of swaps performed
   cout << "Number of exchange: " << cnt_sw << endl;
}

int main()
{
   // Size of the array
   int n = 100;

   // Declare an array of 100 elements
   int arr[100];

   // Initialize array in descending order (worst-case style input)
   for(int i = 0; i < 100; i++)
      arr[i] = 100 - i;

   // Sort the descending array
   selection_sort(n, arr);

   // Reinitialize array in ascending order (already sorted input)
   for(int i = 0; i < 100; i++)
      arr[i] = i;

   // Sort the already sorted array
   selection_sort(n, arr);

   // Print the final array contents
   for(int i = 0; i < 100; i++)
   {
      cout << arr[i] << " ";
   }

   return 0;
}