(Algoritmer)Sortera en array med bollar, i max O(n) tidsåtgång

Tja. Hur sortera ett antal bollar, vita o svarta, så att alla vita bollar kommer till vänster?
Algoritmen ska vara inplace, dvs man får inte använda en extra array.
Den ska vara O(n).

Något snille som vet?

Initialisera två räknare v och s till noll. v räknar antalet vita bollar flyttade, s antalet svarta.

Låt i gå igenom positionerna i array:n från vänster till höger.

För varje i: Kolla om i:te bollen är svart eller vit. Om vit, byt plats på den bollen och den (v+1):te bollen från vänster och öka v med ett. Om den är svart, byt plats på den bollen och den (s+1):te bollen från höger och öka s med ett.

På så sätt skjuts alla vita bollar till vänster och alla svarta till höger.

tack kompis

Låt en pekare v:vänster peka på första elementet och en pekare h:höger peka på sista elementet.

Låt v flytta ett steg till höger tills dess att den stöter på en svart boll. Låt h flytta ett steg till vänster tills dess att den stöter på en vit boll. Invertera då de båda elementen; dvs vit blir svart, och tvärt om.

Kontrollera om båda pekarna, v och h pekar på samma element vid varje flytt av v eller h; om så är fallet så är sorteringen färdig.

Om det är tre olika färger då? Svart, vit röd, och de ska ligga i den ordningen? Fortfarande är O(n) max antal operationer

En metod (men den är two-pass) är ju att först gå igenom hela array:n en gång och räkna antalet svarta, vita och röda kulor, och sen gå igenom array:n igen och swappa in allting på rätt plats direkt.

Jag tänkte annars på att modda den förra metoden du sa.
Typ att ha 3 räknare istället. Att man tänker att om svart ska vara till vänster, vit i mitten och röd till höger, så gör man precis som tidigare med de som ska till vänster o höger, och den som ska vara i mitten kan man plussa på även när den som ska vara till vänster plussas på. Alltså, viträknaren i detta fall plussas på både när svart och vit hittas, och sen är det som förut. Vad tror du om det?

Tack för att du tar dig tid för övrigt

Fast nja, jag tror att i så fall så kommer man inte kunna garantera att de vita och svarta ligger i ordning, va? För man vet ju så att säga inte var man ska "börja" lägga de vita.

Det här borde fungera.

Den är ju dock O(n²) i värsta fall. (T.ex. om alla bollar är röda.)

Om alla bollar var röda skulle den gå igenom den inre loopen A.length gånger och sedan avsluta helt. Så jag ser inte hur det skulle bli O(n²).

Klart enklast och snyggast lösning och funkar med flera färger. Att den kör flera pass ändrar ju inte O(n).