struct stack{
int val;
stack *next;
};

void swap(int tab[], int i, int j){
int tmp=tab[i];
tab[i]=tab[j];
tab[j]=tmp;
}

int partition(int tab[], int left, int right){
int x=tab[right];
int index=left-1;
for(int i=left;i<right;i++){
    if(tab[i]<=right){
        index++;
        swap(tab, i, index);
    }
}
swap(tab, right, index+1);
return index+1;
}

void push(int value, stack *&kot){
stack *nowy=new stack;
if(kot==NULL){
    nowy->val=value;
    nowy->next=NULL;
    nowy=kot;
}
else{
nowy->val=value;
nowy->next=kot;
kot=nowy;
}
}

int pop(stack *&kot){
stack *tmp=kot;
int result=kot->val;
kot=kot->next;
delete tmp;
return result;
}

bool empty(stack *kot){
if(kot==NULL) return true;
else return false;
}

void quicksort(int tab[], int left, int right){
stack *stos=new stack;
stos=NULL;
int q;
while(left<right || !empty(stos)){
        if(left<right){
q=partition(tab, left, right);
 for(int i=0;i<10;i++) cout<<tab[i];
 cout<<endl;
push(q+1, stos);
push(right, stos);
right=q-1;
        }
else{
    right=pop(stos);
    left=pop(stos);
}
}
}