title: Analysis of Hoare's Partioning
body: <p>I have an assignment to draw a graph and analyze the Hoare's partitioning algorithm and compare theoretical and practical worst-case scenario values. It says that I need a count variable to keep track of critical steps (i.e comparison and swapping). I wrote this code for Hoare's partitioning.</p>
  <pre><code>public static int partition(Comparable[] a, int left, int right) {
          Comparable pivot = a[(left + right) / 2];
          int i = left - 1, j = right + 1;
          while (true) {
              do {
                  i++;
              } while (a[i].compareTo(pivot) &lt; 0);
  
              do {
                  j--;
              } while (a[j].compareTo(pivot) &gt; 0);
  
              if (i &lt; j) {
                  Comparable temp = a[i];
                  a[i] = a[j];
                  a[j] = temp;
              } else {
                  return j;
              }
          }
  }
  </code></pre>
  <p>Now I am confused about where to add the count variable. I know that count variable will be incremented in if (i &lt; j) line. But do I also need to increment count in both do-while loops to keep track of comparisons?</p>
  <p><strong>So, the updated code will be like this?</strong></p>
  <pre><code>public static int partition(Comparable[] a, int left, int right) {
          int count = 0;
          Comparable pivot = a[(left + right) / 2];
          int i = left - 1, j = right + 1;
          while (true) {
              do {
                  count++;
                  i++;
              } while (a[i].compareTo(pivot) &lt; 0);
  
              do {
                  count++;
                  j--;
              } while (a[j].compareTo(pivot) &gt; 0);
  
              if (i &lt; j) {
                  count++;
                  Comparable temp = a[i];
                  a[i] = a[j];
                  a[j] = temp;
              } else {
                  return j;
              }
          }
  }
  </code></pre>
  <p><strong>Or like this?</strong></p>
  <pre><code>public static int partition(Comparable[] a, int left, int right) {
              int count = 0;
              Comparable pivot = a[(left + right) / 2];
              int i = left - 1, j = right + 1;
              while (true) {
                  do {
                      i++;
                  } while (a[i].compareTo(pivot) &lt; 0);
      
                  do {
                      j--;
                  } while (a[j].compareTo(pivot) &gt; 0);
      
                  if (i &lt; j) {
                      count++;
                      Comparable temp = a[i];
                      a[i] = a[j];
                      a[j] = temp;
                  } else {
                      return j;
                  }
              }
      }
  </code></pre>