#include <perms.h>

//          Edinburgh IMP77 Compiler - Version 8.4
//
//     1  ! microsoft copilot "write a quicksort function in the Imp77 language"
//     2  %begin

int main(int argc, char **argv) { /*%begin*/
  _imp_initialise(argc, argv);

  //     3     %routine quicksort(%integer %array %name a, %integer left, %integer right)

  void QUICKSORT(int *A, int LEFT, int RIGHT) {
    //     4        %integer i, j, pivot, temp

    int I;
    int J;
    int PIVOT;
    int TEMP;

    //     5        i = left

    I = LEFT;

    //     6        j = right

    J = RIGHT;

    //     7        pivot = a((left + right) // 2)

    PIVOT = A[/*BUG*/ ((long)(LEFT + RIGHT) / (long)2)];

    //     8        %cycle

  L_0001:;

  //     9           i = i + 1 %while a(i) < pivot

  L_0002:;
    if (A[/*BUG*/ I] >= PIVOT) goto L_0003;
    I = I + 1;
    goto L_0002;
  L_0003:;

  //    10           j = j - 1 %while a(j) > pivot

  L_0004:;
    if (A[/*BUG*/ J] <= PIVOT) goto L_0005;
    J = J - 1;
    goto L_0004;
  L_0005:;

  //    11           %exit %if i > j

    if (I <= J) goto L_0006;
    goto L_0007;
  L_0006:;

  //    12           temp = a(i)

    TEMP = A[/*BUG*/ I];

    //    13           a(i) = a(j)

    A[/*BUG*/ I] = A[/*BUG*/ J];

    //    14           a(j) = temp

    A[/*BUG*/ J] = TEMP;

    //    15           i = i + 1

    I = I + 1;

    //    16           j = j - 1

    J = J - 1;

    //    17        %repeat

    goto L_0001;
  L_0007:;

  //    18        quicksort(a, left, j) %if left < j

    if (LEFT >= J) goto L_0008;
    QUICKSORT(A, LEFT, J);
  L_0008:;

  //    19        quicksort(a, i, right) %if i < right

    if (I >= RIGHT) goto L_0009;
    QUICKSORT(A, I, RIGHT);
  L_0009:;

  //    20     %end

    return;
  } /* end of QUICKSORT */

  //    21     %own %integer %array data(0 : 9) = 6, 5, 4, 3, 2, 1, 7, 8, 9, 0

  static int DATA[10] = {6, 5, 4, 3, 2, 1, 7, 8, 9, 0};
  struct _imp_dv DATA_dv = {DATA, sizeof(int) /*, dims, <bounds> */};

  //    22     %integer i

  int I;

  //    23
  //    24     printstring("Before: "); write(data(i),-1) %for i = 0,1,9; newline

  _imp_PRINTSTRING(_imp_str_literal("Before: "));
  // %for I = 0, 1, 9 %cycle
  {
    I = -1;
  L_000A:
    if (I == 9) goto L_000B;
    I += 1;
    _imp_WRITE(DATA[I], -1);
    goto L_000A;
  }

L_000B:;
  _imp_NEWLINE();

  //    25     quicksort(data, 0, 9)

  QUICKSORT(DATA, 0, 9);

  //    26     printstring("After:  "); write(data(i),-1) %for i = 0,1,9; newline

  _imp_PRINTSTRING(_imp_str_literal("After:  "));
  // %for I = 0, 1, 9 %cycle
  {
    I = -1;
  L_000D:
    if (I == 9) goto L_000E;
    I += 1;
    _imp_WRITE(DATA[I], -1);
    goto L_000D;
  }

L_000E:;
  _imp_NEWLINE();

  //    27
  //    28  %end %of %program

  _imp_stop(0);
  return 0;
end_0:;
}