/********************************************************************************************
ezwQuick.cpp
	Jim Millard
	for CO311

    EZwindows sort visualization for QuickSort

********************************************************************************************/
#include "ezwQuick.h"

#include "ezwSwap.h"
#include "ezwUtils.h"

int Partition(SimpleWindow& W, RaySegment* ptrR[], int A[], const int left, const int right, const short load);

void QuickSort(SimpleWindow& W, RaySegment* ptrR[], int A[], const int left, const int right, const short load)
    {
    if (left < right)
        {
        if (A[left] > A[right])
            {
            Swap(A[right], A[left]);
            Swap(W, *ptrR[right], *ptrR[left], load);
            }
        int pivot = Partition(W, ptrR, A, left, right, load);
        
        QuickSort(W, ptrR, A, left, pivot-1, load);
        QuickSort(W, ptrR, A, pivot+1, right, load);

        Highlight(*ptrR[left],Green);
        Highlight(*ptrR[right],Green);

        }
    }

int Partition(SimpleWindow& W, RaySegment* ptrR[], int A[], const int left, const int right, const short load)
    {
    int pivot = A[left];
    int i = left, j = right+1;

    do  {
        do ++i; while (A[i] < pivot);
        do --j; while (A[j] > pivot);
 
        if (i < j)
            {
            Swap(A[i], A[j]);
            Swap(W, *ptrR[i], *ptrR[j], load);
            }
        }
    while (i < j);

    if (j != left)
        {
        Swap(A[j], A[left]);
        Swap(W, *ptrR[j], *ptrR[left], load);
        }

    Highlight(*ptrR[j],Green);
    return j;
    }