#include <iostream>
#include <cstdlib>

using namespace std;

bool generate_array_of_random_numbers(int* &arr, int n, int a, int b);
void show_array(int* arr, int n);
bool check_if_nondescending(int *arr, int n);
int find_max_el(int *arr, int n);
int find_min_el(int *arr, int n);
void selectionsort(int *arr, int n);
void revselectionsort(int *arr, int n);
void bublesort(int *arr, int n);
void revbublesort(int *arr, int n);
void insertionsort(int *arr, int n);
void revinsertionsort(int *arr, int n);


int main()
{
    int n, a, b, opcja;
    int *arr=nullptr;
    cout << "podaj rozmiar tablicy" << endl;
    cin >> n;
    cout << "podaj poczatek przedzialu" << endl;
    cin >> a;
    cout << "podaj koniec przedzialu" << endl;
    cin >> b;
   cout << "" << endl;
    if(generate_array_of_random_numbers( arr, n, a, b)==1) {
            show_array(arr, n);
            cout << "" << endl;}
    else {
        cout << " niepoprawna tablica " << endl;}

    if(check_if_nondescending(arr, n) == 1){
        cout << "Tablica jest niemalejaca" << endl;
    }
    else{
        cout <<"Elementy tablicy nie sa w kolejnosci niemalejacej" << endl;
    }


    cout << "najwiekszy indeks: " << find_max_el(arr, n) << endl;
    cout << "najmniejszy indeks: " << find_min_el(arr, n) << endl;

    cout << "Wybierz opcje:" << endl << "1 - sortowanie rosnace" << endl << "2 - sortowanie malejace" << endl;
    cin >> opcja;

    if(opcja==1){
    cout<< ""<< endl;
    selectionsort(arr, n);
    show_array(arr, n);
    cout << "" << endl;
    bublesort(arr, n);
    show_array(arr, n);
    cout << "" << endl;
    insertionsort(arr, n);
    show_array(arr, n);
    cout << "" << endl;}

    if(opcja==2){
    revselectionsort(arr, n);
    show_array(arr, n);
    cout << "" << endl;
    revbublesort(arr, n);
    show_array(arr, n);
    cout << "" << endl;
    revinsertionsort(arr, n);
    show_array(arr, n);}

    delete [] arr;
    return 0;}


bool generate_array_of_random_numbers(int* &arr, int n, int a, int b){
if(arr == nullptr){
    arr = new int[n];
int diff = b-a+1;
for( int i = 0; i<n; i++)
    arr[i]=a+rand()%diff;
return true;}
    else{
return false;
    }
}

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

bool check_if_nondescending(int *arr, int n){
if(arr == nullptr and n == 0)
    return true;
for(int i=0; i<n; i++)
    if(arr[i]>arr[i+1])
    return false;
return true;
}

int find_max_el(int *arr, int n){
//if(arr == nullptr or n == 0)
    //return -1;
int maxel = arr[0];
int imax = 0;
for (int i =0; i<n; i++)
if(arr[i] > maxel){
    maxel= arr[i];
    imax = i;
}
return imax;
}

int find_min_el(int *arr, int n){
//if(arr == nullptr or n == 0)
    //return -1;
int minel = arr[0];
int imin = 0;
for (int i =0; i<n; i++)
if(arr[i] < minel){
    minel= arr[i];
    imin = i;
}
return imin;
}

void selectionsort(int *arr, int n){
int max_in;
for(int i = n; i>1; i--){
    max_in=find_max_el(arr, i);
    swap(arr[i-1], arr[max_in]);
    }
}

void revselectionsort(int *arr, int n){
int min_in;
for(int i = n; i>1; i--){
    min_in=find_min_el(arr, i);
    swap(arr[i-1], arr[min_in]);
    }
}

void bublesort(int *arr, int n){
for(int i = n-1; i>0; i-- ){
    for( int j = 0; j<i; j++){
        if(arr[j]>arr[j+1])
        swap(arr[j], arr[j+1]);}
        }
}

void revbublesort(int *arr, int n){
for(int i = n-1; i>0; i-- ){
    for( int j = 0; j<i; j++){
        if(arr[j]<arr[j+1])
        swap(arr[j], arr[j+1]);}
        }
}

void insertionsort(int *arr, int n){
int temp, j;
for(int i=n-2; i>=0; i--){
    j = i;
    temp = arr[j];
    while(temp > arr[j+1] and j < n-1){
        arr[j] = arr[j+1];
        j++;
    }
    arr[j] = temp;}
}

void revinsertionsort(int *arr, int n){
int temp, j;
for(int i=n-2; i>=0; i--){
    j = i;
    temp = arr[j];
    while(temp < arr[j+1] and j < n-1){
        arr[j] = arr[j+1];
        j++;
    }
    arr[j] = temp;}
}