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. qsort välittää
vertailualiohjelmalle verrattavaksi osoittimet a ja b.
Meidän täytyy siis katsoa miten suhtautuvat toisiinsa nimet
"kerho- >jasenet[*(int *)a]- >nimi" "kerho- >jasenet[*(int *)b]- >nimi"Tämän homman hoitaa esimerkiksi strcmp - funktio, 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, täytyisi kentän numero saada välitettyä vertailu- aliohjelmalle! Tätä mahdollisuutta qsort ei tarjoa, joten joudumme keksimään jonkin toisen ratkaisun.