#include <stdio.h>
#include "linkedlist.h"
#include "ReadFile.h"
/*#include <stdlib.h> */
#include <time.h> /* needed for rand */

node *quickSort(node *linkedList) {
  node *firstList;
  node *secondList;
  node *compNode;
  int i;
  int lengthOfList;
  firstList = NULL;
  secondList = NULL;
  lengthOfList = length(linkedList);
  linkedList = getFirst(linkedList);
  switch (length(linkedList)) {
  case 1:
    return linkedList;
    break;
  case 2:
    compNode = getRandomElt(linkedList);
    compNode = newList(getCurrent(compNode));
    linkedList = deleteElt(linkedList, getCurrent(compNode));
  
    if (strcmp(getCurrent(linkedList), getCurrent(compNode)) > 0) {
      return meldTwo(compNode, linkedList);
    }
    else {
      return meldTwo(linkedList, compNode);
    }
    break;
  default:
    srand(time((time_t *) 0));
    compNode = getRandomElt(linkedList);
    compNode = newList(getCurrent(compNode));
    linkedList = deleteElt(linkedList, getCurrent(compNode));
    for (i = 1; lengthOfList > i; i++) {
      if (strcmp(getCurrent(linkedList), getCurrent(compNode)) > 0) {
        if (secondList == NULL) {
          secondList = newList(getCurrent(linkedList));
          /* listPrint(secondList); */
        }
        else {
          secondList = addToEnd(secondList, getCurrent(linkedList));
          /* listPrint(secondList); */
        }
      }
      else {
        if (firstList == NULL) {
          firstList = newList(getCurrent(linkedList));
          /*listPrint(firstList);*/
        }
        else {
          firstList = addToEnd(firstList, getCurrent(linkedList));
          /*listPrint(firstList);*/
        }
      }
      linkedList = getNext(linkedList);
      
    }
   
           if (firstList == NULL) {
      
      return meldTwo(compNode, quickSort(secondList));
    }
    else if (secondList == NULL) {
      return meldTwo(quickSort(firstList), compNode);
    }
    else {
    return meldThree(quickSort(firstList), compNode, quickSort(secondList));
    }
    break;
  }
}