title: Heap Sort from Intro to Algorithms in C++ Implementation using Vectors
body: <p>I have been working on Heap Sort Functions in C++ that follows the logic from our class book, Intro to Algorithms 3rd edition and am not getting the desired output.  Have been working through this in my head and am close, but I am not seeing my error.  I am using vectors and have omitted the code that reads the values from a separate text file.  </p>
  
  <p>Any ideas on where I am going wrong with the indexes in each version?  Adding, the input list I am using to test is <strong>10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18</strong>.</p>
  
  <p>The first method I tried is closer to the book but was giving output of <strong>10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1</strong>.  This is my preferred solution if I could figure out how I am messing up the indexing.  </p>
  
  <pre><code>void maxHeapify(vector&lt;int&gt;&amp;);
  void buildMaxHeap(vector&lt;int&gt;&amp;);
  void heapSort(vector&lt;int&gt;&amp;);
  
  int main(int argc, char * argv[])
  {
  if (argc &lt;= 1)
  {
      std::cerr &lt;&lt; "A file was not found or is not accessable." &lt;&lt; std::endl;
      return (1);
  }
  
  vector&lt;int&gt; list;
  int loc;
  
  ifstream fin(argv[1]);
  
  while (fin &gt;&gt; loc)
  {
      list.push_back(loc);
  }
  
  // print unsorted list
  cout &lt;&lt; "Unsorted List:\n";
  for (int i = 0; i &lt; list.size(); ++i)
      cout &lt;&lt; list[i] &lt;&lt; ' ';
  cout &lt;&lt; endl;
  
  heapSort(list);
  
  // print sorted list
  cout &lt;&lt; "Sorted List:\n";
  for (int i = 0; i &lt; list.size(); ++i) {
      cout &lt;&lt; list[i] &lt;&lt; " ";
  }
  cout &lt;&lt; endl;
  
  cin.get();
  
  return(0);
  }
  
  /* Heap Sort from Textbook using Vectors ***********************************/
  void maxHeapify(vector&lt;int&gt;&amp; A, int i)
  {
  int largest;
  int l = 2 * i;
  int r = (2 * i) + 1;
  
  if ((l &lt;= A.size()) &amp;&amp; (A[l] &gt; A[i]))
      largest = l;
  else
      largest = i;
  
  if ((r &lt;= int(A.size())) &amp;&amp; (A[r] &gt; A[largest]))
      largest = r;
  
  if (largest != i)
  {
      swap(A[i], A[largest]);
      maxHeapify(A, largest);
  }
  }
  
  void buildMaxHeap(vector&lt;int&gt;&amp; A)
  {
  for (int i = int((A.size()-1) / 2); i &gt;= 1; i--)  
  {
      maxHeapify(A, i);
  }
  }
  
  void heapSort(vector&lt;int&gt;&amp; A)
  {
  
  buildMaxHeap(A);
  for (int i = int(A.size()-1); i &gt;= 2; i--)  
      swap(A[1], A[i]);
      maxHeapify(A, 1);
  }
  }
  </code></pre>
  
  <p>The second method I tried ends up with an output <strong>2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 to 50</strong> on a randomly sorted list of 50 integers but is correct on a list of only 20 random integers.  The code is as follows:</p>
  
  <pre><code>void maxHeapify(vector&lt;int&gt;&amp;, int, int);
  void buildMaxHeap(vector&lt;int&gt;&amp;, int);
  void heapSort(vector&lt;int&gt;&amp;, int);
  
  int main(int argc, char * argv[])
  {
  if (argc &lt;= 1)
  {
      std::cerr &lt;&lt; "A file was not found or is not accessable." &lt;&lt; std::endl;
      return (1);
  }
  
  vector&lt;int&gt; list;
  int loc;
  
  ifstream fin(argv[1]);
  
  while (fin &gt;&gt; loc)
  {
      list.push_back(loc);
  }
  
  // print unsorted list
  cout &lt;&lt; "Unsorted List:\n";
  for (int i = 0; i &lt; list.size(); ++i)
      cout &lt;&lt; list[i] &lt;&lt; ' ';
  cout &lt;&lt; endl;
  
  clock_t begin = clock();
  
  heapSort(list, int(list.size() - 1));
  
  clock_t end = clock();
  double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  
  
  printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
  cout &lt;&lt; endl;
  
  // print sorted list
  cout &lt;&lt; "Sorted List:\n";
  for (int i = 0; i &lt; list.size(); ++i) {
      cout &lt;&lt; list[i] &lt;&lt; " ";
  }
  cout &lt;&lt; endl;
  
  cin.get();
  
  return(0);
  }
  
  /* Heap Sort from Textbook using Vectors ***********************************/
  void maxHeapify(vector&lt;int&gt;&amp; A, int i, int n)
  {
  int largest;
  int l = 2 * i;
  int r = (2 * i) + 1;
  
  if ((l &lt;= n) &amp;&amp; (A[l - 1] &gt; A[i - 1]))
      largest = l;
  else
      largest = i;
  
  if ((r &lt;= n) &amp;&amp; (A[r - 1] &gt; A[largest - 1]))
      largest = r;
  
  if (largest != i)
  {
      swap(A[i - 1], A[largest - 1]);
      maxHeapify(A, largest, n);
  }
  }
  
  void buildMaxHeap(vector&lt;int&gt;&amp; A, int n)
  {
  for (int i = n / 2; i &gt;= 1; i--)
  {
      maxHeapify(A, i, n);
  }
  }
  
  void heapSort(vector&lt;int&gt;&amp; A, int n)
  {
  
  buildMaxHeap(A, n);
  for (int i = n; i &gt;= 2; i--)
  {
      swap(A[0], A[i]);
      maxHeapify(A, 1, i - 1);
  }
  }
  </code></pre>