title: QuickSort sorting positive ints, sometimes first value is negative int after ordering
body: <p>I am implementing a QuickSort in C which pivot is variable (can be middle, median, or aleatory). It is selected inside an <code>switch</code> clause.</p>
  
  <p>My implementation is:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;math.h&gt;
  
  // swap two values
  void intercambio(int *arrayDatos, int inicio, int fin) {
      int temporal;
  
      temporal = arrayDatos[inicio];
      arrayDatos[inicio] = arrayDatos[fin];
      arrayDatos[fin] = temporal;
  }
  
  // calculate median
  int calcularMediana(int a[], int left, int right) { //Uses median of three partitioning technique
      int center = (left + right) / 2;
      if (a[center] &lt; a[left])
          intercambio(a, left, center);
      if (a[right] &lt; a[left])
          intercambio(a, left, right);
      if (a[right] &lt; a[center])
          intercambio(a, center, right);
  
      intercambio(a, center, right - 1); //since the largest is already in the right.
      return right - 1;
  }
  
  // arrayDatos is array to sorting
  // inicio is start of the partition
  // fin is end of the partition
  // variante is the variable which select the pivote type (0, 1 or 2)
  int quickSort(int *arrayDatos, int inicio, int fin, int variante) {
      int pivote, i, j;
  
      // vector size 1 -&gt; dont do nothing
      if (inicio &gt;= fin)
          return 0;
      // vector size 1 -&gt; check if is necessary swap it
      if (inicio + 1 == fin) {
          if (arrayDatos[inicio] &gt; arrayDatos[fin]) { // No están ordenados los dos números, intercambiar
              intercambio(arrayDatos, inicio, fin);
          }
          return 0;
      }
      // vector size 3+ 
      switch (variante) {
          case 0: // MIDDLE
          {
              int medio = (inicio + fin) / 2;
              // swap pivot and last element
              intercambio(arrayDatos, medio, fin);
              break;
          }
          case 1: //ALEATORY
          {
              int aleatorio = inicio + rand() % (fin - inicio);
              // swap pivot and last element
              intercambio(arrayDatos, aleatorio, fin);
              break;
          }
          case 2: //MEDIAN
          {
              int mediana = calcularMediana(arrayDatos, inicio, fin);
              // swap pivot and last element
              intercambio(arrayDatos, mediana, fin);
              break;
          }
          default:
              printf("No valid pivot. \n");
              break;
      }
      pivote = arrayDatos[fin];
      // start partition
      for (i = inicio, j = fin - 1;;) {
          while ((i &lt;= fin - 1) &amp;&amp; (arrayDatos[i] &lt;= pivote)) {
              i++;
          }
          while ((j &gt;= inicio) &amp;&amp; (pivote &lt;= arrayDatos[j])) {
              j--;
          }
          if (i &lt; j) { // swap numbers
              intercambio(arrayDatos, i, j);
              i++;
              j--;
          } else // end partition
              break;
      }
      // restore pivot
      intercambio(arrayDatos, i, fin);
      // end partition, recursive calls
      quickSort(arrayDatos, inicio, i - 1, variante); // Vector de la izquierda del pivote
      quickSort(arrayDatos, i + 1, fin, variante); // Vector de la derecha del pivote
  
      return (0);
  }
  
  int main() {
      int *a = malloc(4 * sizeof(int));
      a[0] = 2;
      a[1] = 5;
      a[2] = 4;
      a[3] = 9;
  
      quickSort(a, 0, 4, 2);
  
      for (int i = 0; i &lt; 4; ++i) 
          printf("%i \n", a[i]);
  }
  </code></pre>
  
  <p>But sometimes I get an negative number as first element after sorting, other times sorting is well done. </p>
  
  <p>I mean (assuming vector: <code>{5, 1, 4}</code>), possible results are:</p>
  
  <ul>
  <li>sometimes result is ok: <code>{1, 4, 5}</code></li>
  <li>sometimes result is not ok: <code>{-124565646, 4, 5}</code></li>
  </ul>
  
  <p>I have looked for a possible mistake inside the code, but I have not found any. </p>
  
  <p>Any idea why could it be?</p>