Jäsenrekisteristä voitaisiin lajitella se taulukko, jossa on osoittimet jäseniin. Mikäli joku kuitenkin haluaisi säilyttää alkuperäisenkin järjestyksen, voisimme yrittää keksiä tapoja lajitella aineisto siten, että siihen olisi yhtäaikaa useita eri järjestyksiä.
Helpoin ratkaisu tähän on permutaatiotaulukoiden käyttö. Aikaisempi etsimisessä mallina ollut jäsenrekisteri voitaisiin lajitella vaikkapa nimen ja postinumeron mukaan:
**jasenet | o | cJarjestys +------+------+ Jasen_tyyppi +---+nimen_mukaan | +--------------+ max_koko | 7 | v |Kassinen Katto| indekseja| 3 | +----------+ |Katto | *indeksit| o | +--->jasenet[0] | o-----+-------------->|3452 | +-+-+ | +----------| |... | | |+-->jasenet[1] | o-----+--------+ +--------------+ v || +----------| | +-------------+ +---+ +++-->jasenet[2] | o-----+------+ | |Susi Sepe | 0 | 2 +-+|| +----------| | +----->|Takametsä | +---| || ... | | | |- | 1 | 0 +--+| +----------| | |... | +---| | | | | +-------------+ 2 | 1 +---+ +----------| | +-------------+ +---| | | +------->|Ankka Aku | 3 | ? | +----------| |Ankkalinna | +---| | | |1234 | 4 | ? | +----------| |... | +---| | | +-------------+ 5 | ? | +----------+ +---| osoitintaulukko henkilöihin 6 | ? | +---| 7 | ? | indeksitaulukko joka osoittaa järjestyksen +---+
cJarjestys nimen_mukaan +-----+ max_koko | 7 | 0 1 2 3 4 5 6 indekseja| 3 | +--------------------+ *indeksit | o--+------>| 2| 0| 1| ?| ?| ?| ?| +-----+ +--------------------+ cJarjestys postin_mukaan +-----+ max_koko | 7 | 0 1 2 3 4 5 6 indekseja| 3 | +--------------------+ *indeksit | o--+------>| 1| 2| 0| ?| ?| ?| ?| +-----+ +--------------------+
Lajittelu aloitetaan siten, että järjestettävä permutaatiotaulukko alustetaan johonkin järjestykseen. Esimerkiksi:
cJarjestys nimen_mukaan +-----+ max_koko | 7 | 0 1 2 3 4 5 6 indekseja| 3 | +--------------------+ *indeksit | o--+------>| 0| 1| 2| ?| ?| ?| ?| +-----+ +--------------------+ ^ ^ a---+ +----b
Tämän jälkeen lajitteluohjelmalle annetaan lajiteltavaksi taulukko nimen_mukaan.indeksit. sort välittää vertailufunktio-oliolle verrattavaksi indeksit a ja b. Meidän täytyy siis katsoa miten suhtautuvat toisiinsa nimet
"kerho- >anna_jasen(a).nimi" "kerho- >anna_jasen(b).nimi"
Tämän homman hoitaa esimerkiksi <-operaattori, joka tosin järjestää skandit hieman väärään paikkaan, mutta olkoon tällä kertaa. Aliohjelma on helppo kirjoittaa uusiksi, mikäli ominaisuus haittaa enemmän. Vertailu on case- sensitive, eli Zorro < aapinen!
Jos haluamme lajittelusta aliohjelman, joka osaa järjestää minkä kentän mukaan tahansa, viedään kentän numero saada välitettyä vertailufunktio-oliolle!
Taas käytännössä permutaatiotaulu kannattaa toteuttaa vector-luokan avulla.
lajittele - aliohjelma tekee tarvittavat alustukset, mm. laittaa permutaatiotaulukon johonkin järjestykseen (tässä tapauksessa ehdollisesti, eli jos taulukolla jo on järjestys, ei sitä sotketa). Sitten aliohjelma luo vertailufunktio-olion vieden sille parametrinä käsiteltävän jäsenistön ja kentän indeksin ja lopuksi kutsuu sort-algoritmia.
bool operator() (int a, int b) const {
string s1,s2;
s1 = jasenet->anna(a).kentta_jonoksi(kentan_nro);
s2 = jasenet->anna(b).kentta_jonoksi(kentan_nro);
jono_isoksi(s1); jono_isoksi(s2);
return s1 < s2;
}