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

I2luY2x1ZGU8aW9zdHJlYW0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcGVyZm9ybSBJbnNlcnRpb24gU29ydAp2b2lkIGluc2VydGlvbl9zb3J0KGludCBuLCBpbnQgYXJyW10pCnsKICAgY291dCA8PCAiaW5zZXJ0aW9uIHNvcnQiIDw8IGVuZGw7CgogICAvLyBWYXJpYWJsZXMgdG8gY291bnQgY29tcGFyaXNvbnMgYW5kIGV4Y2hhbmdlcyAoc2hpZnRzKQogICBpbnQgY250X2NvbXAgPSAwLCBjbnRfZXggPSAwOwoKICAgLy8gVHJhdmVyc2UgdGhlIGFycmF5IHN0YXJ0aW5nIGZyb20gdGhlIHNlY29uZCBlbGVtZW50CiAgIGZvcihpbnQgaiA9IDE7IGogPCBuOyBqKyspCiAgIHsKICAgICAgLy8gU3RvcmUgdGhlIGN1cnJlbnQgZWxlbWVudCBhcyB0aGUga2V5CiAgICAgIGludCBrZXkgPSBhcnJbal07CgogICAgICAvLyBJbmRleCBvZiB0aGUgcHJldmlvdXMgZWxlbWVudAogICAgICBpbnQgaSA9IGogLSAxOwoKICAgICAgLy8gTW92ZSBlbGVtZW50cyB0aGF0IGFyZSBncmVhdGVyIHRoYW4ga2V5CiAgICAgIC8vIG9uZSBwb3NpdGlvbiBhaGVhZCBvZiB0aGVpciBjdXJyZW50IHBvc2l0aW9uCiAgICAgIHdoaWxlKGkgPj0gMCAmJiBhcnJbaV0gPiBrZXkpCiAgICAgIHsKICAgICAgICAgYXJyW2kgKyAxXSA9IGFycltpXTsgLy8gU2hpZnQgZWxlbWVudCB0byB0aGUgcmlnaHQKICAgICAgICAgaS0tOwoKICAgICAgICAgLy8gQ291bnQgY29tcGFyaXNvbiBhbmQgZXhjaGFuZ2UKICAgICAgICAgY250X2NvbXArKzsKICAgICAgICAgY250X2V4Kys7CiAgICAgIH0KCiAgICAgIC8vIENvdW50IHRoZSBmaW5hbCBjb21wYXJpc29uIHRoYXQgY2F1c2VzIGxvb3AgdGVybWluYXRpb24KICAgICAgY250X2NvbXArKzsKCiAgICAgIC8vIEluc2VydCB0aGUga2V5IGludG8gaXRzIGNvcnJlY3QgcG9zaXRpb24KICAgICAgYXJyW2kgKyAxXSA9IGtleTsKICAgfQoKICAgLy8gRGlzcGxheSBzdGF0aXN0aWNzCiAgIGNvdXQgPDwgIk51bWJlciBvZiBjb21wYXJpc29uczogIiA8PCBjbnRfY29tcCA8PCBlbmRsOwogICBjb3V0IDw8ICJOdW1iZXIgb2YgZXhjaGFuZ2U6ICIgPDwgY250X2V4IDw8IGVuZGw7Cn0KCmludCBtYWluKCkKewogICAvLyBTaXplIG9mIHRoZSBhcnJheQogICBpbnQgbiA9IDEwMDsKCiAgIC8vIEFycmF5IGRlY2xhcmF0aW9uIChjdXJyZW50bHkgdW5pbml0aWFsaXplZCkKICAgaW50IGFyclsxMDBdOwoKICAgLy8gRXhhbXBsZSBpbml0aWFsaXplZCBhcnJheSAodW5jb21tZW50IHRvIHRlc3QpCiAgIC8vIGludCBhcnJbNV0gPSB7NSwgMywgNiwgNywgMX07CgogICAvLyBDYWxsIGluc2VydGlvbiBzb3J0IGZ1bmN0aW9uIChjdXJyZW50bHkgY29tbWVudGVkIG91dCkKICAgLy8gaW5zZXJ0aW9uX3NvcnQobiwgYXJyKTsKCiAgIC8vIFByaW50IGFycmF5IGVsZW1lbnRzCiAgIC8vIE5vdGU6IFNpbmNlIGFyciBpcyB1bmluaXRpYWxpemVkLCBvdXRwdXQgd2lsbCBjb250YWluIGdhcmJhZ2UgdmFsdWVzCiAgIGZvcihpbnQgaSA9IDA7IGkgPCAxMDA7IGkrKykKICAgewogICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CiAgIH0KCiAgIHJldHVybiAwOwp9