/* int input[] = {4, 1, 5, 9, 2, 6, 5, 3};
int n = sizeof input / sizeof *input;

bool test(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

void reorder(int arr[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = random(i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int sort(int arr[], int n) {
    int count = 0;

    while (!test(arr, n)) {
        count++;
        reorder(arr, n);
    }

    return count;
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        Serial.print(arr[i]);
        Serial.print(" ");
    }
    Serial.println();
}

void setup() {
    Serial.begin(9600);

    Serial.print("Initial array: ");
    print_array(input, n);

    int count = sort(input, n);

    Serial.print(count);
    Serial.println("");
    print_array(input, n);
}

void loop() {
}
*/

/*
Initial array: 4 1 5 9 2 6 5 3 
Sorted array: 1 2 3 4 5 5 6 9 
*/


int input[] = {4, 1, 5, 9, 2, 6,}; // 5, 3, }; 
int n = sizeof input / sizeof *input;

void setup() {
  Serial.begin(9600);

  Serial.print("Initial array: ");
  printArray(input, n);

  sort(input, n);

  Serial.print("Sorted array: ");
  printArray(input, n);
}

void loop() {
}

void sort(int *arr, int n) {
  while (!test(arr, n))
    shuffle(arr, n);
}

bool test(int *arr, int n) {
  for (int ii = 0; ii < n - 1; ii++) {
    if (arr[ii] > arr[ii + 1]) {
      return false;
    }
  }
  return true;
}

void shuffle(int *arr, int n) {
  for (int ii = n - 1; ii > 0; ii--) {
    int jj = random(ii + 1);
    int temp = arr[ii];
    arr[ii] = arr[jj];
    arr[jj] = temp;
  }
}

void printArray(int *arr, int n) {
  for (int ii = 0; ii < n; ii++) {
    Serial.print(arr[ii]);
    Serial.print(" ");
  }
  Serial.println();
}