---

Hejsa NG

Jeg har i skolen fået stillet en opgave som lyder :
Bevis at en enhver sammenlignings-baseret sorterings algoritme, der skal
sortere 4 elementer, skal bruge minimum 5 sammenligninger for et eller
andet input, og lav denne.

Jeg har løst den ved banale if-sætninger og kan få det til at gå op, men er
ikke helt tilfreds, og tror heller ikke det accepteres at man blot løser
den med if-sætninger hele vejen igennem, og vil derfor gerne lave noget
mere komplekst, hvor jeg så er gået i stå.

Hver gang jeg når frem til en løsning, bruger denne minimum 6
sammenligninger,
og jeg har prøvet alt muligt med for og while - løkker og har også tænkt på
noget recursion, selv om dette ikke er mit stærke område :)

Men jeg er nået til følgende "program"/funktion :

public fourSort(int arr[])
{
int tmp[0] = arr[0];

for(int i = 1; i < 4; i++)
{
int numberOfElements = countElements(tmp);
int mid = numberOfElements % 2;

if(tmp[mid] <= arr[i])
{
mid++;
if(tmp[mid] <= arr[i] && tmp[mid] != "")
{
tmp[mid++] = arr[i];
}
else
{
tmp = moveElements(1, tmp);
tmp[mid] = arr[i]
}
}
else
{
mid--;
if(tmp[mid] <= arr[i])
{
tmp = moveElements(2, tmp);
tmp[mid++] = arr[i];
}
else
{
tmp = moveElements(3, tmp);
tmp[mid] = arr[i]
}
}
}
}

public moveElements(int elements, int tmp[]) /* elements : antallet af
elementer der skal flyttes, tmp : det array de skal flyttes i */
{
int tmp_arr[] = new int[4];

if(elements == 3)
{
int endPos = 0;
}
else if(elements == 2)
{
int endPos = 1;
}
else if(elements == 1)
{
int endPos = 2;
}

for(int i = 2, j = 3; i >= endPos; i--, j--)
{
tmp_arr[j] = tmp[i);
}

return tmp_arr;
}


public countElements(int tmp[])
{
int numberOfElements;
for(int i = 0; i <= tmp.length; i++)
{
if(tmp[i] != "")
{
numberOfElements++;
}
}

return numberOfElements;
}


--------------------
Det skal lige siges at jeg næsten er HELT ny i Java, så der er nok en masse
fejl :)

Jeg har fundet at min "overflødige" sammenligning ligger når man skal
probbe/sortere
det andet element ind i resultat arrayet (tmp[]) der er det jo bare : større
end eller mindre
end og så probber man den ind, men jeg kan simpelthen ikke se hvordan jeg
skal løse
dette ?

Håber der er nogle der kan hjælpe mig! :)


Med venlig hilsen
Ronni
ronni1@ofir.dk

---

In <9s1jf1$552$1@sunsite.dk> "Ronni \(The real one:\)" <ronni1@ofir.dk> writes:

>Hejsa NG

>Jeg har i skolen fået stillet en opgave som lyder :
>Bevis at en enhver sammenlignings-baseret sorterings algoritme, der skal
>sortere 4 elementer, skal bruge minimum 5 sammenligninger for et eller
>andet input, og lav denne.

Dum opgave, da det kraever 6 sammenligninger og ikke 5.

/Martin




--
Danske musikere tjener penge ved ulovlig softwarekopiering.

---

> >Jeg har i skolen fået stillet en opgave som lyder :
> >Bevis at en enhver sammenlignings-baseret sorterings algoritme, der skal
> >sortere 4 elementer, skal bruge minimum 5 sammenligninger for et eller
> >andet input, og lav denne.
>
> Dum opgave, da det kraever 6 sammenligninger og ikke 5.
>
> /Martin
>
Det kan lade sig gøre med 5 sammenligninger!!!

Her er mit if sætning "program" som gør det :

public int tmp_arr[] = new int[4];

