//------------------------------------------------------------------------------------
//Selects the element to be used for dividing. Moves all the smaller elements
//to the left of this element, and greater than or equal to the right
/*  Type *_arr <- pointer at the beginning of the array
    int _left  <- the number of the first element of the left part of the array
    int _right <- the number of the last element of the right part of the array
    bool _ascending <- variable that determines the sorting method

    if _ascending == true: sorting in ascending order
    if _ascending == false: sorting in descending order
*/
template <typename Type>
int separate(Type *_arr,int _left,int _right,bool _ascending){
    int x = _arr[_left]; // obieramy pivot
    int i = _left, j = _right, w; // i, j - indeksy w tabeli
    while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
    {
        switch((int)_ascending){
            case true: //sorting in ascending order
                while (_arr[j] > x) // dopoki elementy sa wieksze od x
                    j--;
                while (_arr[i] < x) // dopoki elementy sa mniejsze od x
                    i++;
                if (i < j) // zamieniamy miejscami gdy i < j
                {
                    w = _arr[i];
                    _arr[i] = _arr[j];
                    _arr[j] = w;
                    i++;
                    j--;
                }
                else // gdy i >= j zwracamy j jako punkt podzialu tablicy
                    return j;
                break;

            case false: //sorting in descending order
                while (_arr[j] < x) // dopoki elementy sa wieksze od x
                    j--;
                while (_arr[i] > x) // dopoki elementy sa mniejsze od x
                    i++;
                if (i < j) // zamieniamy miejscami gdy i < j
                {
                    w = _arr[i];
                    _arr[i] = _arr[j];
                    _arr[j] = w;
                    i++;
                    j--;
                }
                else // gdy i >= j zwracamy j jako punkt podzialu tablicy
                    return j;
                break;
        }
    }