#include <string.h>

/* partition

   pre: list is an array of len elements.
   post: list is rearranged such that (pivot is a randomly chosen element)
     list[0] ... list[pivot-1] < list[pivot]
     list[pivot+1] ... list[len-1] > list[pivot]

   returns the index of the pivot.
*/

int partition(int *list, int len)
{
  int tmp; // for swapping

  int pivot = random(0, len-1);
  int pivot_val = list[pivot];
  int final_pivot = 0;

  // move pivot to end by swaping
  tmp = list[pivot]
  list[pivot] = list[len-1];  
  list[len-1] = tmp;

  // move items less than pivot_val to front of array and 
  // keep advancing the final_pivot point
  for (int i=0; i < len-1; i++) {
    if ( list[i] < pivot_val ) {
      // swap swap(list[i], list[final_pivot]);
      tmp = list[i]
      list[i] = list[final_pivot];  
      list[final_pivot] = tmp;
      final_pivot++;
    }
  }

  // move pivot to final place
  // swap(list[len-1], list[final_pivot]);
  tmp = list[len-1]
  list[len-1] = list[final_pivot];  
  list[final_pivot] = tmp;

  return final_pivot;
}

/* quicksort

   pre: list is an array of len elements.
   post: list is in sorted (ascending) order
*/

void quicksort(int *list, int len)
{
  if (len > 1) {
    int pivot = partition(list, len);
    quicksort(list, pivot);
    quicksort(list + pivot + 1, len - pivot - 1);
  }
}

unsigned long start_time;
unsigned long stop_time;
     
void start_clock() {
  start_time = micros();
}
     
unsigned long int stop_clock() {
  unsigned long elapsed_time;
  stop_time = micros();
  elapsed_time = stop_time - start_time;
  Serial.print("Elapsed time ");
  Serial.print(elapsed_time);
  Serial.println(" uS");
  return elapsed_time;
}
     
byte is_sorted(int *l, int len) {
  for (int i=0; i < len-1; i++) {
    if ( l[i] > l[i+1] ) { return 0; }
  }
  return 1;
}
     
void display_list(int *l, int len) {
  for (int i=0; i < len; i++ ) { 
    Serial.print(l[i]); Serial.print(" "); 
  }
}
     
void setup() {
  Serial.begin(9600);
      
  for (int len = 100; len < 3000; len += 200) {
    Serial.print("Testing with len "); Serial.println(len);
     
    int l[len];
          
    for (int i=0; i < len; i++ ) { l[i] = random(100); }
          
    //Serial.println("In:");
    //display_list(l, len);
    //Serial.println("");

    start_clock();
    quicksort(l, len);
    stop_clock();
     
    //Serial.println("Out:");
    //display_list(l, len);
    //Serial.println("");
          
    if ( is_sorted(l, len) ) {
      Serial.println("Success: list is sorted");
    }
    else {
      Serial.println("Error: list not sorted!");
    }
     
  }
}
     
void loop() {
}