title: Quicksort of Linked List in C
body: <p>Okay guys, after no success with gdb and valgrind, I humbly present my question to you. We were asked to implement a version of a quicksort in c, using the first element of the list as the pivot (to maintain comparability with a simple haskell implementation we did earlier in the semester). The LIST implementation was provided (make, print, and the structure definition), the rest is up to us. I am (surprise, surprise) receiving a segfault, but valgrind is turning up a HUGE number of errors as well as a stack overflow, so maybe some fresh eyes can help me.</p>
  
  <p>My code:</p>
  
  <pre><code>    #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  
  typedef struct CELL *LIST;
  struct CELL {
      int element;
      LIST next;
  };
  
  
  LIST MakeList();
  void PrintList(LIST);
  LIST qSort(LIST);
  int listLength(LIST);
  LIST combine(LIST, LIST, LIST);
  
  
  int main(){
     LIST list;
      printf ("enter a several numbers separated by spaces or returns and ended by Ctrl-D\n");
      list = MakeList();
      PrintList(qSort(list));
     return 0;
  }
  
  LIST qSort(LIST list){
     LIST current, pivot = list, temp = NULL;//use first element as pivot, start comparison at list-&gt;next
     LIST little, big, littleHead, bigHead;
     little = (LIST) malloc(sizeof(struct CELL));
     little-&gt;element = 0;
     little-&gt;next = NULL;
     littleHead = little;
     big = (LIST) malloc(sizeof(struct CELL));
     big-&gt;element = 0;
     big-&gt;next = NULL;
     bigHead = big;
  
     if(listLength(list) &lt;= 1){//base case
        return list;
     }
  //remove pivot by setting current to list-&gt;next
     current = list-&gt;next;
  
     do{
        if(current-&gt;element &lt;= pivot-&gt;element){
           little-&gt;element = current-&gt;element;
           little-&gt;next = (LIST) malloc(sizeof(struct CELL));
           little = little-&gt;next;
           little-&gt;next = NULL;
        }
        else{
           big-&gt;element = current-&gt;element;
           big-&gt;next = (LIST) malloc(sizeof(struct CELL));
           big = big-&gt;next;
           big-&gt;next = NULL;
        }
  
        current = current-&gt;next;
     }while(current != NULL);
  
     littleHead = qSort(littleHead);
     bigHead = qSort(bigHead);
  
     return combine(littleHead, bigHead, pivot);
  }
  
  int listLength(LIST list){
     int length = 0;
     LIST current = list;
     if(NULL==list){
        return length;
     }
     else{
        while(current != NULL){
           current = current-&gt;next;
           length++;
        }
     }
     return length;
  }
  
  
  
  LIST combine(LIST little, LIST big, LIST pivot){
     LIST temp = little;
     while(temp-&gt;next != NULL){
        temp = temp-&gt;next;
     }
     temp-&gt;next = pivot;
     pivot-&gt;next = big;
     return little;
  }
  
  LIST MakeList()
  {
      int x;
      LIST pNewCell;
  
      if (scanf("\%d", &amp;x) == EOF) return NULL;
      else {
          pNewCell = (LIST) malloc(sizeof(struct CELL));
          pNewCell-&gt;next = MakeList();
          pNewCell-&gt;element = x;
          return pNewCell;
      }
  }
  
  void PrintList(LIST list)
  {
      while (list != NULL) {
          printf("\%d\n", list-&gt;element);
          list = list-&gt;next;
      }
  }
  </code></pre>
  
  <p>And the valgrind output</p>
  
  <pre><code>==20391== Conditional jump or move depends on uninitialised value(s)
  ==20391==    at 0x804855D: qSort (2100assignment4.c:45)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==  Uninitialised value was created by a heap allocation
  ==20391==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
  ==20391==    by 0x8048574: qSort (2100assignment4.c:47)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==
  ==20391== Conditional jump or move depends on uninitialised value(s)
  ==20391==    at 0x804855D: qSort (2100assignment4.c:45)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==  Uninitialised value was created by a heap allocation
  ==20391==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
  ==20391==    by 0x8048574: qSort (2100assignment4.c:47)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==
  ==20391== Conditional jump or move depends on uninitialised value(s)
  ==20391==    at 0x804855D: qSort (2100assignment4.c:45)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==  Uninitialised value was created by a heap allocation
  ==20391==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
  ==20391==    by 0x8048574: qSort (2100assignment4.c:47)
  ==20391==    by 0x80485E0: qSort (2100assignment4.c:61)
  ==20391==    by 0x80484BD: main (2100assignment4.c:22)
  ==20391==
  ==20391== Stack overflow in thread 1: can't grow stack to 0xbe297ff4
  ==20391==
  ==20391== Process terminating with default action of signal 11 (SIGSEGV)
  ==20391==  Access not within mapped region at address 0xBE297FF4
  ==20391==    at 0x402BE35: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
  ==20391==  If you believe this happened as a result of a stack
  ==20391==  overflow in your program's main thread (unlikely but
  ==20391==  possible), you can try to increase the size of the
  ==20391==  main thread stack using the --main-stacksize= flag.
  ==20391==  The main thread stack size used in this run was 8388608.
  ==20391== Stack overflow in thread 1: can't grow stack to 0xbe297fe4
  ==20391==
  ==20391== Process terminating with default action of signal 11 (SIGSEGV)
  ==20391==  Access not within mapped region at address 0xBE297FE4
  ==20391==    at 0x4025430: _vgnU_freeres (in /usr/lib/valgrind/vgpreload_core-x86-linux.so)
  ==20391==  If you believe this happened as a result of a stack
  ==20391==  overflow in your program's main thread (unlikely but
  ==20391==  possible), you can try to increase the size of the
  ==20391==  main thread stack using the --main-stacksize= flag.
  ==20391==  The main thread stack size used in this run was 8388608.
  ==20391==
  ==20391== HEAP SUMMARY:
  ==20391==     in use at exit: 4,190,952 bytes in 523,869 blocks
  ==20391==   total heap usage: 523,869 allocs, 0 frees, 4,190,952 bytes allocated
  ==20391==
  ==20391== LEAK SUMMARY:
  ==20391==    definitely lost: 0 bytes in 0 blocks
  ==20391==    indirectly lost: 0 bytes in 0 blocks
  ==20391==      possibly lost: 0 bytes in 0 blocks
  ==20391==    still reachable: 4,190,952 bytes in 523,869 blocks
  ==20391==         suppressed: 0 bytes in 0 blocks
  ==20391== Rerun with --leak-check=full to see details of leaked memory
  ==20391==
  ==20391== For counts of detected and suppressed errors, rerun with: -v
  ==20391== ERROR SUMMARY: 261929 errors from 3 contexts (suppressed: 0 from 0)
  </code></pre>