E' esattamente quello a cui avevo pensato anche io. Probabilmente si potrebbe trovare anche qualcosa di più elegante, ma la soluzione che proponevi tu è valida comunque. Devi semplicemente fare un "controllo in avanti" nel ciclo for interno: se in un qualsiasi momento hai che un a[j-1] risulti essere maggiore di a[j], l'array non è ordinato, quindi non puoi arrestare il ciclo (e quella variabile booleana di cui dicevi magari la setti a "falso", ossia 0). Se invece per ogni j risulta a[j-1] < a[j], allora l'array è ordinato e non hai motivo di procedere oltre. In questo caso, setti a "vero" (1) la variabile booleana ed esci. L'istruzione break può esserti utile per interrompere un ciclo.