int i = begin - 1;

int j = begin;

int st = a[end - 1];

while (j < end - 1) {

if (a[j] < st) {

i += 1;

int tmp = a[j];

a[j] = a[i];

a[i] = tmp;

}

j += 1;

}

int tmp = a[i + 1];

a[i + 1] = a[end - 1];

a[end - 1] = tmp;

return i + 1;

int position = split(a, begin, end);

if (begin < position)

qsort(a, begin, position);

if (position < end - 1)

qsort(a, position, end);

int left = begin * 2 + 1;

int right = begin * 2 + 2;

int max = begin;

if (left <= end && a[begin] < a[left]) {

max = left;

}

if (right <= end && a[max] < a[right]) {

max = right;

}

if (max != begin) {

int tmp = a[begin];

a[begin] = a[max];

a[max] = tmp;

adjust_heap(a, max, end);

}

int midel = (begin + end) / 2;

for (int i = midel; i >= begin; i--) {

adjust_heap(a, i, end);

}

build_heap(a, begin, end);

for (int j = begin; j <= end; ++j) {

cout << " " << a[j];

}

cout << endl;

for (int i = end; i >= begin; i--) {

adjust_heap(a, begin, i);

int tmp = a[i];

a[i] = a[begin];

a[begin] = tmp;

}

}