spezielle Sortierung

[juggernart]

Hallo, ich hab folgende Problemstellung:

1. Ich habe ein Array mit einer durchgehenden Zahlenfolge.
Also z.B. [1,2,3,4,5,6,7,8,9,10]

2. Das Array wird dann per Zufall gemischt.
z.B. [1,9,7,6,3,8,5,4,2,10]
Beim Mischen kann es sein, dass Zahlen an der Ausgangsposition stehen bleiben (hier 1 und 10).

3. Das Array soll nun durch Austauschen von jeweils zwei Zahlen sortiert werden. Dabei kann es vorkommen, dass beim Austauschen zwei Zahlen auf ihre Ausgangsposition gleichzeitig kommen. Hier 9 und 2

Durch geschicktes Austauschen sollen möglichst wenig Züge erreicht werden. Wie ermittel ich die kleinstmögliche Anzahl von Zügen (Austausch-Vorgängen)?

Für Lösungsansätze wäre ich dankbar.

[dburucu]

ehm ist das ne Hausaufgabe?

also die Technik heißt ja bubble-sort, wenn ich mich nicht irre:

hier findest Du die Sortierung:

//numerical sorting
tester=[54,6,1,346,32,55,3,66,28]
trace("original array :"+tester);
tester1=new Array();
array.prototype.bubble=function(){
        arr_t=new Array();
        count=this.length;
        trace("arrray's length:"+count);
        temp=0;
        for(i=count-1;i>0;i--){
                for(j=0;j<i;j++){
                        if(this[j]>this[j+1]){
                                temp=this[j];
                                this[j]=this[j+1];
                                this[j+1]=temp;
                        }
                }
        }
        return this;
}
 
tester1=tester.bubble();
 
trace("bubbleed array:"+tester); 

nachzulesen unter:
http://www.actionscript.org/actionsc...ct/more4.shtml

Wieviel schritte Du brauchst, könntest Du ja mit einem Zähler erreichen.

[juggernart]

Danke.

Wollte das nur möglichst verständlich beschreiben.
( Aus dem Hausaufgabenalter bin ich längst raus )

Ich werd mir das mal bei Zeiten zu Gemüte führen.

[juggernart]

Naja.
Ich dachte mir schon, das Bubblesort nicht das ist, was ich brauche.
Da muss schon ne intelligentere sortierroutine her
(Bubblesort sortiert ja nur "stur" von vorn nach hinten)
Beispiel:
shuffled array :4,3,2,1
Bubblesort-Züge:
3,4,2,1
3,2,4,1
3,2,1,4
2,3,1,4
2,1,3,4
1,2,3,4

sind also sechs Züge, zwei wären aber ausreichend:
1,3,2,4
1,2,3,4