#include <iostream>
#include <fstream>

using namespace std;

void insertionSort(int x[], int n){
    for (int i = 1; i < n; ++i) {
        for (int j = i; j > 0 && x[j - 1] > x[j]; --j) {
            swap(x[j-1], x[j]);
        }
    }

    /*
    int i, j;
    for(i = 1; i < n; i++){
        int temp = x[i];
        for (j = i-1; j >= 0 && x[j - 1] > temp; j--){
            x[j] = x[j - 1];
            if(x[j] > temp){
                x[j+1] = x[j];
            }else{
                x[j+1] = temp;
                break;
            }

        }
        x[j] = temp;
    }
    */
}

void display(int x[], int length){
    for(int i = 0; i < length; i++){
        cout << x[i] << " ";
    }
    cout << endl;
}

int main() {
    int count, index = 0, temp;
    ifstream data("hw3.dat");
    if (data.is_open()) {
        cout << endl << "File opened successfully." << endl;
    }
    data >> count;
    cout << "Number of elements: " << count << endl << "========================" << endl;
    int *arr = new int[count];
    cout << "Original data: ";
    while (data >> temp) {
        arr[index] = temp;
        temp = 0;
        index++;
    }
    //int test [] = {8, 1, 11, 2, 10, 9, 3, 4, 7, 6, 5};
    display(arr, count);
    insertionSort(arr, count);
    cout << "After sorting: ";
    display(arr, count);
    cout << endl;
    delete[] arr;
}