#include <iostream>
#include <ctime>
#include <chrono>

using namespace std;

void gnomeSort(int arr[], int size);

void combSort(int *arr, int size);

int main() {

    int sizes[] = {1000, 10000, 20000, 40000, 80000, 100000, 200000};


    for (auto &size: sizes) {
        // Generate an array filled with random elements to be sorted by the algorithm
        srand(time(nullptr));
        // Create 5 different arrays with the same size and get the average time
        long total_time_gnome = 0;
        long total_time_comb = 0;
        for (int i = 0; i < 5; i++) {
            int arr[size];
            for (int j = 0; j < size; j++) {
                arr[j] = rand();
            }
            // Copy the array to be sorted by the comb sort
            int arr_comb[size];
            for (int j = 0; j < size; j++) {
                arr_comb[j] = arr[j];
            }

            // Start the timer
            auto start = chrono::high_resolution_clock::now();

            // Sort the array using gnome sort
            gnomeSort(arr, size);

            // Stop the timer
            auto stop = chrono::high_resolution_clock::now();

            // Timer for comb sort
            auto start2 = chrono::high_resolution_clock::now();

            // Sort the array using comb sort
            combSort(arr_comb, size);

            // Stop the timer
            auto stop2 = chrono::high_resolution_clock::now();

            // Calculate the time
            total_time_gnome += chrono::duration_cast<chrono::milliseconds>(stop - start).count();
            total_time_comb += chrono::duration_cast<chrono::milliseconds>(stop2 - start2).count();
        }
        cout << "Gnome sort: time for " << size << " elements: " << total_time_gnome / 5 << " milliseconds" << endl;
        cout << "Comb sort: time for " << size << " elements: " << total_time_comb / 5 << " milliseconds" << endl;

    }



    return 0;
}

void gnomeSort(int *arr, int size) {
    // Sort the array using gnome sort
    int index = 0;
    while (index < size) {
        if (index == 0) index++;
        if (arr[index] >= arr[index - 1]) {
            index++;
        } else {
            int temp;
            temp = arr[index];
            arr[index] = arr[index - 1];
            arr[index - 1] = temp;
            index--;
        }
    }
}

void combSort(int *arr, int size) {
    // Sort the array using comb sort
    int gap = size;
    bool swapped = true;
    while (gap != 1 || swapped) {
        gap = max(1, (int) (gap / 1.3));
        swapped = false;
        for (int i = 0; i < size - gap; i++) {
            if (arr[i] > arr[i + gap]) {
                int temp;
                temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                swapped = true;
            }
        }
    }
}