tmp_arr[0] = arr[0];
/*-----------------------------*/
if(tmp_arr[0] <= arr[1])
{
tmp_arr[1] = arr[1]
}
else
{
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[1];
}
/*-----------------------------*/
if(tmp_arr[1] <= arr[2])
{
tmp_arr[2] = arr[2];
}
else
{
if(tmp_arr[0] <= arr[2])
{
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[2];
}
else
{
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[2];
}

}
/*-----------------------------*/
if(tmp_arr[1] <= arr[3])
{
if(tmp_arr[2] <= arr[3])
{
tmp_arr[3] = arr[3];
}
else
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = arr[3];
}
}
else
{
if(tmp_arr[0] <= arr[3])
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[3];
}
else
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[3];
}
}
/*-----------------------------*/

Hvis du sætter dig med papir og blyant, og tager arrayet arr[4,3,2,1]
og sortere det så resultatet bliver tmp_arr[1,2,3,4] vil du have brugt
5 sammenligninger!

/Ronni
ronni1@ofir.dk

---

In <9s1l7k$a0j$1@sunsite.dk> "Ronni \(The real one:\)" <ronni1@ofir.dk> writes:

>Hvis du sætter dig med papir og blyant, og tager arrayet arr[4,3,2,1]
>og sortere det så resultatet bliver tmp_arr[1,2,3,4] vil du have brugt
>5 sammenligninger!

Dit program virker ikke, hvis arr indeholder tallene i raekkefoelgen: 4,1,3,2

Mvh
Martin





--
Danske musikere tjener penge ved ulovlig softwarekopiering.

---

> Dit program virker ikke, hvis arr indeholder tallene i raekkefoelgen:
4,1,3,2
>
> Mvh
> Martin

Jo det gør :)

Ved tal-rækkefølgen arr[4,1,3,2] får jeg :

tmp[0] = 4 // ved første linie tmp_arr[0] = arr[0];

Første if sætning / første sammenligning! :
if(tmp_arr[0] <= arr[1]) // er 4 <= 1 nej -> derfor rykker vi til else og
får
{}
else
{
tmp_arr[1] = tmp_arr[0]
tmp_arr[0] = arr[1];
}

hvorefter vi har :
tmp_arr[0] = 1
tmp_arr[1] = 4

Anden if sætning / anden sammenligning! :
if(tmp_arr[1] <= arr[2]) // er 4 <= 3 nej -> derfor rykker vi til else og
får
{}
else
{
// Tredje if sætning / tredje sammenligning! :
if(tmp_arr[0] <= arr[2]) // er 1 <= 3 ja -> derfor rykker vi ind i if
sætningen og får
{
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[2];
}
else
{}
}

hvorefter vi har :
tmp_arr[0] = 1
tmp_arr[1] = 3
tmp_arr[2] = 4

Fjerde if sætning / fjerde sammenligning! :
if(tmp_arr[1] <= arr[3]) // er 3 <= 2 nej -> derfor rykker vi til else og
får
{}
else
{
// Femte if sætning / femte og sidste sammenligning!
if(tmp_arr[0] <= arr[3]) er 1 <= 2 ja -> derfor rykker vi ind i if
sætningen og får
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[3];
}
else
{ }
}

hvorefter vi har :
tmp_arr[0] = 1
tmp_arr[1] = 2
tmp_arr[2] = 3
tmp_arr[3] = 4

Hvilket var efter 5 sammenligninger, ergo det virker - efter min
overbevisning :)

Hvilket efter min mening også er ret logisk, da hvis du går slavisk ned
igennem koden
har en if sætning i starten som udføres, to if sætninger i den anden
afdeling som udføres
og to if sætninger i den tredje afdeling som udføres -> altså 5 i alt.

Hvor mange fik du ?

/Ronni

---

Det her funker og tæller også hvor mange sammenligninger der har været
Du kan ikke tvinge den over 5! :) Så det kan lade sig gøre, jeg efterlyser
bare
noget mere "ordenligt" programmeret noget
---------------------------------------------------------------------------


public class s
{

public static void main(String args[])
{
int arr[] = {4,1,3,2};
int tmp_arr[] = new int[4];
int nrcompares = 0;

tmp_arr[0] = arr[0];

if(tmp_arr[0] <= arr[1])
{
tmp_arr[1] = arr[1];
nrcompares++;
}
else
{
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[1];
nrcompares++;
}


if(tmp_arr[1] <= arr[2])
{
tmp_arr[2] = arr[2];
nrcompares++;
}
else
{
nrcompares++;

if(tmp_arr[0] <= arr[2])
{
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[2];
nrcompares++;
}
else
{
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[2];
nrcompares++;
}

}


if(tmp_arr[1] <= arr[3])
{
nrcompares++;

if(tmp_arr[2] <= arr[3])
{
tmp_arr[3] = arr[3];
nrcompares++;
}
else
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = arr[3];
nrcompares++;
}
}
else
{
nrcompares++;

if(tmp_arr[0] <= arr[3])
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = arr[3];
nrcompares++;
}
else
{
tmp_arr[3] = tmp_arr[2];
tmp_arr[2] = tmp_arr[1];
tmp_arr[1] = tmp_arr[0];
tmp_arr[0] = arr[3];
nrcompares++;
}
}

