🚀 go-pugleaf

Daniel van Gerpen schrieb in de.comp.sys.amiga.tech ueber "Q: Sortieralgo":

> Hallo allezusammen,
> kann mir jemand erklaeren, wie der Algorhythmus "Straight Selection" ein
> Array sortiert? Ja, ich weiss, jede gut- sortierte (!) Uni-Bibo sollte
> das koennen, ich hab aber grad keine in Reichweite... 8(
> Frohe Ostern, Daniel

Hmm... ich habe hier das Buch "Algorithmen" von R. Sedgewick (ISBN
3-89319-301-4, DM 79.-). Da ist ein Algorithmus beschrieben, der
"Selection Sort (Sortieren durch (direktes) Auswählen)" heißt:

Die Idee ist folgende: Ich laufe durch das Feld und suche das kleinste
Element. Dieses wird dann mit dem Element am Feld-Anfang ausgetauscht:

    Start:  xya
    1.	    ayx
    2.	    #xy
    3.	    -fertig-

Im 1. Schritt habe ich das "a" nach vorne geholt. Im 2. Schritt kann
ich das "a" ignorieren (durch "#" angedeutet) und ich suche wieder
das kleinste Element, das ist jetzt das "x", das an den neuen Anfang
geholt wird. Das wars.

Der Algorithmus braucht die gleiche Anzahl an Vergleichen wie Bubblesort
(N*N/2) und N swaps (Bubblesort braucht N*N/2 swaps).

--
Aaron "Optimizer" Digulla                        AROS Head of Development
Author of XDME, ResTrackLib, CInt.		   (since no one else wanted)
"(to) optimize: Make a program faster by improving the algorithms rather than
by buying a faster machine."