1.3.4 sort-algoritmi

qsort - aliohjelman vikana on löysä tyypitys ja erityisesti se, ettei sille voi viedä parametrinä lisätietoa lajittelusta. STL:stä löytyy joukko algoritmeja, joita voidaan soveltaa STL:n omien tietorakenteiden lisäksi myös tavallisille taulukoille.

Edellisessä esimerkissä qsort-rivi voitaisiin korvata rivillä:

	  sort(x,x+KOKO);

Tällöin ei itse asiassa tarvita edes lajittelufunktiota, koska sort lajittelee oletuksena taulukon nousevaan järjestykseen edellyttäen että taulukon alkioita voidaan verrata < -operaattorilla.

Varsinainen etu sort-algoritmista saadaan, mikäli lajittelujärjestystä halutaan muuttaa tai lajittelufunktiolle halutaan antaa parametrejä. Parametrit pystytään toteuttamaan funktio-olioiden (joskus sanotaan myös funktoreiksi) avulla.

Seuraavassa esimerkissä merkkijonotaulukko lajitellaan ensin nousevaan järjestykseen luottaen string-luokan <-operaattoriin. Sitten taulukko lajitellaan laskevaan järjestykseen oman laskeva-vertailufunktion avulla. Tosin kirjastossa on valmiina funktio-oliot tämänkaltaisiin vertailuihin. Lopuksi en esimerkki, jossa jonot lajitellaan nousevaan järjestykseen jonon toisen kirjaimen perusteella. Tämä voitaisiin vielä tehdä qsort-funktiollakin, mutta jos se, monennenko kirjaimen mukaan lajittelu tehdään, halutaan parametriksi, olisi globaali muuttuja ainoa vaihtoehto qsort-funktiota käytettäessä.

sort-algoritmia (tai esimerkissä stable_sort, säilyttää "samansuuruisten" keskinäisen järjestyksen) kutsuttaessa luodaan tilapäinen (lajittelun ajan elävä) cVertaaPaikka funktio-olio, jonka konstruktorille välitetään lajiteltavan kirjaimen indeksi. Luokkaan määritellyn ()-operaattorin ansiosta luokaa edustavaa oliota voidaan kutsua funktiomaisesti kahdella merkkijojonolla.

lajittelu\lajstr.cpp - merkkijonotaulukon lajittelu sort-algoritmilla

	// Esimerkki sort-algoritmin käytöstä
	// Vesa Lappalainen 26.12.2001
	#include <iostream>
	#include <string>
	#include <algorithm>
	#include <functional>
	using std::string; using std::ostream_iterator; using std::cout;
	
	class cVertaaPaikka {             // Vertailuluokka joka vertaa jonoja paikassa
	  unsigned int paikka;            // paikka olevan kirjaimen mukaan
	 public:
	  cVertaaPaikka(unsigned int ipaikka) { paikka = ipaikka; }
	  // Jos on cVertaaPaikka vertaa(1); niin seuraavaa operaattoria voi kutsua
	  // "funktiomaisesti":  if ( vertaa(jono1,jono2) ) ...
	  bool operator() (const string &a, const string &b) const {
	    if  ( ( a.length() <= paikka ) ||
	          ( b.length() <= paikka ) )  return a.length() < b.length();
	    return a[paikka] < b[paikka];
	  }
	};
	
	bool laskeva(const string &a,const string &b)
	{
	  return b < a;
	}
	
	void tulosta(const string nimet[],int lkm)
	{
	  copy(nimet,nimet+lkm,ostream_iterator<string>(cout," ")); cout << "\n";
	}
	
	int main(void)
	{
	  const int lkm = 6;
	  string nimet[lkm] = { "Aku","Mikki","Roope","Hannu","Pelle","Sepe" };
	
	  // Nouseva:                              Aku Hannu Mikki Pelle Roope Sepe
	  sort(nimet,nimet+lkm);                          tulosta(nimet,lkm);
	
	  // Laskeva:                              Sepe Roope Pelle Mikki Hannu Aku
	  sort(nimet,nimet+lkm,laskeva);                  tulosta(nimet,lkm);
	  sort(nimet,nimet+lkm,std::greater<string>());   tulosta(nimet,lkm);
	
	  // Toisen kirjaimen mukaan:              Hannu Sepe Pelle Mikki Aku Roope
	  stable_sort(nimet,nimet+lkm,cVertaaPaikka(1));  tulosta(nimet,lkm);
	  // HUOM!  Sepe oli ennen Pelleä, koska stabiili lajittelu
	  return 0;
	}