title: quicksort program with segmentation fault
body: <p>Today I was going through the quick sort algorithm from Algorithms in C by R.Sedgewick. </p>
  
  <p>I understood a good chunk of how the algorithm works. The coding part just confused me a bit and I got a segmentation fault at the end. Here is the code:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  void quicksort(int[], int, int); // prototype
  
  void quicksort(int a[], int l, int r) // What is the value of l. Why hasn't the author 
                                        // mentioned it. Is it the size of the array? 
  {
      int i, j, v, t;
      if(r &gt; l)
      {
          v = a[r];
          i = l - 1; // What is l here? Is it the size if yes look at first while statement
          j = r;
  
          for(;;)
          {
  
              /*The algorithm says: scan from right until an element &lt; a[r] is found. Where 
                r is the last position in the array. But while checking in the second while
                loop elements &gt; a[r] is searched */
  
              while (a[++i] &lt; v); // How can you increment again after reaching end of arrray
                                  // size if l is the size of the array
              while (a[--j] &gt; v);
              if(i &gt;= j) break;
              t = a[i]; a[i] = a[j]; a[j] = t;
          }
      }
  
      t = a[i]; a[i] = a[r]; a[r] = t;
  
      quicksort(a, l, i - 1);
      quicksort(a, i + 1, r);
  
      return;
  }
  
  int main()
  {
      int i, a[10]; // assuming size is 10
  
      for(i = 0; i &lt; 10; i++)
      {
          scanf("%d", &amp;a[i]);
      }
  
      int l = 10; // I am passing size of the array
      int r = 9; // position of last element
  
      quicksort(a, l, r);
      return 0;
  }
  </code></pre>
  
  <p>The error is like this. Suppose if I enter 10 elements and then press enter, this is what happens:</p>
  
  <pre><code>1 4 8 2 3 6 4 7 10 9
  segmentation fault.
  
  process returned 139(0x8b)
  </code></pre>
  
  <p>This is what debugger returned:</p>
  
  <pre><code>Breakpoint 1, quicksort (a=0xbffff808, l=0, r=0) at quick.c:11
  11      if(r &gt; 1)
  (gdb) c
  Continuing.
  
  Program received signal SIGSEGV, Segmentation fault.
  0x080484fb in quicksort (a=0xbffff808, l=0, r=0) at quick.c:28
  28      t = a[i]; a[i] = a[r]; a[r] = t;
  (gdb) c
  Continuing.
  
  Program terminated with signal SIGSEGV, Segmentation fault.
  The program no longer exists.
  (gdb) c
  The program is not being run.
  </code></pre>
  
  <p>The correct way to do the above program is this. There is nothing with the left and right pointer. The left pointer should point to 0th location and right pointer to n - 1 location, if array occupies n memory locations. I had done a silly mistake by not including the recursive function of quicksort inside the if condition. Hence all that headache. The correct program is:</p>
  
  <pre><code>/* Working quicksort
   * Robert sedgewick best
   */
  
  #include &lt;stdio.h&gt;
  
  void quicksort(int[], int, int); // prototype
  
  void quicksort(int a[], int l, int r) 
  {
      int i, j, v, t;
      if(r &gt; l)
      {
          v = a[r];
          i = l - 1;
          j = r;
  
          for(;;)
         {
              while (a[++i] &lt; v); 
              while (a[--j] &gt; v);
  
              if(i &gt;= j) break;
              t = a[i]; a[i] = a[j]; a[j] = t;
  
          } // End for here
  
  
      t = a[i]; a[i] = a[r]; a[r] = t;
  
      quicksort(a, l, i - 1);
      quicksort(a, i + 1, r);
  
      } /* End if here. That is include the recursive
           functions inside the if condition. Then it works 
           just fine. */
  
      return;
  }
  
  int main()
  {
      int i, a[5]; // assuming size is 10
  
      for(i = 0; i &lt; 5; i++)
      {
          scanf("%d", &amp;a[i]);
      }
  
      int l = 0; // I am passing size of the array
      int r = 4; // position of last element
  
      quicksort(a, l, r);
  
         int s;
  
      for(s = 0; s &lt; 5; s++)
      {
          printf("%d ", a[s]);
      }
      return 0;
  }
  </code></pre>