Introduktion til Sorting Network Applet

Allan Grønlund Jørgensen, 2006

Introduktion til Problemstilling

I denne applet arbejder man med Sorterings-Netværk. Det vil sige det handler om sortering af tal via et netværk. Et netværk er en række vandrette inputlinjer, en for hvert input element, og et antal lodrette sammenligningskanter(Linje der forbinder to inputlinjer). Hvert inputelement har sin egen linje. To inputelementer kan skifte linje via en lodret sammenligningskant.

Ved en sammenlingningskant flytter det mindste element op til den øverste inputlinje mens den største flytter til den nederste inputlinje. Det vil sige der kun sker noget hvis værdien på den nederste inputlinje er mindre end værdien på den øverste inputlinje.

Inputelementer starter i venstre, og det handler om at få inputelementerne til at stå sorteret til højre. Altså efter den sidste lodrette sammenligningskant. Lille eksempel med 3 elementer der der kører igennem et Sorterings-Netværk(7,4,5).

\begin{figure}\par \begin{verbatim}7 --4--4--4 \vert \vert \vert \vert 4 ... ...vert \vert \vert \vert 5 --5--7--7\end{verbatim}\centering \par \end{figure}

Efter hver sammenlingningskant kan man på linjen se den værdi der kører videre mod højre derfra.. Der er 3 sammenligningskanter.

Et Sorterings-Netværk med inputstørrelse $ n$ er korrekt, hvis det korrekt sorterer alle permutationer af $ \{1,\ldots,n\}$ . Det vil sige ligegyldig hvilken permutation af input der kommer, skal elementerne stå sorteret i højre efter sidste sammenligningskant. Det vil sige oppefra og ned skal der stå $ \{1,2,\ldots,n\}$ .

Forklaring af Brugergrænseflade

Image Init

På dette 2 kan man se hvordan appleten starter med at se ud ved inputstørrelse 4. Til venstre kan man se en permutation af input som Sorterings-Netværket (inden sidste opdatering) ikke sorterer korrekt.

De vandrette gule linjer er inputlinjerne.

I bunden er der knapper og et beskedfelt. Knappernes funktionalitet vil blive forklaret på følgende sider.

Indsæt Sammenligningskant

Man kan tilføje en sammenligningskant på følgende vis. Start med at holde cursor over den ene af de inputlinjer man ønsker at forbinde. Denne vil blive farvet rød for at tydeliggøre at denne linje kan vælges. Drag(hold museknap nede og ryk) cursor til den linje der ønskes at forbinde den første linje med. Denne vil også blive farvet når man kommer tæt på. En blå linje vil følge efter cursoren vertikalt for at illustrere hvilken kant der er ved at blive indsat. Når museknappen slippes vil kanten blive indsat hvis den var tæt nok på en anden linje(Den var rød).

Image Insert

Slet Sammenligningskant

For at slette en sammenligningskant flyttes cursor hen over den sammenligningskant der ønskes slettet. Det vil få den til at skifte farve til rød for at markere at man faktisk har flyttet musen henover.

Herefter venstreklikker man og så skifter farven af kanten til hvid for at markere at kanten er valgt til at kunne slettes. For at slette trykkes på knappen delete som vil være mulig at trykke på efter en kant er valgt.

Image delete

Korrekt Sorterings-Netværk

I højre hjørne af appleten kan man se hvor mange sammenligningskanter der er indsat. Her kan man også se dybden netværket. Dybden forklares i et senere afsnit.

For at finde ud hvorvidt man har lavet et korrekt Sorterings-Netværk trykkes på knappen Verify Network.

I textområdet i bunden vil der stå hvorvidt det nu er et korrekt Sorterings-Netværk. Hvis ikke dette er tilfældet, vil der til venstre blive skrevet en permutation der ikke bliver sorteret korrekt. Til højre kan ses resultatet af Sorterings-Netværket på dette input. Og i selve netværket kan man følge værdierne mens de vandrer fra venstre mod højre. Se 2.3

Image Verify


Upload

For at man indbyrdes kan sammenligne hvor god en løsning man har fundet til problemet er der mulighed for at uploade resultatet til en high-score liste. Denne high-score liste indeholder kun korrekte Sorterings-Netværk. Og det handler om at bruge så få sammenligningskanter som muligt. Denne highscore eksisterer for 4 inputstørrelser, 4,8,10 og 12. Hvis to korrekte Sorterings-Netværk har samme antal sammenligningskanter bruges dybden til at differenciere.

Dybde af Sorterings-Netværk

Dybden af en netværk relaterer sig til parallele beregninger. Hvis man f.eks. har en sammenlingnigskant mellem linje 1 og 2, og en mellem linje 3 og 4, kunne man udføre begge operationer(flyt min op og max ned) samtidig uden problemer.

Det vil ikke gælde hvis linjerne var mellem 1 og 2, og 2 og 3. Så skal den ene sammenligningskant bruges før den anden. Så dybden af netværket kan ses som den tid det vil tage at sortere med netværket hvis sådanne parallelle operationer var lovlige. Hvis parallel udførsel af sammenligningskanter ikke er lovlig vil tiden blive det lig med antallet sammenligningskanter.

Det er denne dybdeværdi man kan finde sammen med antal sorteringskanter i højre hjørne.

For at overskueliggøre hvordan man kan gruppere sammenligningskanterne kan man trykke på knappen Enable Depth Lines. Den vil inddele sammenligningskanterne i grupper fra venstre mod højre der kan udføres samtidig. Dette er gjort med lodrette grønne linjer. Se 2.5.

Image Depth

Applet

Bare følg link for at starte applet.

Links til High-Score