Avatar billede snebaer Novice
02. januar 2002 - 12:56 Der er 9 kommentarer og
1 løsning

Insertionsort

Jeg sidder med en opgave, hvori jeg har fået den vejledende løsning:

public void sortKundeList(KundeList kl){
//PRE: none
//POST: KundeListen kl er sorteret i voksende rækkefølge efter kundenummer (Der anvendes en simpel insertionsort)

if(kl.count()==0) return; //tom liste
for(int p=1; p<kl.count();p++){
  for(int j=p; j>0&&kl.inspect(p).getKundenr()<
    kl.inspect(j).getKundenr(); j--)
  kl.swap(j,j-1);
}
}

Jeg kan godt se teorien i, at man skal undersøge hvert enkelt tal (Kundenr) og se om det er mindre end det forrige.
Men hvordan helt nøjagtigt virker de to for-løkker. Hvordan gennemløber de en Kundelist med f.eks Kundenumre som 22,15,29,26,11,8.
Det er de to for-løkkers indbyrdes løb gennem talrækken, som jeg er i tvivl om.

VH snebaer
Avatar billede erikjacobsen Ekspert
02. januar 2002 - 13:01 #1
Du har i gennemløbet hele tiden en foreløbig sorteret liste til venstre,
og resten, usorteret, til højre. Undervejs vil dine tal se sådan ud:

    15 22 29      26 11 8

Så tager du fat i 26, og bytter med den foregående indtil den står rigtigt.
I dette tilfælde tager det kun én bytning

    15 22 26 29    11 8

Det tager længere tid med 11

    15 22 26 11 29      8
    15 22 11 26 29      8
    15 11 22 26 29      8
    11 15 22 26 29      8

Der var den.
Avatar billede greybeard Nybegynder
02. januar 2002 - 13:46 #2
Så vidt jeg kan se sorterer den løsning ingenting.
I den inderste løkke sættes j = p, hvorefter den ene betingelse kræver at kundenummeret på plads p er mindre end kundenummeret på plads j.
Da p = j er de to kundenumre ens, og betingelsen kan aldrig være true.
Avatar billede erikjacobsen Ekspert
02. januar 2002 - 14:03 #3
Nå ja, skal man nu også læse den kode der bliver vist. Den skal nok rettes til

for(int j=p; j>0&&kl.inspect(j).getKundenr()<kl.inspect(j-1).getKundenr(); j--)
Avatar billede greybeard Nybegynder
02. januar 2002 - 14:10 #4
Det vil få det til at virke, men det er en bubblesort og ikke en insertionsort, som kommentaren siger.
Avatar billede erikjacobsen Ekspert
02. januar 2002 - 14:16 #5
Nej, det ér en insertionsort.
Avatar billede greybeard Nybegynder
02. januar 2002 - 14:28 #6
I en insertionsort sættes hvert enkelt element ind på sin rette plads ved at flytte alle de efterfølgende for at give plads.
Her flyttes elementet én ad gangen indtil det er på sin plads, og det er en bubblesort
Avatar billede erikjacobsen Ekspert
02. januar 2002 - 14:37 #7
Nej, det er rigtigt at denne implementation af inserttionsort er ineffektiv, ved
at den indsætter det aktuelle element på alle de mellemliggende pladser,
i stedet for at vente til sidst.

En boblesortering er karakteriseret ved at man bytter konsekutive elementer
et passende antal gange, uden at kigge på deres indhold. En boblesortering
vil efter første gennemløb anbringe det største tal til sidst (og have en globalt
sorteret delliste til sidst), og en boblesortering kan stoppe tidligere, hvis der viser
sig ikke at være flere ombytninger. Ingen af disse ting er tilfældet for denne sortering.
Avatar billede snebaer Novice
02. januar 2002 - 16:19 #8
Hej erikjacobsen og greybeard

Tak for hjælpen. Da jeg i for-løkken fik udskiftet inspect(p) med hhv inspect(j) og inspect(j-1) så lykkedes det hele.

Men hvem skal have point?
VH snebaer
Avatar billede nielsbrinch Nybegynder
19. januar 2002 - 18:49 #9
Prøv med Arrays.sort næste gang du får en opgave, med mindre selvfølgelig der kræves at du skal bruge InsertionSort.

En fordel ved InsertionSort er i øvrigt at den er hurtig til at finde ud af hvis det hele allerede er sorteret.
Avatar billede snebaer Novice
15. august 2003 - 15:07 #10
Da ingen af "svarerne" har svaret tager jeg selv pointene, så jeg ikke har nogen ude i mit pointregnskab.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester