#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;
}

I2luY2x1ZGU8aW9zdHJlYW0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcGVyZm9ybSBTZWxlY3Rpb24gU29ydAp2b2lkIHNlbGVjdGlvbl9zb3J0KGludCBuLCBpbnQgYXJyW10pCnsKICAgLy8gRGlzcGxheSB0aGUgc29ydGluZyBtZXRob2QgYmVpbmcgdXNlZAogICBjb3V0IDw8ICJzZWxlY3Rpb24gc29ydCIgPDwgZW5kbDsKCiAgIC8vIFZhcmlhYmxlcyB0byBjb3VudCBjb21wYXJpc29ucyBhbmQgc3dhcHMKICAgaW50IGNudF9jb21wID0gMCwgY250X3N3ID0gMDsKCiAgIC8vIE1vdmUgdGhlIGJvdW5kYXJ5IG9mIHRoZSB1bnNvcnRlZCBwb3J0aW9uIG9uZSBzdGVwIGF0IGEgdGltZQogICBmb3IoaW50IGogPSAwOyBqIDwgbiAtIDE7IGorKykKICAgewogICAgICAvLyBBc3N1bWUgdGhlIGN1cnJlbnQgcG9zaXRpb24gY29udGFpbnMgdGhlIHNtYWxsZXN0IGVsZW1lbnQKICAgICAgaW50IHNtYWxsZXN0ID0gajsKCiAgICAgIC8vIFNlYXJjaCBmb3IgdGhlIHNtYWxsZXN0IGVsZW1lbnQgaW4gdGhlIHJlbWFpbmluZyB1bnNvcnRlZCBhcnJheQogICAgICBmb3IoaW50IGkgPSBqICsgMTsgaSA8IG47IGkrKykKICAgICAgewogICAgICAgICAvLyBDb21wYXJlIGN1cnJlbnQgZWxlbWVudCB3aXRoIHRoZSBjdXJyZW50IHNtYWxsZXN0IGVsZW1lbnQKICAgICAgICAgaWYoYXJyW2ldIDwgYXJyW3NtYWxsZXN0XSkKICAgICAgICAgICAgc21hbGxlc3QgPSBpOyAvLyBVcGRhdGUgaW5kZXggb2YgdGhlIHNtYWxsZXN0IGVsZW1lbnQgZm91bmQKICAgICAgfQoKICAgICAgLy8gU3dhcCB0aGUgc21hbGxlc3QgZWxlbWVudCB3aXRoIHRoZSBmaXJzdCB1bnNvcnRlZCBlbGVtZW50CiAgICAgIGludCB0bXAgPSBhcnJbal07CiAgICAgIGFycltqXSA9IGFycltzbWFsbGVzdF07CiAgICAgIGFycltzbWFsbGVzdF0gPSB0bXA7CgogICAgICAvLyBJbmNyZW1lbnQgc3dhcCBjb3VudGVyCiAgICAgIGNudF9zdysrOwogICB9CgogICAvLyBEaXNwbGF5IHRoZSBudW1iZXIgb2YgY29tcGFyaXNvbnMgcGVyZm9ybWVkCiAgIC8vIChOb3RlOiBjbnRfY29tcCBpcyBkZWNsYXJlZCBidXQgbm90IGluY3JlbWVudGVkIGluIHRoaXMgY29kZSkKICAgY291dCA8PCAiTnVtYmVyIG9mIGNvbXBhcmlzb25zOiAiIDw8IGNudF9jb21wIDw8IGVuZGw7CgogICAvLyBEaXNwbGF5IHRoZSBudW1iZXIgb2Ygc3dhcHMgcGVyZm9ybWVkCiAgIGNvdXQgPDwgIk51bWJlciBvZiBleGNoYW5nZTogIiA8PCBjbnRfc3cgPDwgZW5kbDsKfQoKaW50IG1haW4oKQp7CiAgIC8vIFNpemUgb2YgdGhlIGFycmF5CiAgIGludCBuID0gMTAwOwoKICAgLy8gRGVjbGFyZSBhbiBhcnJheSBvZiAxMDAgZWxlbWVudHMKICAgaW50IGFyclsxMDBdOwoKICAgLy8gSW5pdGlhbGl6ZSBhcnJheSBpbiBkZXNjZW5kaW5nIG9yZGVyICh3b3JzdC1jYXNlIHN0eWxlIGlucHV0KQogICBmb3IoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspCiAgICAgIGFycltpXSA9IDEwMCAtIGk7CgogICAvLyBTb3J0IHRoZSBkZXNjZW5kaW5nIGFycmF5CiAgIHNlbGVjdGlvbl9zb3J0KG4sIGFycik7CgogICAvLyBSZWluaXRpYWxpemUgYXJyYXkgaW4gYXNjZW5kaW5nIG9yZGVyIChhbHJlYWR5IHNvcnRlZCBpbnB1dCkKICAgZm9yKGludCBpID0gMDsgaSA8IDEwMDsgaSsrKQogICAgICBhcnJbaV0gPSBpOwoKICAgLy8gU29ydCB0aGUgYWxyZWFkeSBzb3J0ZWQgYXJyYXkKICAgc2VsZWN0aW9uX3NvcnQobiwgYXJyKTsKCiAgIC8vIFByaW50IHRoZSBmaW5hbCBhcnJheSBjb250ZW50cwogICBmb3IoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspCiAgIHsKICAgICAgY291dCA8PCBhcnJbaV0gPDwgIiAiOwogICB9CgogICByZXR1cm4gMDsKfQ==