for(int i = 0; i <= tmp_arr.length - 1; i++)
{
System.out.println("tal i er : " + tmp_arr[i]);
}

System.out.println("Antal sammenligninger : " + nrcompares);
}

}

--------------------------------------------------------------------

/Ronni

---

"Martin Moller Pedersen" <tusk@daimi.au.dk> skrev i en meddelelse
news:9s1kcb$v88$1@news.net.uni-c.dk...
> In <9s1jf1$552$1@sunsite.dk> "Ronni \(The real one:\)"
<ronni1@ofir.dk> writes:
>
> >Hejsa NG
>
> >Jeg har i skolen fået stillet en opgave som lyder :
> >Bevis at en enhver sammenlignings-baseret sorterings
algoritme, der skal
> >sortere 4 elementer, skal bruge minimum 5 sammenligninger for
et eller
> >andet input, og lav denne.
>
> Dum opgave, da det kraever 6 sammenligninger og ikke 5.
>

En bucket sort kan gøre det uden sammenligning.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

Soren 'Disky' Reinke wrote:

> En bucket sort kan gøre det uden sammenligning.

Hvordan dog det?

---

"Dennis Thrysøe" <qabi@qabi.dk> skrev i en meddelelse
news:3BE659FF.90303@qabi.dk...
> Soren 'Disky' Reinke wrote:
>
> > En bucket sort kan gøre det uden sammenligning.
>
> Hvordan dog det?

Hvis du skal sortere tal der kan være i intervallet 1-10

Laver du ti spande 'buckets' en til vær mulig værdi.

Så tager du det første tal lad os sige '7' altså skal det i spand
nummer 7, så spand tælleren tælles 1 op.

Det samme gør du med resten af tallene. Til sidst scanner du
spandene , antallet i spandene fortæller hvor mange der landede
der.

Problemmer med denne sorteringsalgoritme er at hvis du skal
sortere tal fra 0-1 milliard, skal du have 1 milliard spande !

Men den er lynende hurtigt.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

Hmm. Nifty. Ihvertfald sådan ... på et akademisk plan ;)

-dennis


Soren 'Disky' Reinke wrote:

> "Dennis Thrysøe" <qabi@qabi.dk> skrev i en meddelelse
> news:3BE659FF.90303@qabi.dk...
>
>>Soren 'Disky' Reinke wrote:
>>
>>
>>>En bucket sort kan gøre det uden sammenligning.
>>>
>>Hvordan dog det?
>>
>
> Hvis du skal sortere tal der kan være i intervallet 1-10
>
> Laver du ti spande 'buckets' en til vær mulig værdi.
>
> Så tager du det første tal lad os sige '7' altså skal det i spand
> nummer 7, så spand tælleren tælles 1 op.
>
> Det samme gør du med resten af tallene. Til sidst scanner du
> spandene , antallet i spandene fortæller hvor mange der landede
> der.
>
> Problemmer med denne sorteringsalgoritme er at hvis du skal
> sortere tal fra 0-1 milliard, skal du have 1 milliard spande !
>
> Men den er lynende hurtigt.
>
> --
> With many Thanks
>
> Soren ' Disky ' Reinke ICQ #1413069
> http://www.disky-design.dk/fish
> Remove IHSYD from email address when replying by email
>
>
>
>

---

Soren 'Disky' Reinke wrote:

