Scopira 20080306

sort_imp.h

00001 
00002 /*
00003  *  Copyright (c) 2002    National Research Council
00004  *
00005  *  All rights reserved.
00006  *
00007  *  This material is confidential and proprietary information of
00008  *  National Research Council Canada ("Confidential Information").
00009  *  This Confidential Information may only be used and reproduced
00010  *  in accordance with the terms of the license agreement.
00011  *
00012  */
00013 
00014 #ifndef __INCLUDED__SCOPIRA_TOOL_SORT_IMP__
00015 #define __INCLUDED__SCOPIRA_TOOL_SORT_IMP__
00016 
00017 namespace scopira
00018 {
00019   namespace tool
00020   {
00021     template <class T> void qsort(T &s, int lo0, int hi0);
00022   }
00023 }
00024 
00045 template <class T> void scopira::tool::qsort(T &s, int lo0, int hi0)
00046 {
00047   int lo = lo0;
00048   int hi = hi0;
00049   int mid;
00050 
00051   if ( hi0 > lo0) {
00052     // Arbitrarily establishing partition element as the midpoint of
00053     // the array.
00054     mid = ( lo0 + hi0 ) / 2;
00055 
00056     // loop through the array until indices cross
00057     while( lo <= hi ) {
00058       // find the first element that is greater than or equal to
00059       // the partition element starting from the left Index.
00060       while( ( lo < hi0 ) && ( s.compare_element(lo, mid) < 0 ) )
00061         lo++;
00062       // find an element that is smaller than or equal to
00063       // the partition element starting from the right Index.
00064       while( ( hi > lo0 ) && ( s.compare_element(hi, mid) > 0 ) )
00065         hi--;
00066 
00067       // if the indexes have not crossed, swap
00068       if( lo <= hi ) {
00069         // because we're dealin with indecies (and not the data directly)
00070         // we need to see if we swapped out midpoint away
00071         if (lo == mid)
00072           mid = hi;
00073         else if (hi == mid)
00074           mid = lo;
00075         s.swap_element(lo, hi);
00076         lo++;
00077         hi--;
00078       }
00079     }
00080 
00081     qsort(s, lo0, hi );
00082     qsort(s, lo, hi0 );
00083   }
00084 }//quick_sort
00085 
00086 #endif
00087