Gyorsrendezés C++-ben

Innen: Programozás Wiki
Ugrás a navigációhozUgrás a kereséshez

Ez a rendezés nem cserélgeti az elemeket, hanem ellépteti azokat, így fölöslegesen nem cseréli fel a nem vizsgált elemek sorrendjét, csak a vizsgált elemet mozgatja. Ezáltal egy majdnem rendezett adatbázis rendezése sokkal gyorsabb, általában azt lehet mondani, minél rendezettebb volt az adatbázis, annál gyorsabb a rendezés. A gyorsrendezés más változatainak sebessége teljesen véletlenszerű. Továbbá a vezérelemmel azonos elemeket középre gyűjti, azokat később nem kell újrarendezni. Az #include <vector> csak az utolsó eljárás miatt került be, amely eljárás használatát el lehet kerülni, vagy más iterator típust használó alaptípust lehet a <vector> helyett használni (list). A sort_ eljárás egy jobb alternatívája az <algorithm> sort eljárásának. Az indexelés unsigned jellege miatt trükközni kell az alulcsordulás vizsgálatával. A BASE alaposztályban működnie kell a < összehasonlító operátornak.

#incude <vector>

template<class BASE> inline
void rotate_left( BASE &lo, BASE &hi ) {
   BASE tmp = lo, *from = &lo, *to = from++;
   while( to < &hi ) *to++ = *from++;
   *to = tmp;
}

template<class BASE> inline
void rotate_right( BASE &lo, BASE &hi ) {
   BASE tmp = hi, *from = &hi, *to = from--;
   while( to > &lo ) *to-- = *from--;
   *to = tmp;
}

template<class BASE> inline
void qsort_(BASE *base, size_t first, size_t last) {
   if (first < last) {
       size_t current, minor, major;
       BASE pivot = base[(first + last) / 2];
       for (current = first; current <= last && base[current] < pivot; current++);
       for (minor = current; current <= last; current++) {
           if (base[current] < pivot) {
               rotate_right(base[minor], base[current]);
               minor++;
           }
        }
        if (last >= minor){
           for (current = last; pivot < base[current]; ) {
               if (current-- == minor) break;
           }
           for (major = current; ;) {
               if (pivot < base[current]) {
                   rotate_left(base[current], base[major]);
                   major--;
               }
               if (current-- == minor) break;
            }
            major++;
            if (last > major) qsort_(base, major, last);
        }
        if( minor > first+1 ) qsort_(base, first, minor-1);
    }
}

template<class ITERATOR> inline
void sort_( ITERATOR begin, ITERATOR end) { // end point to after last element
    qsort_( begin.operator->(), 0, end-begin-1 );
}

// Author takacs.ferenc.bp 7 Marc 2017