#include <iostream>
#include <ctime>

using namespace std;

void OutPut(int *arr, int lenght) {
    cout << "\n";
    for (int i = 0; i < lenght; ++i) {
        cout << arr[i] << " ";
    }
}

int *Sorting(int *arr, int lenght) {
    // Сортировка массива
    int complexity = 0;
    int transposition = 0;
    for (int start_index = 0; start_index < lenght - 1; ++start_index) {
        // Найменьший элемент - Первый (по условию)
        int smallest_index = start_index;
        // Ищем элемент меньше в остальной части массива
        for (int current_index = start_index; current_index < lenght; ++current_index) {
            // Если текущий элеммент меньше найменьшего
            if (arr[current_index] < arr[smallest_index]) {
                // Запоминаем его
                smallest_index = current_index;
                complexity += 1;
            }
            transposition += 1;
        }
        std::swap(arr[start_index], arr[smallest_index]);
    }
    cout << "Transposition: " << transposition << " Comparison:" << complexity;
    return arr;
}

int main() {
    srand(time(0));
    int lenght = 5;
    int arr[lenght];
    int arr_copy[lenght];
    int increase_arr[] = {1, 2, 5, 7, 10};
    int decrease_arr[] = {10, 9, 5, 3, 0};

    // Заполнение массива
    for (int i = 0; i < lenght - 1; ++i) {
        arr[i] = rand() % 10;
    }
    // Copy
    for (int i = 0; i < lenght - 1; ++i) {
        arr_copy[i] = arr[i];
    }

    // Вывод массива
    OutPut(arr, lenght);

    // Сортировка
    //int *complexity = new int (1);
    cout << "\n" << "Random: \n";
    int *sort_array = Sorting(arr, lenght);
    cout << "\n" << "Increase: \n";
    int *inc_arr = Sorting(increase_arr, 5);
    cout << "\n" << "Decrease: \n";
    int *dec_arr = Sorting(decrease_arr, 5);
    // Вывод массива
    OutPut(arr_copy, lenght);
    OutPut(sort_array, lenght);
    OutPut(inc_arr, lenght);
    OutPut(dec_arr, lenght);

    return 0;
}