/*  Unoptimized quicksort implementation
    Written 4 Mar 2004 by Warren M Myers
      templatized swap not ideal for int or char types
      for int and char types, use :
        x^=y; y^=x; x^=y;
 */

#ifndef _QSORTU_H_
#define _QSORTU_H_

template <class T> void swap(T &l, T &r){
    T t = l;
    l = r;
    r = t;
}

template <class T> int part(T a[], int l, int r){
    T p = a[l];
    int i = l, 
	j = r+1;
    do{
	while(a[++i]<p);
	while(a[--j]>p);
	swap(a[i],a[j]);
    }while(i<j);
    swap(a[i],a[j]);
    swap(a[l],a[j]);
    return j;
}

template <class T> void qsort(T a[], int l, int r){
    if(l<r){
	int s = part(a,l,r);
	qsort(a,l,s-1);
	qsort(a,s+1,r);
    }
}

#endif