#include <iostream>
using namespace std;
 
void qsort (int a[], int lef, int rit);
 
int main() 
{
	int a[]={5,10,7,6,3,9,4,8,12};
	for (int i=0;i<9;i++) cout<< a[i]<<" "; cout<< endl;
	qsort (a, 0, 8);
	for (int i=0;i<9;i++) cout<< a[i]<<" "; cout<< endl;
	return 0;
}
 
void qsort (int a[], int lef, int rit)
{
int ir, rm, buf; // ir – для индекса среднего элемента
// текущей части массива.
// rm – для значения среднего
// элемента текущего массива.
// buf – для промежуточных значений
// обрабатываемой информации.
int l1, r1; // l1 – для индекса элемента, который
// расположен левее и
// больше среднего.
// r1 – для индекса элемента, который
// расположен правее и
// меньше среднего.
int i; // i – для управляющего параметра цикла.
l1 = lef; // Определяем начальный индекс текущей
// части массива.
r1 = rit; // Определяем конечный индекс текущего
// массива.
ir = (l1+r1)/2; // Определяем индекс среднего элемента
// текущей части массива.
rm = a[ir]; // В rm пересылаем значение среднего
// элемента текущего массива.
do // Цикл для перебора элементов, которые
// находятся левее и правее среднего
// элемента текущей части массива.
{
while ( a[l1] < rm ) l1++; // Находим 1-й элемент, который лежит
// слева и больше среднего элемента.
// Индекс этого элемента фиксируется
// в переменной l1.
while ( a[r1] > rm ) r1--; // Находим 1-й элемент, который лежит
// справа и больше среднего элемента.
// Индекс этого элемента фиксируется
// в переменной r1.
if ( l1 <= r1 ) // Начало перестановки элементов
// массива. Меньший относительно
// среднего переставляем в позицию l1,
// а больший относительно среднего
// переставляем в позицию r1 и директивами
// l1++; и r1++; переходим к рассмотрению
// следующих элементов, расположенных
// соответственно левее и правее среднего элемента.
{
// Переставляем элементы массива.
buf = a[l1];
a[l1] = a[r1];
a[r1] = buf;
l1++;
r1--;
} // Конец перестановки элементов массива.
}
while ( r1 > l1 );
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBxc29ydCAoaW50IGFbXSwgaW50IGxlZiwgaW50IHJpdCk7CgppbnQgbWFpbigpIAp7CglpbnQgYVtdPXs1LDEwLDcsNiwzLDksNCw4LDEyfTsKCWZvciAoaW50IGk9MDtpPDk7aSsrKSBjb3V0PDwgYVtpXTw8IiAiOyBjb3V0PDwgZW5kbDsKCXFzb3J0IChhLCAwLCA4KTsKCWZvciAoaW50IGk9MDtpPDk7aSsrKSBjb3V0PDwgYVtpXTw8IiAiOyBjb3V0PDwgZW5kbDsKCXJldHVybiAwOwp9Cgp2b2lkIHFzb3J0IChpbnQgYVtdLCBpbnQgbGVmLCBpbnQgcml0KQp7CmludCBpciwgcm0sIGJ1ZjsgLy8gaXIg4oCTINC00LvRjyDQuNC90LTQtdC60YHQsCDRgdGA0LXQtNC90LXQs9C+INGN0LvQtdC80LXQvdGC0LAKLy8g0YLQtdC60YPRidC10Lkg0YfQsNGB0YLQuCDQvNCw0YHRgdC40LLQsC4KLy8gcm0g4oCTINC00LvRjyDQt9C90LDRh9C10L3QuNGPINGB0YDQtdC00L3QtdCz0L4KLy8g0Y3Qu9C10LzQtdC90YLQsCDRgtC10LrRg9GJ0LXQs9C+INC80LDRgdGB0LjQstCwLgovLyBidWYg4oCTINC00LvRjyDQv9GA0L7QvNC10LbRg9GC0L7Rh9C90YvRhSDQt9C90LDRh9C10L3QuNC5Ci8vINC+0LHRgNCw0LHQsNGC0YvQstCw0LXQvNC+0Lkg0LjQvdGE0L7RgNC80LDRhtC40LguCmludCBsMSwgcjE7IC8vIGwxIOKAkyDQtNC70Y8g0LjQvdC00LXQutGB0LAg0Y3Qu9C10LzQtdC90YLQsCwg0LrQvtGC0L7RgNGL0LkKLy8g0YDQsNGB0L/QvtC70L7QttC10L0g0LvQtdCy0LXQtSDQuAovLyDQsdC+0LvRjNGI0LUg0YHRgNC10LTQvdC10LPQvi4KLy8gcjEg4oCTINC00LvRjyDQuNC90LTQtdC60YHQsCDRjdC70LXQvNC10L3RgtCwLCDQutC+0YLQvtGA0YvQuQovLyDRgNCw0YHQv9C+0LvQvtC20LXQvSDQv9GA0LDQstC10LUg0LgKLy8g0LzQtdC90YzRiNC1INGB0YDQtdC00L3QtdCz0L4uCmludCBpOyAvLyBpIOKAkyDQtNC70Y8g0YPQv9GA0LDQstC70Y/RjtGJ0LXQs9C+INC/0LDRgNCw0LzQtdGC0YDQsCDRhtC40LrQu9CwLgpsMSA9IGxlZjsgLy8g0J7Qv9GA0LXQtNC10LvRj9C10Lwg0L3QsNGH0LDQu9GM0L3Ri9C5INC40L3QtNC10LrRgSDRgtC10LrRg9GJ0LXQuQovLyDRh9Cw0YHRgtC4INC80LDRgdGB0LjQstCwLgpyMSA9IHJpdDsgLy8g0J7Qv9GA0LXQtNC10LvRj9C10Lwg0LrQvtC90LXRh9C90YvQuSDQuNC90LTQtdC60YEg0YLQtdC60YPRidC10LPQvgovLyDQvNCw0YHRgdC40LLQsC4KaXIgPSAobDErcjEpLzI7IC8vINCe0L/RgNC10LTQtdC70Y/QtdC8INC40L3QtNC10LrRgSDRgdGA0LXQtNC90LXQs9C+INGN0LvQtdC80LXQvdGC0LAKLy8g0YLQtdC60YPRidC10Lkg0YfQsNGB0YLQuCDQvNCw0YHRgdC40LLQsC4Kcm0gPSBhW2lyXTsgLy8g0JIgcm0g0L/QtdGA0LXRgdGL0LvQsNC10Lwg0LfQvdCw0YfQtdC90LjQtSDRgdGA0LXQtNC90LXQs9C+Ci8vINGN0LvQtdC80LXQvdGC0LAg0YLQtdC60YPRidC10LPQviDQvNCw0YHRgdC40LLQsC4KZG8gLy8g0KbQuNC60Lsg0LTQu9GPINC/0LXRgNC10LHQvtGA0LAg0Y3Qu9C10LzQtdC90YLQvtCyLCDQutC+0YLQvtGA0YvQtQovLyDQvdCw0YXQvtC00Y/RgtGB0Y8g0LvQtdCy0LXQtSDQuCDQv9GA0LDQstC10LUg0YHRgNC10LTQvdC10LPQvgovLyDRjdC70LXQvNC10L3RgtCwINGC0LXQutGD0YnQtdC5INGH0LDRgdGC0Lgg0LzQsNGB0YHQuNCy0LAuCnsKd2hpbGUgKCBhW2wxXSA8IHJtICkgbDErKzsgLy8g0J3QsNGF0L7QtNC40LwgMS3QuSDRjdC70LXQvNC10L3Rgiwg0LrQvtGC0L7RgNGL0Lkg0LvQtdC20LjRggovLyDRgdC70LXQstCwINC4INCx0L7Qu9GM0YjQtSDRgdGA0LXQtNC90LXQs9C+INGN0LvQtdC80LXQvdGC0LAuCi8vINCY0L3QtNC10LrRgSDRjdGC0L7Qs9C+INGN0LvQtdC80LXQvdGC0LAg0YTQuNC60YHQuNGA0YPQtdGC0YHRjwovLyDQsiDQv9C10YDQtdC80LXQvdC90L7QuSBsMS4Kd2hpbGUgKCBhW3IxXSA+IHJtICkgcjEtLTsgLy8g0J3QsNGF0L7QtNC40LwgMS3QuSDRjdC70LXQvNC10L3Rgiwg0LrQvtGC0L7RgNGL0Lkg0LvQtdC20LjRggovLyDRgdC/0YDQsNCy0LAg0Lgg0LHQvtC70YzRiNC1INGB0YDQtdC00L3QtdCz0L4g0Y3Qu9C10LzQtdC90YLQsC4KLy8g0JjQvdC00LXQutGBINGN0YLQvtCz0L4g0Y3Qu9C10LzQtdC90YLQsCDRhNC40LrRgdC40YDRg9C10YLRgdGPCi8vINCyINC/0LXRgNC10LzQtdC90L3QvtC5IHIxLgppZiAoIGwxIDw9IHIxICkgLy8g0J3QsNGH0LDQu9C+INC/0LXRgNC10YHRgtCw0L3QvtCy0LrQuCDRjdC70LXQvNC10L3RgtC+0LIKLy8g0LzQsNGB0YHQuNCy0LAuINCc0LXQvdGM0YjQuNC5INC+0YLQvdC+0YHQuNGC0LXQu9GM0L3QvgovLyDRgdGA0LXQtNC90LXQs9C+INC/0LXRgNC10YHRgtCw0LLQu9GP0LXQvCDQsiDQv9C+0LfQuNGG0LjRjiBsMSwKLy8g0LAg0LHQvtC70YzRiNC40Lkg0L7RgtC90L7RgdC40YLQtdC70YzQvdC+INGB0YDQtdC00L3QtdCz0L4KLy8g0L/QtdGA0LXRgdGC0LDQstC70Y/QtdC8INCyINC/0L7Qt9C40YbQuNGOIHIxINC4INC00LjRgNC10LrRgtC40LLQsNC80LgKLy8gbDErKzsg0LggcjErKzsg0L/QtdGA0LXRhdC+0LTQuNC8INC6INGA0LDRgdGB0LzQvtGC0YDQtdC90LjRjgovLyDRgdC70LXQtNGD0Y7RidC40YUg0Y3Qu9C10LzQtdC90YLQvtCyLCDRgNCw0YHQv9C+0LvQvtC20LXQvdC90YvRhQovLyDRgdC+0L7RgtCy0LXRgtGB0YLQstC10L3QvdC+INC70LXQstC10LUg0Lgg0L/RgNCw0LLQtdC1INGB0YDQtdC00L3QtdCz0L4g0Y3Qu9C10LzQtdC90YLQsC4KewovLyDQn9C10YDQtdGB0YLQsNCy0LvRj9C10Lwg0Y3Qu9C10LzQtdC90YLRiyDQvNCw0YHRgdC40LLQsC4KYnVmID0gYVtsMV07CmFbbDFdID0gYVtyMV07CmFbcjFdID0gYnVmOwpsMSsrOwpyMS0tOwp9IC8vINCa0L7QvdC10YYg0L/QtdGA0LXRgdGC0LDQvdC+0LLQutC4INGN0LvQtdC80LXQvdGC0L7QsiDQvNCw0YHRgdC40LLQsC4KfQp3aGlsZSAoIHIxID4gbDEgKTsKfQo=