#include <stdio.h>
#include <stdlib.h>
#include "funcsSort.h"

 void partition(int a[], int l, int r, int *i, int *j)
{
*i = l-1, *j = r;
int p = l-1, q = r;
int v = a[r];

while (1)
{

    while (a[++(*i)] < v);
    while (v < a[--(*j)])
        if (*j == l)
            break;


    if (*i >= (*j))

    swap(&a[(*i)], &a[(*j)]);


    if (a[(*i)] == v)
    {
        p++;
        swap(&a[p], &a[(*i)]);
    }

    if (a[(*j)] == v)
    {
        q--;
        swap(&a[(*j)], &a[q]);
    }
 }

swap(&a[(*i)], &a[r]);

int k;
   *j = (*i)-1;
   for (k = l; k < p; k++, (*j)--)
    swap(&a[k], &a[(*j)]);


*i = (*i)+1;
for (k = r-1; k > q; k--, (*i)++)
    swap(&a[(*i)], &a[k]);
}

void quickSort3way(int a[], int l, int r)
{
if (r <= l) return;

int i, j;


partition(a, l, r, &i, &j);

quickSort3way(a, l, j);
quickSort3way(a, i, r);
}