---

#include <iostream>
#include <vector>
#include <cstdlib>  // Для rand(), srand()
#include <ctime>    // Для clock(), time(), CLOCKS_PER_SEC
#include <algorithm> // Для swap()

using namespace std;

// --- ФУНКЦИЯ ЗАПОЛНЕНИЯ МАССИВА СЛУЧАЙНЫМИ ЧИСЛАМИ ---
void fillRandom(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = rand() % 10000; // Числа от 0 до 9999
    }
}

// --- 1. ПУЗЫРЬКОВАЯ СОРТИРОВКА (Обычная) ---
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// --- 2. ПУЗЫРЬКОВАЯ СОРТИРОВКА (Оптимизированная) ---
void bubbleSortOptimized(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // Флаг: были ли перестановки
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Если перестановок нет — массив отсортирован
    }
}

// --- ГЛАВНАЯ ФУНКЦИЯ ---
int main() {
    srand(time(0)); // Инициализация генератора случайных чисел

    cout << "Исследование эффективности алгоритмов сортировки\n";
    cout << "------------------------------------------------\n";

    // Тестируем массивы от 100 до 1000 элементов с шагом 100
    for (int n = 100; n <= 1000; n += 100) {
        cout << "Размер массива: " << n << " элементов\n";

        vector<int> original(n);
        fillRandom(original); // Создаем случайный массив

        vector<int> temp; 
        clock_t start, end;
        double time_spent;
        
        int repeats = 1000; // Запускаем 1000 раз для точного замера

        // 1. Замер Обычной пузырьковой сортировки
        start = clock();
        for (int k = 0; k < repeats; k++) {
            temp = original; // Копируем оригинал перед каждым запуском
            bubbleSort(temp);
        }
        end = clock();
        time_spent = double(end - start) / CLOCKS_PER_SEC / repeats;
        cout << "  Пузырьковая (обычная):  " << time_spent << " сек.\n";

        // 2. Замер Оптимизированной пузырьковой сортировки
        start = clock();
        for (int k = 0; k < repeats; k++) {
            temp = original; 
            bubbleSortOptimized(temp);
        }
        end = clock();
        time_spent = double(end - start) / CLOCKS_PER_SEC / repeats;
        cout << "  Пузырьковая (оптимиз.): " << time_spent << " сек.\n\n";
    }

    cout << "Исследование завершено!\n";
    return 0;
}