#include"algo.h"
#include<stdlib.h>
#include<math.h>
#include<time.h>
void QuickSort(int* arr, int left, int right)
{
    if (left >= right) 
    {
        return;
    }
    int position = PartSort(arr, left, right);
    QuickSort(arr, left, position - 1);
    QuickSort(arr, position + 1, right);
}


int  PartSort(int* arr, int left, int right)
{
    int key = arr[left];

    while (left < right) {
        while (left < right && arr[right] >= key) 
        {
            right--;
        }
        swap(arr, left, right);

        while (left < right && arr[left] <= key) 
        {
            left++;
        }         
        swap(arr, left, right);
    }

    return left;
}


void swap(int* arr, int left, int right)
{
    int temp = 0;

    temp = arr[right];
    arr[right] = arr[left];
    arr[left] = temp;
}