Mega Code Archive

 

Categories / C++ Tutorial / Template

 

Generic quick sort

#include<iostream.h> #include<iomanip.h> #include<cstdlib> template<class T> inline void swap(T& v1,T& v2) {   T temp=v2;   v2=v1;   v1=temp; } template<class T> void quicksort(T *array,int hi,int lo=0) {   while(hi>lo)   {     int i=lo;     int j=hi;     do     {       while(array[i]<array[lo]&&i<j)          i++;       while(array[--j]>array[lo])                  ;       if(i<j)          swap(array[i],array[j]);     }while(i<j);     swap(array[lo],array[j]);     if(j-lo>hi-(j+1)) {        quicksort(array,j-1,lo);        lo=j+1;     }else{        quicksort(array,hi,j+1);        hi=j-1;     }   } } int main() {    int dim = 100;    int *arrs=new int[dim+1];    for(int i=0;i < dim;i++)       arrs[i]=rand();    cout << endl<<"unsorted"<<endl;    for(int i=0;i<dim;i++)       cout<<setw(8)<<arrs[i];    quicksort(arrs,dim);    cout<<endl<<"sorted"<<endl;    for(int i=0;i<dim;i++)       cout<<setw(8)<<arrs[i];    delete arrs;    return 0; } unsorted 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 778 12316 3035 22190 1842 288 30106 9040 8942 19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541 sorted 41 153 288 292 491 778 1842 1869 2082 2995 3035 3548 3902 4664 4827 4966 5436 5447 5537 5705 6334 6729 6868 7376 7711 8723 8942 9040 9741 9894 9961 11323 11478 11538 11840 11942 12316 12382 12623 12859 13931 14604 14771 15006 15141 15350 15724 15890 16118 16541 16827 16944 17035 17421 17673 18467 18716 18756 19169 19264 19629 19718 19895 19912 19954 20037 21538 21726 22190 22648 22929 23281 23805 23811 24084 24370 24393 24464 24626 25547 25667 26299 26308 26500 26962 27446 27529 27644 28145 28253 28703 29358 30106 30333 31101 31322 32391 32439 32662 32757