LAB_ONE

#include<iostream>
using namespace std;


int partition1(int arr[], int l, int h)
{
    int p = arr[l];
    int i = l;
    int j = h;
    while (i < j)
    {
        do
        {
            i++;
        } while (arr[i] <= p);
        do
        {
            j--;
        } while (arr[j] > p);

        if (i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[j]);
    return j;
}

void quickSort1(int arr[], int l, int h)
{

    if (l < h) {
        int piv = partition1(arr, l, h);
        quickSort1(arr, l, piv);
        quickSort1(arr, piv + 1, h);
    }

}



int partition2(int arr[], int iBegin, int jEnd) {
    int i = iBegin;
    int j = jEnd;
    int pivLoc = i;
    while (true)
    {
        while (arr[pivLoc] <= arr[j] && pivLoc != j)
        {
            j--;
        }
        if (pivLoc == j)
            break;
        else if (arr[pivLoc] > arr[j])
        {
            swap(arr[j], arr[pivLoc]);
            pivLoc = j;
        }

        while (arr[pivLoc] >= arr[i] && pivLoc != i)
        {
            i++;
        }
        if (pivLoc == i)
            break;
        else if (arr[pivLoc] < arr[i])
        {
            swap(arr[i], arr[pivLoc]);
            pivLoc = i;
        }
    }
    return pivLoc;
}


void quickSort2(int arr[], int l, int h)
{

    if (l < h) {
        int piv = partition2(arr, l, h);
        quickSort2(arr, l, piv - 1);
        quickSort2(arr, piv + 1, h);
    }

}


int main()
{
    int arr[] = { 2,-1,4,7,0 };

    for (int i = 0; i < 5; i++)
    {
        cout << arr[i] << " ";
    }

    cout << endl;
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort2(arr, 0, n - 1);

    cout << "the sorted array is : \n";
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}