#include<iostream>

using namespace std;

// Function to perform Insertion Sort
void insertion_sort(int n, int arr[])
{
   cout << "insertion sort" << endl;

   // Variables to count comparisons and exchanges (shifts)
   int cnt_comp = 0, cnt_ex = 0;

   // Traverse the array starting from the second element
   for(int j = 1; j < n; j++)
   {
      // Store the current element as the key
      int key = arr[j];

      // Index of the previous element
      int i = j - 1;

      // Move elements that are greater than key
      // one position ahead of their current position
      while(i >= 0 && arr[i] > key)
      {
         arr[i + 1] = arr[i]; // Shift element to the right
         i--;

         // Count comparison and exchange
         cnt_comp++;
         cnt_ex++;
      }

      // Count the final comparison that causes loop termination
      cnt_comp++;

      // Insert the key into its correct position
      arr[i + 1] = key;
   }

   // Display statistics
   cout << "Number of comparisons: " << cnt_comp << endl;
   cout << "Number of exchange: " << cnt_ex << endl;
}

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

   // Array declaration (currently uninitialized)
   int arr[100];

   // Example initialized array (uncomment to test)
   // int arr[5] = {5, 3, 6, 7, 1};

   // Call insertion sort function (currently commented out)
   // insertion_sort(n, arr);

   // Print array elements
   // Note: Since arr is uninitialized, output will contain garbage values
   for(int i = 0; i < 100; i++)
   {
      cout << arr[i] << " ";
   }

   return 0;
}