QS

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];



      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };



      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}

//---------------------------------------------------------------------

inline void Sch(int &x, int &y)
{
    Interval aux;
    aux = in[x];
    in[x] = in[y];
    in[y] = aux;
}

int Pivot(int st, int dr)
{
    int i, j, piv;
    piv = v[st].b;
    i = st+1;
    j = dr;
    while(i <= j)
    {
        if(v[i].b <= piv) i++;
        if(v[j].b >= piv) j--;
        if(i < j && v[i].b > piv && v[j].b < piv)
        {
            Sch(v[i], v[j]);
            i++; j--;
        }
    }
    Sch(v[st], v[i-1]);
    return i-1;
}

void QuickSort(int st, int dr)
{
    int m;
    m = Pivot(st, dr);
    if(st < m-1) QuickSort(st, m-1);
    if(m+1 < dr) QuickSort(m+1, dr);
}