Prawdziwy kod jest ciut bardziej skomplikowany, stad ten przykladu z X. Fakt, X nie jest funkcja sortujaca tylko klasa posiadajaca w interfejsie funkcje swap uzywana przez funkcje sortujace:
class XInterface
{
virtual void swap( int l, int r ) = 0;
};
class X
: XInterface
{
CRow _row[ 10 ];
void swap( int l, int r ) { CRow temp = _row[ l ]; _row[ l ] = _row[ r ]; _row[ r ] = temp; }
};
void sort( X & x )
{
for( int i = 0; i < 9; ++i )
for( j = i + 1; j < 10; ++j )
if( jakas_logika( x._row[ i ], x._row[ j ] ) )
x.swap( i, j );
}
Klasa Y ma liste X i mapowanie indexow (w przykladzie uzylem tablicy by uproscic zapis). Generalnie Y sluzy do mapowania indexow do klas X:
class Y
{
std::vector < X *> _listaXow;
std::map < int, std::pair < int, int > > _indexy;
int _rzedy;
add( X * x )
{
for( int i = 0; i < x.ileMaRzedow(); ++i )
{
++_rzedy;
_indexy.push_back( std::make_pair( _listaXow.size(), i ) );
}
_listaXow.push_back( x );
}
}
Dziala to tak ze majac 100 klas X, kazda ma tablice z 10 elementami, dodaje sie ja do Y i uzywa jakby to byla jedna tabelka z 1000 elementow:
X x1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
X x2 = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
x1[ 11 ] <- poza zakresem
Y y = x1 + x2;
y[ 11 ] <- zwroci 11
To wszystko jest przykladowy kod. Problem jest przy sortowaniu, funkcja sortujaca przyjmuje X, i ma zahardcodowane sortowanie tablicy 10 elementowej. wiec potrzebuje zaimplementowac algorym ktory posortuje liste X (kazdy X sortuje osobno, ztad przyklad:
{ {1, 3, 4}, {1, 7, 9}, {2, 3, 8} }
// wolanie sort 3 razy dla: X={1, 3, 4}, X={1, 7, 9} X={2, 3, 8}
{ {3, 1, 4}, {1, 9, 7}, {8, 2, 3} }.
nastepnie podzieli wszystkie X, zbuduje nowy X i posortuje (np nastepnym krokiem moze byc: "wez 1sze elementy z kazdego X'a i posrtuje"):
{ {3, 1, 4}, {1, 9, 7}, {8, 2, 3} }. <- 1sze elementy do temp'a X={3,1,8} -> sortowanie -> {1,3,8} -> wstaw spowrotem -> { {1,1,4}, {3,9,7}, {8,2,3}}
Czyli:
1) Nie szukam poprawek do klas X i Y, to sa tylko przyklady.
2) Nie da rady porownac w prosty sposob 2 elementow (mozna przekazujac X z 2ma elemntami, ale to najgorsze rozwiazanie)
3) Zaden algorym counting-sort nie wchodzi w gre. Mozna uzywac tylko funkcji sort, czyli to typowy divide & conquer
4) Ja nie podzielime zbioru na podzbiory tylko chce je polaczyc (jako Y)
5) Nie dam rady wkleic calego kodu (jest go za duzo) i nie szukam implementacji tylko algorytmu.
Na chwile obecna mam algorytm oparty na drzewach. Buduje z X'ow drzewa, gdzie wezel jest lepszy od potomkow, a nastepnie w kolejnych iteracjach merguje drzewa (do sortowania wezly z iloscia dzieci >1). Po N iteracjach dostaje 1 drzewo, gdzie kazdy wezel ma dokladnie 1 dziecko (liste), ale zastanawiam sie czy jest to optymalne rozwiazanie.