#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

void print_list(const char *label, const int a[], int n) {
    printf("%s:", label);
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
}

int is_sorted(const int a[], int n) {
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            return 0;
        }
    }
    return 1;
}

int main(int argc, char *argv[]) {
    int thread_count = 4;
    int n = 20000;
    if (argc > 1) {
        thread_count = (int)strtol(argv[1], NULL, 10);
    }
    if (argc > 2) {
        n = (int)strtol(argv[2], NULL, 10);
    }

    int *a = malloc(n * sizeof(int));
    srandom(1);
    for (int i = 0; i < n; i++) {
        a[i] = (int)(random() % 1000);
    }
    if (n <= 20) {
        print_list("Before", a, n);
    }

    double start = omp_get_wtime();
#   pragma omp parallel num_threads(thread_count) \
        default(none) shared(a, n)
    for (int phase = 0; phase < n; phase++) {
        if (phase % 2 == 0) {
#           pragma omp for
            for (int i = 1; i < n; i += 2) {
                if (a[i - 1] > a[i]) {
                    int tmp = a[i - 1];
                    a[i - 1] = a[i];
                    a[i] = tmp;
                }
            }
        } else {
#           pragma omp for
            for (int i = 1; i < n - 1; i += 2) {
                if (a[i] > a[i + 1]) {
                    int tmp = a[i + 1];
                    a[i + 1] = a[i];
                    a[i] = tmp;
                }
            }
        }
    }
    double elapsed = omp_get_wtime() - start;

    if (n <= 20) {
        print_list("After ", a, n);
    }
    printf("Values: %d\n", n);
    printf("Threads: %d\n", thread_count);
    printf("Sorted: %s\n", is_sorted(a, n) ? "yes" : "NO");
    printf("Elapsed time: %.3f seconds\n", elapsed);
    free(a);
    return 0;
}