> "Dennis Thrysøe" <qabi@qabi.dk> skrev i en meddelelse
> news:3BE659FF.90303@qabi.dk...
> > Soren 'Disky' Reinke wrote:
> >
> > > En bucket sort kan gøre det uden sammenligning.
> >
> > Hvordan dog det?
>
> Hvis du skal sortere tal der kan være i intervallet 1-10
>
> Laver du ti spande 'buckets' en til vær mulig værdi.
>
> Så tager du det første tal lad os sige '7' altså skal det i spand
> nummer 7, så spand tælleren tælles 1 op.
>
> Det samme gør du med resten af tallene. Til sidst scanner du
> spandene , antallet i spandene fortæller hvor mange der landede
> der.
>
> Problemmer med denne sorteringsalgoritme er at hvis du skal
> sortere tal fra 0-1 milliard, skal du have 1 milliard spande !

Hov - er det ikke counting sort du beskriver? Bucket sort har
et antal spande som hver indeholder et antal underintervaller
af et givet interval. Når input er fordelt i disse spande laves der
en insertion sort på hver spand (sammenligning!) og spandene
(listerne) hægtes sammen til output.

Ulrik Magnusson

---

> > Problemmer med denne sorteringsalgoritme er at hvis du skal
> > sortere tal fra 0-1 milliard, skal du have 1 milliard spande
!
>
> Hov - er det ikke counting sort du beskriver? Bucket sort har
> et antal spande som hver indeholder et antal underintervaller
> af et givet interval. Når input er fordelt i disse spande laves
der
> en insertion sort på hver spand (sammenligning!) og spandene
> (listerne) hægtes sammen til output.

Det kan man også kalde den, men hvis man kun skal sortere tal er
det ligegyldigt. Men hvis det er objekter der skal sorteres ud
fra en værdie, skal man bruge en linked liste i hver spand.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

In <tv3G7.104$Ba5.3427237916@news.euroconnect.net> "Soren 'Disky' Reinke" <disky@disky-design.ihsyd.dk> writes:

>> > Problemmer med denne sorteringsalgoritme er at hvis du skal
>> > sortere tal fra 0-1 milliard, skal du have 1 milliard spande
>!
>>
>> Hov - er det ikke counting sort du beskriver? Bucket sort har
>> et antal spande som hver indeholder et antal underintervaller
>> af et givet interval. Når input er fordelt i disse spande laves
>der
>> en insertion sort på hver spand (sammenligning!) og spandene
>> (listerne) hægtes sammen til output.

>Det kan man også kalde den, men hvis man kun skal sortere tal er
>det ligegyldigt. Men hvis det er objekter der skal sorteres ud
>fra en værdie, skal man bruge en linked liste i hver spand.

>--
>With many Thanks

>Soren ' Disky ' Reinke ICQ #1413069
>http://www.disky-design.dk/fish
>Remove IHSYD from email address when replying by email


Nemlig. Det var egentlig det, jeg tænkte på med min kommentar
om hvad han ville gøre hvis der var flere ens værdier.
Der er flere andre sorteringsmetoder, hvor der sker noget uventet
hvis fx alle nøgler er ens.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Soren 'Disky' Reinke wrote:

> > Hov - er det ikke counting sort du beskriver? Bucket sort har
> > et antal spande som hver indeholder et antal underintervaller
> > af et givet interval. Når input er fordelt i disse spande laves
> der
> > en insertion sort på hver spand (sammenligning!) og spandene
> > (listerne) hægtes sammen til output.
>
> Det kan man også kalde den, men hvis man kun skal sortere tal er
> det ligegyldigt.

Er hvad ligegyldigt? Det er to forskellige algoritmer, som dog minder
om hinanden - de sorterer begge noget, hvor man kender intervallet
for værdierne i input.

Forskellen er at man i bucket sort fordeler input i et antal spande
som hver er en delmængde af input. Spandene sorteres og hægtes
sammen. I counting sort bruger man et tællearray som beskriver,
ikke indeholder, input.

http://www.nist.gov/dads/HTML/bucketsort.html
http://www.nist.gov/dads/HTML/countingsort.html

Ulrik Magnusson

---

>
> Forskellen er at man i bucket sort fordeler input i et antal
spande
> som hver er en delmængde af input. Spandene sorteres og hægtes
> sammen. I counting sort bruger man et tællearray som beskriver,
> ikke indeholder, input.
>
> http://www.nist.gov/dads/HTML/bucketsort.html
> http://www.nist.gov/dads/HTML/countingsort.html

Så findes der flere slags bucketsort. Jeg har kendt begge de
slags algoritmer som værende bucketsort

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

In <V9qF7.75$vO4.2064634904@news.euroconnect.net> "Soren 'Disky' Reinke" <disky@disky-design.ihsyd.dk> writes:


