777

#include<iostream>
#include<cstdlib>

using namespace std;

void fill ( int *a, int n){
    for (int i = 0; i < n; i++){
        *(a + i) = 1 + rand () % n;
    }
}

void show ( int *a, int n){
    for (int i = 0; i < n; i++){
        cout << *(a + i) << " ";
    }
    cout << endl;
}

void bubble_sort ( int *a, int n){
    for (int i = 0; i < (n - 1); i++){
        bool swap = false;
        for (int j = 0; j < (n - i) - 1; j++){
            if ( *(a + j) > *(a + j + 1 )){
                int b = *(a + j);
                *(a + j) = *(a + j + 1);
                *(a + j + 1) = b;
                swap = true;
            }
        }
        if (!swap)
        break;
    }

}

bool is_sorted (int *a, int n){
    int index = 0;
    for (int i = 0; i < n; i++){
        if ( a[i] < a[i+1]){
            index++;
        }
    }
    if (index == n){
       cout << "Sorted" << endl;
       return true;
    }
    else {
        cout << "Not sorted" << endl;
        bubble_sort (a, n);
        return false;
    }
}

int main ()
{
    int n;
    cout << "Size: ";
    cin >> n;
    int *a = new int [n];
    fill (a, n);
    show (a, n);
    is_sorted (a, n);
    show (a, n);
    delete [] a;
    return 0;
}