Tehokas lajittelu on mielenkiintoinen probleema. Etenkin siihen liittyvä kysymys: montako vertailua n-kokoisen taulukon lajittelu vaatii? Voi olla kova väite, mutta esimerkiksi 256-alkioisen taulukon lajittelu vaatii enintään 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, koska 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 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 enemmän osoittaa, että vertailuja tarvitaan n-alkioita sisältävässä lajittelutapauksessa enintään n+1 kappaletta, eikä jotain n*log(n) määrää.
Ohjelman käyttöohjeista sen verran, että anna parametrille LAJITTELU_KOKO haluamasi arvo, ja aja ohjelma. Ohjelma dumppaa käyttövalmiin lajittelufunktion tiedostoon "xsort.cpp". Jos kommenttien vähyys aiheuttaa jotain kysymyksiä, vastaan paremmin sitten niihin.
//////////////////////////////////
// Lajittelufunktion generointi //
// JA 10.7.2006 //
//////////////////////////////////
#include <stdio.h>
#include <conio.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];
int n=LAJITTELU_KOKO, i, j;
for (i=0x00; i<n; i++) a[i]=i;
// poista samat
for (i=0; i<n; i++)
if (a[i]==b[i]) a[i]=b[i]=-1;
// vaihdot pareittain
for (i=0; i<n; i++)
for (j=i+1; j<n; j++)
{
if (a[i]==b[j] && a[j]==b[i] && a[i]!=-1 && b[j]!=-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;
}
}
// alusta ketjuvaihto
for (i=j=0; j<n; j++)
if (a[j]!=-1 && b[j]!=-1)
{a[i]=a[j], b[i]=b[j]; ++i;}
if ((n=i) != 0x00)
{
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 ((int)b[i]==(int)a[0])
{fprintf(fi, "r[%d]=tmp;\n", a[i]); break;}
else {fprintf(fi, "r[%d]=r[%d], ", a[i], b[i]); etsi=b[i];}
}
}
}
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);
}//////////////////////////////////
// Ohjelman esimerkkiajo, jossa //
// #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.