sg_sort.h

/**
* \file sg_sort.hpp
*
* Generikus rendező algoritmus, ami
* az elemek előfordulási gyakorisága
* szerint rendez egy tömböt.
*/

 #ifndef SORT_HPP
 #define SORT_HPP

/// elemek és darabszámuk tárolása a gyakoriság miatt
template <class T>
struct element {
    T data;         // számolandó elem
    int n;          // számolandó elem darabszáma
};


/// tömb egyedi elemeinek száma
/// @param  _array      vizsgálandó tömb
/// @param  length      vizsgálandó tömb mérete
/// return              tömb egyedi elemeinek száma
template <class T>
int Unique(const T *_array, int length) {

    int db = 0;
    T *tmp = new T[length];
    for (int i = 0; i < length; i++) {
        bool volt = false;
        for (int j = 0; j < length; j++)
        if (_array[i] == tmp[j])
            volt = true;
        if (!volt)   tmp[db++] = _array[i];
    }
    delete[] tmp;
    return db;

}


/// Generikus rendező algoritmus, ami
/// az elemek előfordulási gyakorisága
/// szerint rendez egy tömböt.
/// @param  _array      rendezendő tömb
/// @param  length      rendezendő tömb mérete
/// @param  debug       debug mode on / off
template <class T>
void sg_sort(T *_array, int length, bool debug = false) {

    if (debug) {
        // tömb elemeinek vizsgálata
        std::cout << "original array (length=" << length << ")" << std::endl;
        for (int i = 0; i < length; i++) {
            int db = 0;
            for (int j = 0; j < length; j++) {
                if (_array[i] == _array[j])
                    db++;
            }
            std::cout << " " << _array[i] << " {" << db << "}" << std::endl;
        }
        std::cout << std::endl;
    }


    // egyedi elemek száma
    int newLength = Unique<int>(_array, length);
    if (debug)  std::cout << "new array (length=" << newLength << ")" << std::endl;

    // új tömb az egyedi elemek tárolására
    if (newLength < 0)  throw std::out_of_range("sg_sort()");
    element<T> *result = new element<T>[newLength];
    int m = 0;  // tömb indexelő

    for (int i = 0; i < length; i++) {
        // benne van már a listába az akt. elem vagy nem
        bool volt = false;
        for (int j = 0; j < newLength; j++) {
            if (_array[i] == result[j].data) {
                volt = true;
                break;
            }
        }
        if (!volt) {
            // még nincs benne a listába az adott elem
            result[m].data = _array[i];
            result[m++].n = 1;
        } else {
            // az adott elem már benne van a listába, növelni kell a számlálóját
            int result_idx = 0;
            for (int j = 0; j < newLength; j++) {
                // index keresése az adott elemhez
                if (result[j].data == _array[i]) {
                    result_idx = j;
                    break;
                }
            }
            (result[result_idx].n)++;   // adott elem számlálójának növelése
        }
    }

    if (debug) {
        for (int i = 0; i < newLength; i++) {
            std::cout << " " << result[i].data << " {" << result[i].n << "}" << std::endl;
        }
    }

    // eredmény tömb rendezése
    if (debug) { std::cout << std::endl << "sorted array (length=" << newLength << ")" << std::endl; }
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1; j++) {
            if (result[j].n > result[j + 1].n) {
                element<T> tmp = result[j];
                result[j] = result[j + 1];
                result[j + 1] = tmp;
            }
        }
    }
    if (debug) {
        for (int i = 0; i < newLength; i++) {
            std::cout << " " << result[i].data << " {" << result[i].n << "}" << std::endl;
        }
    }


    for (int i = 0; i < length;) {          //  _array.length
        for (int j = 0; j < newLength; j++) {   //  result.length
            int count = 0;
            while (count < result[j].n) {       //  result[x].n
                _array[i++] = result[j].data;
                count++;
            }
        }
    }

    delete[] result;    // temporális tömb törlése <-- BUG BUG BUG
}


 #endif // SORT_HPP