/*
 Outline of Quick Sort
 */

/* 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)
{
  // select a pivot index and initalize the final_pivot index
  int final_pivot = 0;

  // move pivot index to end of the list
 
  // move items less than pivot_val to front of array and 
  // keep advancing the final_pivot point

  // move pivot to final place

  // return the final_pivot index
  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 is greater than one, recursively call quicksort
}

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() {
}