Posted By

acecengic on 12/17/14


Tagged

sort Shell


Versions (?)

Shell Sort


 / Published in: C++
 

shell sort algorithm

  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. template<typename Comparable>
  7. void heapsort(vector<Comparable> & a)
  8. {
  9. for (int i = a.size() / 2; i >= 0; i--) /* buildHeap */
  10. percDown(a, i, a.size());
  11. for (int j = a.size() - 1; j > 0; j--)
  12. {
  13. swap(a[0], a[j]); /* deleteMax */
  14. percDown(a, 0, j);
  15. }
  16. }
  17.  
  18. /**
  19.  * Internal method for heapsort.
  20.  * i is the index of an item in the heap.
  21.  * Returns the index of the left child.
  22.  */
  23. inline int leftChild(int i)
  24. {
  25. return 2 * i;
  26. }
  27.  
  28. /**
  29.  * Internal method for heapsort that is used in deleteMax and buildHeap.
  30.  * i is the position from which to percolate down.
  31.  * n is the logical size of the binary heap.
  32.  */
  33. template<typename Comparable>
  34. void percDown(vector<Comparable> & a, int i, int n)
  35. {
  36. int child;
  37. Comparable tmp;
  38.  
  39. for (tmp = a[i]; leftChild(i) < n; i = child)
  40. {
  41. child = leftChild(i);
  42. if (child != n - 1 && a[child] < a[child + 1])
  43. child++;
  44. if (tmp < a[child])
  45. a[i] = a[child];
  46. else
  47. break;
  48. }
  49. a[i] = tmp;
  50. }
  51.  
  52. void printVector(vector<int> & h)
  53. {
  54. unsigned int i;
  55. cout << "Start:" << endl;
  56. for (i = 0; i < h.size(); ++i)
  57. {
  58. cout << "h[" << i << "] = " << h[i] << endl;
  59. } // end for
  60. cout << "End." << endl;
  61. }
  62.  
  63. int main()
  64. {
  65.  
  66. vector<int> h(5);
  67.  
  68. h[0] = 21;
  69. h[1] = 52;
  70. h[2] = 67;
  71. h[3] = 19;
  72. h[4] = 82;
  73.  
  74. printVector(h);
  75. heapsort(h);
  76. printVector(h);
  77. return 0;
  78.  
  79. }

Report this snippet  

You need to login to post a comment.