>"Martin Moller Pedersen" <tusk@daimi.au.dk> skrev i en meddelelse
>news:9s1kcb$v88$1@news.net.uni-c.dk...
>> In <9s1jf1$552$1@sunsite.dk> "Ronni \(The real one:\)"
><ronni1@ofir.dk> writes:
>>
>> >Hejsa NG
>>
>> >Jeg har i skolen fået stillet en opgave som lyder :
>> >Bevis at en enhver sammenlignings-baseret sorterings
>algoritme, der skal
>> >sortere 4 elementer, skal bruge minimum 5 sammenligninger for
>et eller
>> >andet input, og lav denne.
>>
>> Dum opgave, da det kraever 6 sammenligninger og ikke 5.
>>

>En bucket sort kan gøre det uden sammenligning.

>--
>With many Thanks

>Soren ' Disky ' Reinke ICQ #1413069
>http://www.disky-design.dk/fish
>Remove IHSYD from email address when replying by email


Hmm, det er vel ikke en specielt relevant oplysning, når opgaven
har som udgangspunkt at det er en sammenligningsbaseret sortering.

Hvad har du forresten tænkt dig at din bucketsort skal gøre, hvis
du sætter den til at sortere 4 elementer med samme nøgle ?

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

> Hvad har du forresten tænkt dig at din bucketsort skal gøre,
hvis
> du sætter den til at sortere 4 elementer med samme nøgle ?

Hvad tænker du på ?

Så skal den bare tælle bucket counteren op 4 gange, så den bucket
de værdier lander i indeholder '4'

Men denne sorteringsmetode er ikke altid anvendeligt hvis min-max
er et stort område.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

> Men denne sorteringsmetode er ikke altid anvendeligt hvis min-max
> er et stort område.

Nej, eller hvis du forsøger at sortere floating points

Med venlig hilsen,
Jacob Møller
www.kiloo.dk

---

"Jacob Møller" <jacob@jvector.dk> skrev i en meddelelse
news:9s5qk7$16ls$1@news.cybercity.dk...
>
> > Men denne sorteringsmetode er ikke altid anvendeligt hvis
min-max
> > er et stort område.
>
> Nej, eller hvis du forsøger at sortere floating points

Jo det kan du nu godt alligevel. Da et floating point tal
stadigvæk er et unikt nummer.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

Soren 'Disky' Reinke wrote:

>
> "Jacob Møller" <jacob@jvector.dk> skrev i en meddelelse
> news:9s5qk7$16ls$1@news.cybercity.dk...
>>
>> > Men denne sorteringsmetode er ikke altid anvendeligt hvis
> min-max
>> > er et stort område.
>>
>> Nej, eller hvis du forsøger at sortere floating points
>
> Jo det kan du nu godt alligevel. Da et floating point tal
> stadigvæk er et unikt nummer.

Men det er nok ikke særlig effektivt, da du så skal undersøge alle
floating point tal mellem to intervaller og bare mellem 0 og 1 er der
fandme mange, med 10 eller 12 decimalers præcision (eller hvor mange
det nu er).

Mvh.
Martin Ehmsen
--
"Life is good for only two things,
discovering mathematics and teaching mathematics"
Siméon Poisson

---

"Martin Ehmsen" <thames@get2net.dk> skrev i en meddelelse
news:9s5t0f$dum$1@sunsite.dk...
> Soren 'Disky' Reinke wrote:
>
> >
> > "Jacob Møller" <jacob@jvector.dk> skrev i en meddelelse
> > news:9s5qk7$16ls$1@news.cybercity.dk...
> >>
> >> > Men denne sorteringsmetode er ikke altid anvendeligt hvis
> > min-max
> >> > er et stort område.
> >>
> >> Nej, eller hvis du forsøger at sortere floating points
> >
> > Jo det kan du nu godt alligevel. Da et floating point tal
> > stadigvæk er et unikt nummer.
>
> Men det er nok ikke særlig effektivt, da du så skal undersøge
alle
> floating point tal mellem to intervaller og bare mellem 0 og 1
er der
> fandme mange, med 10 eller 12 decimalers præcision (eller hvor
mange
> det nu er).

Helt enig, jeg siger ikke den altid er god men den kan bruges :)

