// copied from K: tests/diverse/sortings.simple

function init(n) {
  var x[n];
  print("Type ",n," numbers: ");
  for (var i = 0; i <= n - 1; ++i) {
    x[i] = read();
  }
  print("Finished reading the ",n," numbers\n");
  return x;
}

function printArray(x) {
  print("\n");
  for (var i = 0; i <= sizeOf(x) - 1; ++i) {
    print(x[i]," ");
  }
  print("\n");
}

function reverse(x) {
  var n = sizeOf(x);
  for (var i = 0; i <= n/2 - 1; ++i) {
    var t = x[i];
    x[i] = x[n - i - 1];
    x[n - i - 1] = t;
  }
}

function map(m,f,x) {
  for (var i = 0; i <= sizeOf(f) - 1; ++i) {
    print(m[i]);
    f[i](x);
  }
}

function insertionSort(x) {
  for (var i = 1; i <= sizeOf(x) - 1; ++i) {
    var v = x[i], j = i - 1;
    while (j > 0 && x[j] > v) {  // doing the loop only up to 1
      x[j + 1] = x[j];
      j = j - 1;
    }
    if (x[0] > v) { 
      x[1] = x[0];
      x[0] = v;
    }
    else {
      x[j+1] = v;
    }
  }
}

function bubbleSort(v) {
  var n = sizeOf(v);
  for (var i = 0; i <= n - 1; ++i) {
    for (var j = 0; j <= n - 2; ++j) {
      if (v[j] > v[j+1]) {
        var t = v[j+1];
        v[j+1] = v[j];
        v[j] = t;
      }
    }
  }
}

function siftDown(x, root, bottom) {
  var done = false, maxChild;
  while (root*2 <= bottom && !done) {
    if (root*2 == bottom) {
      maxChild = root*2;
    }
    else {
      if (x[root*2] > x[root*2 + 1]) {
        maxChild = root*2;
      }
      else {
        maxChild = root*2 + 1;
      }
    }
    if (x[root] < x[maxChild]) {
      var t = x[root];
      x[root] = x[maxChild];
      x[maxChild] = t;
      root = maxChild;
    }
    else {
      done = true;
    }
  }
}

function heapSort(x) {
  var n = sizeOf(x), i = n/2 - 1;
  while (i >= 0) {
    siftDown(x, i, n - 1);
    i = i - 1;
  }
  i = n - 1;
  while (i >= 1 ) {
    var t = x[0];
    x[0] = x[i] ;
    x[i] = t;
    siftDown(x, 0, i - 1);
    i = i - 1;
  }
}

function main() {
  print("Size of the array to sort = ");
  var x = init(read()), m[11], f[11];
  m[ 0] = "The original unsorted array is:";
  f[ 0] = printArray;
  m[ 1] = "Reversing the array ... ";
  f[ 1] = reverse;
  m[ 2] = "Done!\nThe reversed array is:";
  f[ 2] = printArray;
  m[ 3] = "Sorting the array using insertion sort ... ";
  f[ 3] = insertionSort;
  m[ 4] = "Done!\nThe resulting array is:";
  f[ 4] = printArray;
  m[ 5] = "Reversing the array ... ";
  f[ 5] = reverse;
  m[ 6] = "Done!\nSorting the array using bubble sort ... ";
  f[ 6] = bubbleSort;
  m[ 7] = "Done!\nThe resulting array is:";
  f[ 7] = printArray;
  m[ 8] = "Reversing the array ... ";
  f[ 8] = reverse;
  m[ 9] = "Done!\nSorting the array using heap sort ... ";
  f[ 9] = heapSort;
  m[10] = "Done!\nThe resulting array is:";
  f[10] = printArray;
  map(m,f,x);
}