Quick_Sort

#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

int ran(int a1, int a2)
{
    return rand() % (a2 - a1 + 1) + a1;
}

int swap(int &a, int &b)
{
    int temp = a; a = b; b = temp;
}

int Partition(int *arr, int left, int right)
{
    int i = left, j = right;
    int pivot = ran(left, right);
    do
    {
        while (i == pivot || arr[i]<=arr[pivot]) i++;
        while (j == pivot || arr[j]>=arr[pivot]) j--;
        if (i<j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    } while (i<j);
    if (j<left)
    {
        if ((pivot - i)*(arr[pivot] - arr[i])<0)
        {
            swap(arr[pivot], arr[i]);
            return i;
        }
        return pivot;
    }
    else if (i>right)
    {
        if ((pivot - j)*(arr[pivot] - arr[j])<0)
        {
            swap(arr[pivot], arr[j]);
            return j;
        }
        return pivot;
    }
    if ((pivot - i)*(arr[pivot] - arr[i])<0)
    {
        swap(arr[pivot], arr[i]);
        return i;
    }
    else if ((pivot - j)*(arr[pivot] - arr[j])<0)
    {
        swap(arr[pivot], arr[j]);
        return j;
    }
    else
        return pivot;
}

void quickSort(int *arr, int left, int right)
{
    if (left<right)
    {
        int p = Partition(arr, left, right);
        if (left<p)
            quickSort(arr, left, p - 1);
        if (right>p)
            quickSort(arr, p + 1, right);
    }
}

int main()
{
    srand((unsigned)(time(NULL)));
    int i, arr[20] = {};
    for (i = 0; i<20; i++)
        arr[i] = ran(1, 1000);
    cout << "Before " << endl;
    for (i = 0; i<20; i++)
        cout << arr[i] << " ";
    cout << endl;
    quickSort(arr, 0, 19);
    cout << "After " << endl;
    for (i = 0; i<20; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}