Men som en skrev, fra et teoretisk synspunkt er den god.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

Soren 'Disky' Reinke wrote:

> "Martin Moller Pedersen" <tusk@daimi.au.dk> skrev i en meddelelse
> news:9s1kcb$v88$1@news.net.uni-c.dk...
> > In <9s1jf1$552$1@sunsite.dk> "Ronni \(The real one:\)"
> <ronni1@ofir.dk> writes:
> >
> > >Hejsa NG
> >
> > >Jeg har i skolen fået stillet en opgave som lyder :
> > >Bevis at en enhver sammenlignings-baseret sorterings
> algoritme, der skal
> > >sortere 4 elementer, skal bruge minimum 5 sammenligninger for
> et eller
> > >andet input, og lav denne.
> >
> > Dum opgave, da det kraever 6 sammenligninger og ikke 5.
> >
>
> En bucket sort kan gøre det uden sammenligning.

men counting sort var lidt sjovere at implementere - her i en
version som forventer at alle tal i ar er >= min og <= max. Det
skal da lige nævnes at dennes performance falder stejlt ved
store forskelle på min og max (der laves et array af størrelsen
((max+1)-min) for hvert kald - uanset antal elementer i ar.

public class s
{

// for ints fra og med min og til og med max
static int[] countingSort( int[] ar, int min, int max )
{
int[] countArray = new int[(max+1)-min];
for( int i = 0; i < ar.length; i++ )
{
++countArray[ ar[i]-min ];
}
// nu indeholder countArray[n-min] antal forekomster af tallet n
for( int i = min+1; i < max+1; ++i )
{
countArray[i-min] += countArray[i-min-1];
}
// nu indeholder countArray[n-min] antal forekomster af tal <= n
int[] res = new int[ar.length];
for( int i = ar.length; --i >= 0; )
{
// indsættelse af ar[i] på dets plads
res[countArray[ar[i]-min]-1] = ar[i];
// dekrementering af antal forekomster af tal < ar[i]
--countArray[ar[i]-min];
}
return res;
}

static void print( int[] ar )
{
for( int i = 0; i < ar.length; ++i )
{
System.out.print(ar[i]+",");
}
System.out.println();
}

static int randomInt( int min, int max )
{
int res = ((int)(Math.random()*(max-min)))+min;
return res;
}

static int[] randomArray( int length, int min, int max )
{
int[] res = new int[length];
for( int i = res.length; --i >= 0; )
{
res[i] = randomInt( min, max );
}
return res;
}

static void checkSort( int[] ar )
{
for( int i = 1; i < ar.length; i++ )
{
if( ar[i-1] > ar[i] )
{
print(ar);
throw new RuntimeException("NOT SORTED");
}
}
}

public static void main(String args[])
{
for( int i = 0; i < 1000; i++ )
{
int min = randomInt( 1, 1000 );
int max = randomInt( min, 1000 );
int[] in = randomArray( 10, min, max );
System.out.print("in:");
print(in);
int[] out = countingSort( in, min, max );
checkSort( out );
System.out.print("out:");
print(out);
}
}
}

Ulrik Magnusson

---

<klip>

Jeg vil kigge på den senere :)

> static int randomInt( int min, int max )
> {
> int res = ((int)(Math.random()*(max-min)))+min;
> return res;
> }
>

p.s. Math.random() laver ikke altid jævnt fordelte tilfældige
tal.

Brug hellere Random.

--
With many Thanks

Soren ' Disky ' Reinke ICQ #1413069
http://www.disky-design.dk/fish
Remove IHSYD from email address when replying by email

---

Soren 'Disky' Reinke wrote:

> p.s. Math.random() laver ikke altid jævnt fordelte tilfældige
> tal.
>
> Brug hellere Random.

"næsten" jævnt er vist godt nok til lidt test. Et større problem
er nok at min randomInt( int min, int max ) metode aldrig kan
returnere max, som der ellers lægges op til.

Ulrik Magnusson

---

"Soren 'Disky' Reinke" <disky@disky-design.ihsyd.dk> writes:

> En bucket sort kan gøre det uden sammenligning.

Til gengæld er du nødt til at vide lidt mere om dit input end bare at
det kan sammenlignes.

Du er nødt til at være sikker på at det ligger i et bestemt
interval.

