1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
// This code performs a heapsort, which is non-stable
// this algorithm is O(n) and is useful if you have to sort
// large arrays

using namespace std;

void siftDown(int *array, int root, int end) {
  int node=root;
  int child=2*root+1;
  int swap;
  while (child<=end) {
    if (child<end && array[child]<array[child+1]) child++;
    if (array[node]<array[child]) {
       swap=array[child]; array[child]=array[node]; array[node]=swap;
       node=child;
       child=2*node+1;
       } else return;
    }
  }

void heapsort(int * array, int size) {
  // turn the array into a heap
  int end=size-1;
  int root=end/2;
  while (root>=0) {
   siftDown(array, root, end);
   root--;
   }
  // take nodes off one at a time, placing them at the top
  int swap;
  while (end>0) {
   swap=array[0]; array[0]=array[end]; array[end]=swap;
   end--;
   siftDown(array,0,end);
   }
  }


int main(void) {
 int * array=new int[34];
 int val=13,m=197,b=256,p=1337;
 // initializing the array with a pseudo-random permutation of
 // the numbers 0 through 33
 for (int i=0; i<34; i++) {
  // val=m*val+b;
  // val%=p;
  // array[i]=val%100;
  array[i]=(19*i+13)%34;
  cout << array[i] << " ";
  }
 cout << endl;
 heapsort(array,34);
 for (int i=0; i<34; i++)
  cout << array[i] << " ";
 cout << endl;
 }