Een sorting algorithm dat niet hoort te werken.

[Brainhero]

Ik ben nu aan het leren te programmeren en dit is mijn derde programma in kotlin. Ik heb een sorting algorithm dat eigenlijk hoort te sorteren door twee getallen naast elkaar te vergelijken en zo doorgaat totdat het gesorteerd is. Dit is de code.

code:

import java.util.*

fun main() {
    val shuffled = (1..10).shuffled().toMutableList()
    println(shuffled)
    for (d in 1..9)
        for (i in 0..8) {
            if (shuffled[i] > shuffled[d]) {
                Collections.swap(shuffled, i, d)
                println(shuffled)
            }
        }
}

En als uitkomst krijg ik dit bijv.

code:

[3, 2, 1, 10, 5, 6, 8, 9, 7, 4]
[2, 3, 1, 10, 5, 6, 8, 9, 7, 4]
[2, 10, 1, 3, 5, 6, 8, 9, 7, 4]
[1, 10, 2, 3, 5, 6, 8, 9, 7, 4]
[1, 2, 10, 3, 5, 6, 8, 9, 7, 4]
[1, 2, 3, 10, 5, 6, 8, 9, 7, 4]
[1, 2, 3, 5, 10, 6, 8, 9, 7, 4]
[1, 2, 3, 5, 6, 10, 8, 9, 7, 4]
[1, 2, 3, 5, 6, 8, 10, 9, 7, 4]
[1, 2, 3, 5, 6, 8, 9, 10, 7, 4]
[1, 2, 3, 5, 6, 7, 9, 10, 8, 4]
[1, 2, 3, 5, 6, 7, 8, 10, 9, 4]
[1, 2, 3, 5, 6, 7, 8, 9, 10, 4]
[1, 2, 3, 4, 6, 7, 8, 9, 10, 5]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 6]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
[1, 2, 3, 4, 5, 6, 7, 9, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

En soms onsorteerd hij zichzelf en sorteerd zich daarna weer.
Kan iemand mij uitleggen waarom dit gebeurt en waarom het werkt?

[Daos]

Je vergelijking en swap kloppen niet. Het volgende item is niet d, maar i + 1.

De loop met d is er alleen om 9 iteraties van de binnenste loop te doen. Een lijst met 10 items is na maximaal 9 iteraties gesorteerd. Die d zelf heb je nergens voor nodig.

[eric.1]

Schrijf letterlijk en stap voor stap uit wat je code doet (dan is het wel makkelijker om een kleinere dataset te gebruiken, maar goed, dat ter zijde).

Dan kom je er snel genoeg achter waarom de twee loops en logica daarbinnen dit resultaat leveren.

[Brainhero]

Daos schreef op zondag 14 augustus 2022 @ 13:57:
Je vergelijking en swap kloppen niet. Het volgende item is niet d, maar i + 1.

De loop met d is er alleen om 9 iteraties van de binnenste loop te doen. Een lijst met 10 items is na maximaal 9 iteraties gesorteerd. Die d zelf heb je nergens voor nodig.

Ik weet dat mijn code geen goede bubblesort implementatie is. De vraag is waarom het dan toch werkt.

[Daos]

Ik heb je algoritme even doorgerekend en hij klopt inderdaad.

Het is nu een soort insertion-sort waarbij je in het begin wat swaps teveel doet. Blijkbaar maakt dat niet uit voor de werking.

Als je de binnenste loop naar d - 1 laat lopen ipv 8, dan krijg je een echte insertion-sort. d is dan de kolom die je met je binnenste loop naar links verplaatst zodat de waardes tot en met die kolom gesorteerd zijn.

Neem jouw voorbeeld waarbij ik na elke binnenste loop print:

code:

[3, 2, 1, 10, 5, 6, 8, 9, 7, 4] // start
[2, 3, 1, 10, 5, 6, 8, 9, 7, 4] // na d = 1 zijn 2 waardes gesorteerd
[1, 2, 3, 10, 5, 6, 8, 9, 7, 4] // na d = 2 zijn 3 waardes gesorteerd
[1, 2, 3, 10, 5, 6, 8, 9, 7, 4] // ...
[1, 2, 3, 5, 10, 6, 8, 9, 7, 4]
[1, 2, 3, 5, 6, 10, 8, 9, 7, 4]
[1, 2, 3, 5, 6, 8, 10, 9, 7, 4]
[1, 2, 3, 5, 6, 8, 9, 10, 7, 4]
[1, 2, 3, 5, 6, 7, 8, 9, 10, 4]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] // na d = 9 zijn 10 waardes gesorteerd

[jeanj]

Als je bij je output, nou een ook de i en de d opneemt, dan zie je welke waarden worden zijn omgedraait. Voor debuging is het ook handig om output te generen als je conditie niet waar is, wederommet de i en de d

Misschien kan je ook eens de i en de d omdraaien in de conditie, wat gebeurt er dan?