title: Modifying this Quicksort to always use the last element as the pivot
body: <p>I have the following <a href="http://www.mycstutorials.com/articles/sorting/quicksort" rel="nofollow noreferrer">Quicksort</a> that always chooses the first element of the subsequence as its pivot:</p>
  
  <pre><code>void qqsort(int array[], int start, int end) {
      int i = start; // index of left-to-right scan
      int k = end; // index of right-to-left scan
  
      if (end - start &gt;= 1) { // check that there are at least two elements to sort 
          int pivot = array[start]; // set the pivot as the first element in the partition
          while (k &gt; i) { // while the scan indices from left and right have not met, 
              while (array[i] &lt;= pivot &amp;&amp; i &lt;= end &amp;&amp; k &gt; i)  // from the left, look for the first element greater than the pivot
                  i++;
              while (array[k] &gt; pivot &amp;&amp; k &gt;= start &amp;&amp; k &gt;= i) // from the right, look for the first element not greater than the pivot
                  k--;
              if (k &gt; i) // if the left seekindex is still smaller than the right index, swap the corresponding elements
                  swap(array, i, k);              
          }
          swap(array, start, k); // after the indices have crossed, swap the last element in the left partition with the pivot 
          qqsort(array, start, k - 1); // quicksort the left partition
          qqsort(array, k + 1, end); // quicksort the right partition
      } else { // if there is only one element in the partition, do not do any sorting 
          return;
      }
  }
  </code></pre>
  
  <p>Now as you can see, this algorithm always takes the  first element to be the pivot: <code>int pivot = array[start];</code></p>
  
  <p>I want to modify this algorithm to make it always use the last element instead of the first element of the subsequence, because I want to analyze the physical running times of both implementations.</p>
  
  <p>I tried changing the line <code>int pivot = array[start];</code> to <code>int pivot = array[end];</code> but the algorithm then outputted an unsorted sequence:</p>
  
  <pre><code>//Changes: int pivot = array[end]; 
  unsorted: {5 4 3 2 1}
  *sorted*: {1 2 5 4 3}
  </code></pre>
  
  <p>To test another pivot, I also tried using the center element of the subsequence but the algorithm still failed:</p>
  
  <pre><code>//Changes: int pivot = array[(start + end) / 2]; 
  unsorted: {5 3 4 2 1}
  *sorted*: {3 2 4 1 5}
  </code></pre>
  
  <hr>
  
  <p>Can someone please help me understand this algorithm correctly and tell me what changes do I need to make to successfully have this implementation always choose the last element of the subsequence as the pivot? </p>