Schleifendurchläufe selection-Sort

TrappedUnderIce

Hallo,

also zunächst hier der C-Code von selection-Sort aus unserer Vorlesung:

void selectionSort(RecTyp liste[], int S[])
{
	int i, j, m;
	for(i=n; i>1; i--)
	{
		m=1;
		for(j=2; j<=i; j++)
		{

		  if(liste[S[j]].Suchattribut > liste[S[m]].Suchattribut)
		       m=j;
		}

		j=S[i];         
		S[i]=S[m];
		S[m]=j;
	}
}

Die Zeilen 14-16 werden doch immer nur nach Durchlaufen der inneren j-Schleife ausgeführt oder?

Nun zur eigentlichen Frage: Es ist eine Zahlenfolge

5 1 8 3 9 2

gegeben. Gesucht ist nun die Zahlenfolge nach dem 3. Durchlauf der i-Schleife. Dabei komme ich immer auf

3 1 2 5 8 9

. Dies ist aber bei meinen vorgegeben Antwortmöglichkeiten gar nicht dabei.

Die einzige Antwortmöglichkeit was überhaupt in Frage käme, wäre

1 2 3 5 8 9

da nur hier die "9" am Ende steht, was ja beim 1. Durchlauf der i-Schleife schon passiert.

Ich habe mir die einzelnen Schritte in einer Tabelle aufgeschrieben, allerdings sehe ich gerade keine Option hier ein .pdf hochladen zu können. Könnt ihr mein Ergebnis bestätigen oder ist es tatsächlich falsch?

Th69

Hallo,

dein C-Code scheint aus Pseudocode (oder aber z.B. Pascal) entstanden zu sein, denn die Indizes sind falsch (in C ähnlichen Sprachen beginnt ein Array-Index immer mit Null (0))!
Vgl. deinen Code auch mal mit Sortierverfahren: Selectionsort (C)

TrappedUnderIce

Hi,

du hast natürlich recht. Man sollte oben genannten Code als Pseudo-Code verstehen, und die Indizierung der Zahlenfolge starte bei 1. Mir kommt es also mehr auf den Algorithmus an sich an.

MFK

Wie lauten die anderen Antwortmöglichkeiten?

TrappedUnderIce

Hier alle Möglichkeiten, die ich ankreuzen kann:

a)1 5 8 3 9 2

b)1 3 5 8 9 2

c)1 2 3 8 9 5

d)1 2 3 5 8 9

e)1 2 3 5 9 8

EDIT:
hier noch ergänzend der C-Code mit dem ich es gerade ausprobiert habe:

void selectionSortA(const int data[], int n, int S[])
{
    //data[]={5, 1, 8, 3, 9, 2}
    //S[]={1, 2, 3, 4, 5, 6}

    int i, j, m;
    for(i = n-1; i >=n-3; i--) //n=6
    {
        m = 0;
        for(j = 1; j <= i; j++)
            if(data[S[j]-1]>data[S[m]-1])
                m = j;

        j = S[i]; S[i] = S[m]; S[m] = j;

    }
}

Damit erhalte ich ebenfalls

3 1 2 5 8 9

nach dem 3. Durchlauf der i-Schleife.

MFK

Die Lösungsmöglichkeiten passen einfach nicht zum Code. Die Lösungen sehen danach aus, dass da eine Funktion von vorn den kleinsten Wert sucht, nicht von hinten den größten.

TrappedUnderIce

Ok, komisch, wir haben nämlich nie eine andere Variante von selection-Sort besprochen, und auch in der Aufgabenstellung steht nichts was darauf hindeuten würde.