//Insertion Sort
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int arr[] = { 21, 2 ,34, 8 ,0 };
    int number = 0, index = -1, number_at_index = 0;
    
    cout << "sorting started" << endl;
    for (int i = 0; i < (sizeof(arr)/ sizeof(arr[0])) - 1 ; i++) {
        if (arr[i] < arr[i + 1]) {
            continue;            
        }
        else {
            number = arr[i]; //number to change
            
            for(int j = i; j > 0; j--) {
                if (arr[j] > number) {
                    index++;
                }
            }

           number_at_index = arr[index];
           arr[index] = number;

           for (int k = index + 1; k < sizeof(arr) / sizeof(arr[0]) - 1; k++) {
                arr[k] = number_at_index;
                if (sizeof(arr[k + 1]) == 4) {
                    number_at_index = arr[k + 1];
                }
                else {
                    break;
                }
            }
        }

        index = -1;
        number_at_index = 0;
    }


    for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        cout << arr[i] << " ";
    }

}