Tehokas lajittelu on mielenkiintoinen probleema. Etenkin siihen liittyvä kysymys: montako vertailua n-kokoisen taulukon lajittelu vaatii? Esimerkiksi 256-alkioisen taulukon sortteeraus tarvitsisi vain 256+1 vertailua.
Oheisella apuohjelmalla voi optimoida pieniä inline sort3 - sort6 -funktioita. Ne ovat 3-4 kertaa nopeampia suorittaa, kuin stl:n sort-funktio. Koodi järjestää tiedostoon "xsort.cpp" minimimäärän tarvittavia vertailuja ja vaihtoja.
qsort -algoritmi hajottaa lajittelun nopeasti pieniin osaongelmiin. Jos niihin soveltaa tehokkaita osalajitteluja, koko qsort -algoritmin voi silloin räätälöidä moninkertaiseen nopeuteen. Ohjelmalla ei kannata generoida kovin suuria osalajittelutapauksia, koska silloin koodia generoituu niin paljon, että prosessori hyytyy sellaisen koodimössön kanssa. Esimerkiksi LAJITTELU_KOKO 8:lla koodia generoituu jo muutama satatuhatta riviä. (Valitan työkiireiden vuoksi kommenttien vähyyttä, mutta vastaan koodia koskeviin kysymyksiin kysyttäessä.)
//////////////////////////////////
// Lajittelufunktion generointi //
// JA 17.7.2006 //
//////////////////////////////////
#include <stdio.h>
#include <memory.h>
#define LAJITTELU_KOKO 4
class Laskuri
{
public:
Laskuri(void);
int* incx(void);
~Laskuri(void) {};
private:
int x[LAJITTELU_KOKO];
int y[LAJITTELU_KOKO];
int* kopio(void);
void reset(void);
};
Laskuri::Laskuri(void)
{
reset();
}
void Laskuri::reset(void)
{
int n=LAJITTELU_KOKO;
for (int i=0; i<n; i++)
x[i]=i; x[n-1]-=(int)0x01;
}
int* Laskuri::kopio(void)
{
int n=LAJITTELU_KOKO;
memcpy(y, x, sizeof(int)*n);
return y;
}
int* Laskuri::incx(void)
{
int n=LAJITTELU_KOKO;
int i=n-1, j;
while (i>=0)
{
if ((++x[i])==n)
{
--i;
}
else
{
for (j=0; j<i; j++)
if (x[j]==x[i]) break;
if (j==i)
{
if ((++i)==n)
return kopio();
else x[i]=-1;
}
}
}
return (int*)0;
}
class solmu
{
public:
solmu(void);
~solmu(void);
void aja(int*);
void print(FILE*);
private:
solmu *If;
solmu *Else;
int LastIf, LastElse;
void main(int*, int, int);
void print(FILE*, int*, int, int, int);
};
solmu::~solmu(void)
{
}
solmu::solmu(void)
{
memset(this, 0, sizeof(solmu));
}
void solmu::aja(int *r)
{
main(r, 0, 1);
}
void solmu::print(FILE *fi)
{
int k[LAJITTELU_KOKO];
int n=(int)LAJITTELU_KOKO;
for (int i=0; i<n; i++) k[i]=i;
fprintf(fi, "inline void sort%d(register int *r) {\n", n);
fprintf(fi, " register int tmp;\n");
print(fi, k, 0x00, 0x01, 1);
fprintf(fi, "}\n\n");
}
void VieritaYlos(int *r, int i, int j)
{
int tmp=r[j];
for (; j>i; j--)
r[j]=r[j-1]; r[i]=tmp;
}
void solmu::main(int *r, int i, int j)
{
int I=i;
int J=j;
if ((++J)==LAJITTELU_KOKO) ++I, J=I+1;
if (r[j]<r[i])
{
VieritaYlos(r, i, j);
if (J<LAJITTELU_KOKO)
{
if (If==(solmu*)0) If=new solmu;
If->main(r, I, J);
}
else LastIf=1;
}
else
{
if (J<LAJITTELU_KOKO)
{
if (Else==(solmu*)0) Else=new solmu;
Else->main(r, I, J);
}
else LastElse=1;
}
}
void Sisenna(FILE *F, int sisennys)
{
for (int i=0; i<sisennys; i++)
for (int j=0; j<3; j++)
fprintf(F, " ");
}
void TeeVaihdot(FILE *fi, int *b, int t)
{
int a[LAJITTELU_KOKO], i;
int n=LAJITTELU_KOKO, j;
for (i=j=0x00; i<n; i++)
if ((a[i]=i)!=b[i]) ++j;
if (j)
{
// vaihdot pareittain
for (i=0; i<n; i++)
for (j=i+0x01; j<n; j++)
if (a[i]==b[j]&&a[j]==b[i]&&a[i]!=-1)
{
Sisenna(fi, t);
fprintf(fi, "tmp=r[%d], r[%d]=r[%d], r[%d]=tmp;\n",
a[i], a[i], b[i], b[i]);
a[i]=a[j]=b[i]=b[j]=-1;
}
// ketjuvaihdot
do
{
for (i=j=0; i<n; i++)
if (a[i]!=-1&&a[i]!=b[i])
{a[j]=a[i]; b[j]=b[i]; ++j;}
if ((n=j)!=0)
{
Sisenna(fi, t);
fprintf(fi, "tmp=r[%d], r[%d]=r[%d], ", a[0], a[0], b[0]);
for (int etsi=b[0];;)
{
for (i=0; i<n; i++)
if (a[i]==etsi) break;
if (b[i] == a[0])
{
fprintf(fi, "r[%d]=tmp;\n", a[i]);
a[i]=a[0]=-1; --j; break;
}
else
{
fprintf(fi, "r[%d]=r[%d], ", a[i], b[i]);
etsi=b[i]; a[i]=b[i]=-1; --j;
}
}
}
}
while (j>1);
}
}
void solmu::print(FILE *fi, int *k, int i, int j, int t)
{
int I=i, J=j;
int n=sizeof(int);
int e[LAJITTELU_KOKO];
memcpy(e, k, n*LAJITTELU_KOKO);
if ((++J)==LAJITTELU_KOKO) ++I, J=I+1;
if (If && Else)
{
Sisenna(fi, t);
fprintf(fi, "if (r[%d]<r[%d]) {\n", k[j], k[i]);
VieritaYlos(k, i, j);
If->print(fi, k, I, J, t+1);
Sisenna(fi, t);
fprintf(fi, "} else {\n");
Else->print(fi, e, I, J, t+1);
Sisenna(fi, t);
fprintf(fi, "}\n");
}
else if (If)
{
If->print(fi, k, I, J, t);
}
else if (Else)
{
Else->print(fi, e, I, J, t);
}
else
{
if (LastIf && LastElse)
{
Sisenna(fi, t);
fprintf(fi, "if (r[%d]<r[%d]) {\n", k[j], k[i]);
VieritaYlos(k, i, j);
TeeVaihdot(fi, k, t+1);
Sisenna(fi, t);
fprintf(fi, "} else {\n");
TeeVaihdot(fi, e, t+1);
Sisenna(fi, t);
fprintf(fi, "}\n");
}
else if (LastIf)
{
VieritaYlos(k, i, j);
TeeVaihdot(fi, k, t);
}
else if (LastElse)
{
TeeVaihdot(fi, e, t);
}
}
}
void GeneroiSolmut(solmu *alku)
{
int *x;
Laskuri cou;
while ((x=cou.incx())!=(int*)0)
{
alku->aja(x);
}
}
void main(void)
{
FILE *F=fopen("xsort.cpp", "w");
solmu *alku=new solmu;
GeneroiSolmut(alku);
alku->print(F);
fclose(F);
}///////////////////////////////
// Ajoesimerkki parametrilla //
// #define LAJITTELU_KOKO 4 //
// Tiedosto: "xsort.cpp" //
///////////////////////////////
inline void sort4(register int *r) {
register int tmp;
if (r[1]<r[0]) {
if (r[2]<r[1]) {
if (r[3]<r[2]) {
tmp=r[0], r[0]=r[3], r[3]=tmp;
tmp=r[1], r[1]=r[2], r[2]=tmp;
} else {
if (r[3]<r[1]) {
tmp=r[0], r[0]=r[2], r[2]=r[1], r[1]=r[3], r[3]=tmp;
} else {
if (r[3]<r[0]) {
tmp=r[0], r[0]=r[2], r[2]=r[3], r[3]=tmp;
} else {
tmp=r[0], r[0]=r[2], r[2]=tmp;
}
}
}
} else {
if (r[3]<r[1]) {
if (r[2]<r[0]) {
tmp=r[0], r[0]=r[3], r[3]=tmp;
} else {
tmp=r[0], r[0]=r[3], r[3]=r[2], r[2]=tmp;
}
} else {
if (r[2]<r[0]) {
if (r[3]<r[2]) {
tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=tmp;
} else {
if (r[3]<r[0]) {
tmp=r[0], r[0]=r[1], r[1]=r[2], r[2]=r[3], r[3]=tmp;
} else {
tmp=r[0], r[0]=r[1], r[1]=r[2], r[2]=tmp;
}
}
} else {
if (r[3]<r[0]) {
tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
} else {
if (r[3]<r[2]) {
tmp=r[0], r[0]=r[1], r[1]=tmp;
tmp=r[2], r[2]=r[3], r[3]=tmp;
} else {
tmp=r[0], r[0]=r[1], r[1]=tmp;
}
}
}
}
}
} else {
if (r[2]<r[0]) {
if (r[3]<r[2]) {
tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=r[2], r[2]=tmp;
} else {
if (r[3]<r[0]) {
tmp=r[0], r[0]=r[2], r[2]=tmp;
tmp=r[1], r[1]=r[3], r[3]=tmp;
} else {
if (r[3]<r[1]) {
tmp=r[0], r[0]=r[2], r[2]=r[3], r[3]=r[1], r[1]=tmp;
} else {
tmp=r[0], r[0]=r[2], r[2]=r[1], r[1]=tmp;
}
}
}
} else {
if (r[3]<r[0]) {
if (r[2]<r[1]) {
tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=tmp;
} else {
tmp=r[0], r[0]=r[3], r[3]=r[2], r[2]=r[1], r[1]=tmp;
}
} else {
if (r[2]<r[1]) {
if (r[3]<r[2]) {
tmp=r[1], r[1]=r[3], r[3]=tmp;
} else {
if (r[3]<r[1]) {
tmp=r[1], r[1]=r[2], r[2]=r[3], r[3]=tmp;
} else {
tmp=r[1], r[1]=r[2], r[2]=tmp;
}
}
} else {
if (r[3]<r[1]) {
tmp=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
} else {
if (r[3]<r[2]) {
tmp=r[2], r[2]=r[3], r[3]=tmp;
} else {
}
}
}
}
}
}
}On varmaankin jokin järkevä syy sille, miksi näin:
if (r[1]<r[0]) {
if (r[2]<r[1]) {
if (r[3]<r[2]) {
if (r[0]<r[1]) {Eihän tuo viimeinen ehto voi olla tosi, jos ensimmäinen on jo ollut. Näin kuitenkin alkaa tuo jälkimmäinen koodilistauksesi. Vastaavia löytyy tuosta pätkästä useampiakin jo hyvin pikaisella vilkaisulla.
Hyvä ja mielenkiintoinen kysymys, johon en osaa vastata. Kuitenkin if- ja else -lohkot suorittavat erilaiset vaihdot. Algoritmin lajittelu käy pöytämallina seuraavasti, jos lajiteltavana ovat esimerkiksi luvut 4, 3, 1, 5, 2;
4, 3, 1, 5, 2
3 < 4 => tosi
3, 4, 1, 5, 2
1 < 3 => tosi
1, 3, 4, 5, 2
...jne.
Lukujen vierittäminen taulukossa yhdellä askeleella tekee aina osan tulevista vertailuista tarpeettomiksi, jolloin vertailun tulos olisi aina tosi tai epätosi. Koodin print –funktiossa:
else if (If)
{
If->print(fi, k, I, J, t);
}
else if (Else)
{
Else->print(fi, e, I, J, t);
}karsii pois ne vertailut, joiden tuloksena on aina ollut joko tosi tai epätosi. Ehkä on olemassa sellainen algoritmi, joka generoisi n-alkiota sisältävälle taulukolle enintään n kappaletta vertailuja - tai vieläkin vähemmän.
Koodivinkin kuvauksessa on vakava virhe. N-kokoista taulukkoa ei voi yleisesti järjestää N+1 vertailulla. Näkeehän sen generoidusta koodistakin: sort6 eli 6-alkioisen taulukon järjestely tekee keskimäärin 11,05 ja enintään 15 vertailua.
Määrän voi myös testata seuraavalla koodilla:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
struct myint {
int val;
myint(int val_ = 0): val(val_) {}
};
int compare_count = 0;
bool operator < (myint a, myint b) {
compare_count += 1;
// std::cout << a.val << " < " << b.val << "?\n";
return a.val < b.val;
}
#include "xsort.cpp"
int main() {
std::vector<int> a {0, 1, 2, 3, 4, 5};
std::map<int, int> counts;
double compare_count_sum = 0, test_count = 0;
do {
std::vector<myint> b(a.begin(), a.end());
compare_count = 0;
sort6(&b[0]);
counts[compare_count] += 1;
test_count += 1;
compare_count_sum += compare_count;
} while (std::next_permutation(a.begin(), a.end()));
for (auto c: counts) {
std::cout << c.first << " vertailua " << c.second << " tapauksessa.\n";
}
std::cout << "Keskiarvo " << compare_count_sum / test_count << "\n";
}Tässä xsort.cpp sisältää sort6-funktion, jossa register int -tyypin tilalle on vaihdettu myint vertailujen laskemista varten. Ohjelma käy läpi kaikki taulukon järjestykset ja laskee, montako vertailua kunkin järjestämiseen menee.
Sinänsä ihan kiinnostava kyhäelmä mutta jos muistin käyttö on luokkaa O(C*2^n), missä C on tähtitieteellisen suuri vakio, niin käyttökelvotonhan tuo käytännössä on. Toisaalta jos lajittelet muutaman alkion kokoista taulukkoa, niin vertailu qsort-funktioon ei ole kovin kiinnostava - insertion sort -proseduurikin on itseasiassa paljon parempi vaihtoehto kuin quick sort kun järjestettävän taulukon koko liikkuu muutamissa kymmenissä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.