Flettesortering

[Vial]

void flett(int t[], int v, int m, int h)
{
int * ht = new int[v - h+1];
int i = 0,j = v, k = m + 1;
while (j <= m && k <= h)
{
 ht[i++] = (t[j] <= t[k]) ? t[j++] : t[k++];
}
while (k <= m)
{
 ht[i++] = t[j++];
}
for (i=v;i<k;i++)
{
 t[i] = ht[i-v];
}

} // ends void flett


int flettesort(int t[], int v, int h)
{
clock_t start, end;
start = clock();
if (v < h)
{
 int m = (v+h)/2;
  flettesort(t,v,m);
  flettesort(t,m+1,h);
 flett(t,v,m,h);
}
end = clock();
cout << "Flettesort fullført! " << endl;
for (int i=0;i<h;i++)
{
cout << t[i] << " ";
}
return (end - start);
}

 

Har denne koden for flettesortering for en oblig på skolen. Men skyt meg om jeg tar feil - men i den første funksjonen - void flett(...) - vil ikke t[] bare forsvinne inn i intet når den er ferdigkjørt? Burde kanskje ha en global array her istedenfor å bruke den i funksjonene på den måten jeg har gjort, men det passer ikke i programstrukturen. Anyways - går det ann å passe videre arrayer via funksjoner?

[<BøNilzen>]

Nei, den vil ikke det.

Når du tar imot et helt array i en funksjon og endrer det endrer det seg også

i funksjonen som kalte "flett" funksjonen.

hvis du derimot hadde tatt i mot kun ett element, f.eks. t[7] og endret det ville det ikke ha endret seg.

 

(Litt dårlig formulert kanskje)

 

Edit: Jeg gidder ikke skyte deg, for jeg er for ung til å komme i fengsel allerede

Endret 29. januar 2004 av <BøNilzen>

[☀ ❄]

int t[] betyr praktisk talt det samme som int t*. Med andre ord, funksjonen lager ikke en kopi av arrayet, den bruker den som ble passet inn, noe som igjen betyr at arrayet ikke går ut av scope når funksjonen returnerer. (Hvis du ikke forstår dette 100%, foreslår jeg at du leser mer om pointers og references, og om pass-by-value vs. pass-by-reference).

 

Med mindre du _må_ bruke et array (av en eller annen bisarr grunn, f.eks. teite lærere), anbefaler jeg å bruke en std::vector.

[Vial]

er ikke helt stødig på std::vector enda, så tror jeg lar det utgå (denne måten er enklest å skjønne for meg).

 

Men er det noen som vet hva flettesortering heter på engelsk? Ønsker med flere ressurser på akkurat denne sorteringsmetoden... hva er egentlig flette på engelsk? Braid?

Endret 29. januar 2004 av Vial

[Paull]

For øvrig:

int * ht = new int[v - h+1];

 

Gir ikke denne en minnelekasje, siden det ikke kalles delete på ht ved retur fra flett ?

[Vial]

har ikke så mye å si. Det systemet som kneler for den minnelekasjen er ikke verdt min algoritme

 

Nå har jeg faktisk blitt ferdig med obligen! Iallfall sorteringene. Eneste som gjenstår nå er tidtagingen. Som dere ser av koden så antok jeg at tiden som skulle måles var hvor lang tid cpu'en brukte på å prosessere algoritmen - men nå ser jeg plutselig at det kanskje er feil. Det skal måles hvor mange enkle operasjoner som skjer. Ikke skjønner jeg at det har noenting å si på tiden, men hvis det er det som må til for at denne skal bli godkjent, så er det det som skal til for at denne blir godkjent.

 

Neste oblig er fin: "I denne obligen skal dere lage et bondesjakk spill. Ettersom et 2D spill ville vært for _ENKELT_ så ...blablabla"

 

Blir spennende.

[GeirGrusom]

Minnelekasjer blir fikset av gc uansett, så det går vel bra.

[Paull]

Hø? Er vel ikke gc i C++ ?

[☀ ❄]

Selv om Bjarne drømmer om en rask og effektiv garbage collector i C++, vet ikke jeg om noen implementasjon som inneholder noen. Minnelekasjer er best unngått uansett.

[A_N_K]

Boehm gc har vel eksistert lenge? Vet ikke hvor rask denne er i forhold til Java sin f.eks, men gc er uansett lite brukt i C++ så vidt jeg vet.

Edit: Den idiomatiske i løsningen i C++ er vel smart pointers, f.eks Boost eller Loki.

Endret 3. februar 2004 av A_N_K