I øvrigt kan den med held kombineres med fx hægtede lister, så man i
hver "spand" har en hægtet liste, som man så indsætter elementer i, og
hver spand så til gengæld dækker over et interval i stedet for et
enkelt element.

Det er en fordel, hvis man fx skal sortere 1000 tal, som er jævnt
fordelt over et stort interval. Så gør det mindre at man bruger
insertionsort til at indsætte i en hægtet liste, hvis der ikke kommer
ret mange elementer i listen. Til gengæld kan man så spare en masse
hukommelse i forhold til at have en "spand" for hvert element i
intervallet elementerne kan forekomme i.

--
Jacob - www.bunk.cc
If you wish to succeed, consult three old people.

---

"Ronni (The real one:)" wrote:

> Hejsa NG
>
> Jeg har i skolen fået stillet en opgave som lyder :
> Bevis at en enhver sammenlignings-baseret sorterings algoritme, der skal
> sortere 4 elementer, skal bruge minimum 5 sammenligninger for et eller
> andet input, og lav denne.
>
> Jeg har løst den ved banale if-sætninger og kan få det til at gå op, men er
> ikke helt tilfreds, og tror heller ikke det accepteres at man blot løser
> den med if-sætninger hele vejen igennem, og vil derfor gerne lave noget
> mere komplekst, hvor jeg så er gået i stå.

Nedenstående skulle da helst ikke være mere komplekst ( ), men
løser også problemet. Man fletter 2 sorterede arrays á 2 elementer -
fletningen kræver max 3 sammenligninger og sorteringen 2:

public class s
{

static void print( int[] ar )
{
for( int i = 0; i < ar.length; ++i )
{
System.out.print(ar[i]+",");
}
System.out.println();
}

static void swap( int[] ar, int i1, int i2 )
{
int tmp = ar[i1];
ar[i1] = ar[i2];
ar[i2] = tmp;
}

static int[] sort( int[] ar )
{
int comp = 1;//antal sammenligninger
if( ar[0] > ar[1] )
{
swap( ar, 0, 1 );
}
comp++;
if( ar[2] > ar[3] )
{
swap( ar, 2, 3 );
}
// nu er de to halvdele sorteret og de flettes ind i res
int[] res = new int[4];
int inc1 = 0;//indeks i venstre halvdel
int inc2 = 2;//indeks i højre halvdel
for( int i = 0; i < 4; i++ )
{
if( inc1 > 1 )
{
//der er ikke flere elementer i venstre halvdel - indsæt fra højre halvdel
res[i] = ar[inc2++];
}
else if( inc2 > 3 )
{
//der er ikke flere elementer i højre halvdel - indsæt fra venstre halvdel
res[i] = ar[inc1++];
}
else if( ar[inc1] < ar[inc2] )
{
comp++;
res[i] = ar[inc1++];
}
else
{
comp++;
res[i] = ar[inc2++];
}
}
System.out.print("comp:" + comp + "\tres: ");
print( res );
return res;
}

public static void main(String args[])
{
/*
så skal der bare laves en algoritme til at
generere permutationer
*/
sort( new int[]{1,2,3,4} );
sort( new int[]{1,2,4,3} );
sort( new int[]{1,3,2,4} );
sort( new int[]{1,3,4,2} );
sort( new int[]{1,4,3,2} );
sort( new int[]{1,4,2,3} );

sort( new int[]{2,1,3,4} );
sort( new int[]{2,1,4,3} );
sort( new int[]{2,3,1,4} );
sort( new int[]{2,3,4,1} );
sort( new int[]{2,4,3,1} );
sort( new int[]{2,4,2,1} );

sort( new int[]{3,2,1,4} );
sort( new int[]{3,2,4,1} );
sort( new int[]{3,1,2,4} );
sort( new int[]{3,1,4,2} );
sort( new int[]{3,4,1,2} );
sort( new int[]{3,4,2,1} );

sort( new int[]{4,2,1,3} );
sort( new int[]{4,2,3,1} );
sort( new int[]{4,1,2,3} );
sort( new int[]{4,1,3,2} );
sort( new int[]{4,3,1,2} );
sort( new int[]{4,3,2,1} );
}
}

---

Mange tak!

Så kunne det lade sig gøre alligevel :)

Det sad jeg kun og biksede med i 4 - 5 timer i går uden at finde en
egentlig løsning.

/Ronni
ronni1@ofir.dk