/**
Bubble sort

Se traverseaza sirul si se compara doar elemente aflate unul langa altul
(si daca e cazul se interschimba).

Observam ca astfel maximul, odata intalnit va fi plimbat pana la final.
Asadar la o trecere prin sir e garantat ca ducem maximul la final.

In felul asta la a doua trecere se va mai duce si al doilea maxim la locul lui
si tot asa pana cand dupa maxim n-1 treceri sirul se sorteaza.

Strategia de implementare: la trecerea prin sir se si verifica daca s-a facut
vreo interschimbare iar cand observam ca nu s-a facut niciuna la o trecere
ne putem opri, caci sirul este sortat.

Complexitate de ordin n^2

Pe cazul cel mai defavorabil, adica sirul este descrescator, se fac n
treceri deci se ajunge la n^2.
Insa, daca sirul este sortat se trece o singura data si se opreste.
Acest algoritm este tine cont de structura sirului fiind mai bun cand sirul este sortat.

**/
#include <fstream>

using namespace std;
int v[500001];
int n, i, j, sortat;
int main () {
    ifstream fin("algsort.in");
    ofstream fout("algsort.out");

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    do {
        sortat = 1;
        for (i=1;i<n;i++)
            if (v[i]>v[i+1]) {
                swap(v[i], v[i+1]);
                sortat = 0; /// am facut macar o interschimbare la aceasta trecere
                            /// insemnand ca sirul nu e inca sortat deci voi mai face o trecere
            }

    } while(!sortat);

    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";


    return 0;
}