Sorteer algoritme

[xandie]

hoi,
Ik ben net begonnen met het leren van wat algoritmes adv Introduction to Algorithms.
Nu zit ik al vast bij het eerste algoritme, Insertion-sort

code:

  Dim Inti, intKey, intteller As Integer
        For intteller = 0 To arrIntGetalen.Length - 1
            intKey = arrIntGetalen(intteller)
            Inti = intteller - 1

  -------> While Inti > 0 And arrIntGetalen(Inti) > intKey
                arrIntGetalen(Inti + 1) = arrIntGetalen(Inti)
                Inti -= 1
                arrIntGetalen(Inti + 1) = intKey
            End While
        Next
        MsgBox("done")

de fout zit bij de pijl; daar zegt visual studio: "Index was outside the bounds of the array."

alvast bedankt voor jullie hulp

[michiel_hc]

De eerste keer dat de code word doorlopen is Inti -1. Ik gok dat ondanks dat de eerste voorwaarde van de while false is toch de tweede voorwaarde word uitgevoerd. Probeer eens intteller op 1 te laten beginnen?

[xandie]

Visual Basic .NET:

Dim Inti, intKey, intteller As Integer
        For intteller = 1 To arrIntGetalen.Length - 1
            intKey = arrIntGetalen(intteller)
            Inti = intteller - 1

           While Inti > 0 And arrIntGetalen(Inti) > intKey
                arrIntGetalen(Inti + 1) = arrIntGetalen(Inti)
                Inti -= 1
                arrIntGetalen(Inti + 1) = intKey
            End While
        Next
        MsgBox("done")

nu sorteert hij het eerste getal niet.

[Fish]

eerste run inteller=0
inti word -1

While Inti > 0 And arrIntGetalen(-1) > intKey

arrIntGetalen(-1) => out of bounds


gewoon een laag dieper nesten

[ Voor 11% gewijzigd door Fish op 25-09-2013 19:01 ]

[Verwijderd]

De eerste while lus word overgeslagen omdat IntI dan 0 is.

[naitsoezn]

Iets met (het ontbreken van) Lazy Evaluation... Probeer de 2e conditie eens binnen de eerste conditie. Niet heel nette code, maar het werkt wel. Mogelijk levert een Google op Lazy Evaluation Visual Basic .NET andere oplossingen...

[ Voor 18% gewijzigd door naitsoezn op 25-09-2013 19:04 ]

[Fish]

Verwijderd schreef op woensdag 25 september 2013 @ 19:01:
De eerste while lus word overgeslagen omdat IntI dan 0 is.

Er word niets overgeslagen

Om de while te evaluren moet hij arrIntGetalen(-1) opzoeken. en die bestaat niet

[Verwijderd]

fish schreef op woensdag 25 september 2013 @ 19:03:
[...]


Er word niets overgeslagen

Om de while te evaluren moet hij arrIntGetalen(-1) opzoeken. en die bestaat niet

xandie heeft de code aangepast (begint nu bij 1) en zegt dat het eerste getal niet gesorteerd wordt.

Edit: hm weet even niet of VB nu ook zero-index arrays heeft, neem aan van wel toch. Dan mis je dus index 0.

[ Voor 14% gewijzigd door Verwijderd op 25-09-2013 19:07 ]

[Fish]

Ja als je 1 hoger begint dan sla je hem zelf over en dan sorteert die natuurlijk niet

het makkelijkt is om de 2e vergelijking niet in de while te stopppen maar een niveau dieper

[xandie]

Visual Basic .NET:

 Dim Inti, intKey, intteller As Integer
        For intteller = 0 To arrIntGetalen.Length - 1
            intKey = arrIntGetalen(intteller)
            Inti = intteller - 1

            While Inti > 0 AndAlso arrIntGetalen(Inti) > intKey
                arrIntGetalen(Inti + 1) = arrIntGetalen(Inti)
                Inti -= 1
                arrIntGetalen(Inti + 1) = intKey
            End While
        Next
        MsgBox("done")

nu begint intteller terug op 0 en is het probleem met "lazy evalution" opgelost.
maar hij sorteert nog altijd het eerste getal niet.

[pedorus]

Dat komt omdat er een klassieke off-by-one error in de code hierboven zit... (En eigenlijk was beginnen bij 1 prima; waarom begin je nu weer bij 0?)

[xandie]

Visual Basic .NET:

Dim Inti, intKey, intteller As Integer 
        For intteller = 1 To arrIntGetalen.Length - 1 
            intKey = arrIntGetalen(intteller) 
            Inti = intteller - 1 

            While Inti >= 0 AndAlso arrIntGetalen(Inti) > intKey 
                arrIntGetalen(Inti + 1) = arrIntGetalen(Inti) 
                Inti -= 1 
                arrIntGetalen(Inti + 1) = intKey 
            End While 
        Next 
        MsgBox("done")

Gevonden,
Bedankt
je kan inderdaad bij 1 beginnen aangezien inti groter moet zijn dan 0
Ik begin steeds meer en meer de schoonheid van programeren in te zien

[ Voor 6% gewijzigd door xandie op 25-09-2013 19:42 ]

[RobIII]

naitsoezn schreef op woensdag 25 september 2013 @ 19:02:
Iets met (het ontbreken van) Lazy Evaluation... Probeer de 2e conditie eens binnen de eerste conditie. Niet heel nette code, maar het werkt wel. Mogelijk levert een Google op Lazy Evaluation Visual Basic .NET andere oplossingen...

Je bedoelt Short-circuit evaluation
Zie ook: Short-Circuiting Logical Operations

[ Voor 11% gewijzigd door RobIII op 25-09-2013 20:26 ]