Tehokas lajittelu on mielenkiintoinen probleema. Etenkin siihen liittyvä kysymys: montako vertailua n-kokoisen taulukon lajittelu vaatii? Esimerkiksi 256-alkioisen taulukon sortteeraus tarvitsee vain 256+1 vertailua.
Vuosia sitten eräässä signaalinkäsittelyyn liittyvässä algoritmissa pullonkaulaksi muodostui qsort-algoritmin hitaus. Vaikka lopullinen 16-alkion optimoitu lajittelufunktio vaatikin itselleen oman kovon, se ei ollut ongelma. Kun qsort "pohdiskeli" vasta ensimmäisiä vaihtojaan, optimoitu sort16 oli jo maalissa.
Oheisella riisutulla ja yksinkertaisella apuohjelmalla voi optimoida pieniä inline sort3 - sort6 -funktioita. Ne ovat vain 3-4 kertaa nopeampia suorittaa, kuin stl:n sort-funktio, mutta siitäkin voi olla apua jossain spesifisessä lajittelutapauksessa.
Koodi järjestää tiedostoon "xsort.cpp" minimimäärän tarvittavia vertailuja ja vaihtoja. Ohjelmalla ei kannata generoida sen suurempia lajittelutapauksia, koska silloin pitää jo ruveta hajottamaan ja hallitsemaan. Toinen syy on se, että koodia generoituu niin paljon, ettei prosessori voi enää hyödyntää välimuistiaan.
Apuohjelman ensisijaisena tarkoituksena on herättää keskustelua, että vertailuja tarvitaan n-alkioita sisältävässä lajittelutapauksessa n+1 kappaletta. Kenties sitten olisi mahdollista laatia sellainen yleinen lajittelualgoritmi, joka käyttäisi minimäärän vertailuja ja vaihtoja, mene ja tiedä.
Ohjelman käyttöohjeista sen verran, että parametrille LAJITTELU_KOKO annetaan haluttu arvo. Sen jälkeen ohjelma dumppaa valmiin lajittelufunktion tiedostoon "xsort.cpp". (Valitan työkiireiden vuoksi kommenttien vähyyttä, mutta vastaan koodia koskeviin kysymyksiin parhaani mukaan.)
//////////////////////////////////
// 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;
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
{
if (J<LAJITTELU_KOKO)
{
if (Else==(solmu*)0) Else=new solmu;
Else->main(r, I, J);
}
}
}
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
{
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");
}
}
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, jossa parametrina //
// #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]) {
if (r[0]<r[1]) {
tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=r[2], r[2]=tmp;
} else {
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]) {
if (r[0]<r[1]) {
tmp=r[0], r[0]=r[2], r[2]=tmp;
tmp=r[1], r[1]=r[3], r[3]=tmp;
} else {
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]) {
if (r[0]<r[2]) {
tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
} else {
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]) {
if (r[2]<r[0]) {
tmp=r[0], r[0]=r[1], r[1]=r[3], r[3]=tmp;
} else {
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]) {
if (r[1]<r[0]) {
tmp=r[0], r[0]=r[3], r[3]=tmp;
tmp=r[1], r[1]=r[2], r[2]=tmp;
} else {
tmp=r[0], r[0]=r[3], r[3]=r[1], r[1]=r[2], r[2]=tmp;
}
} else {
if (r[3]<r[0]) {
if (r[1]<r[0]) {
tmp=r[0], r[0]=r[2], r[2]=r[1], r[1]=r[3], r[3]=tmp;
} else {
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]) {
if (r[1]<r[2]) {
tmp=r[1], r[1]=r[3], r[3]=r[2], r[2]=tmp;
} else {
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]) {
if (r[2]<r[1]) {
tmp=r[1], r[1]=r[3], r[3]=tmp;
} else {
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 {
}
}
}
}
}
}
}Aihe on jo aika vanha, joten et voi enää vastata siihen.