Insertion-Sort

Maex2808

Hey Leute,

brauche mal wieder eure Hilfe, diesmal bei der Implementierung von Inserion-Sort.

Aufgabe ist es, verschiedene Sortier-Algorithmen zu implementieren und via O-Notation zu vergleichen.

Jedenfalls will mein Insertion-Sort nicht so ganz.

void insertionsort(int numbers[], int start, int end)
{
	int i, k, current;

	for (i=start+1; i<=end; i++)
	{
		printf("Test\n");
		current=numbers[i];
		for (k=i-1; k>=start; k--);
		{
			if (numbers[k]>current)
			{
				numbers[k+1]=numbers[k];				
			}
			else
			{
				break;
			}
		}
		numbers[k+1]=current;		
	}
}

start hat den Wert 0, end 8.
Das Problem scheint am break zu liegen.
Ist break auskommentiert, wird "Test" 8 mal ausgegeben, ansonsten nur 1 mal.
break scheint sich also auf die erste for-Schleife zu beziehen, was für mich unbegreiflich ist.

NDEBUG

Der Fehler ist das hier:

for (k=i-1; k>=start; k--);
//                        ^

Hier die richtige Version:

//....
    int numbers[10] = {94, 89, 41, 23, 18, 73, 51, 31, 85, 113};
    int i, j, k, current;
    int start = 0, end = 8;

    for(i = start + 1; i < end; i++)
    {
        printf("Durchlauf #%d: ", i);    // infos 
        for(j = start; j < end; j++)     // infos
            printf("%d ", numbers[j]);   // infos
        printf("-> ");                   // infos

        for(k = i - 1, current = numbers[i]; k >= start && numbers[k] > current; k--)
            numbers[k+1] = numbers[k];
        numbers[k+1] = current;

        for(j = start; j < end; j++)          // infos
            printf("%d ", numbers[j]);        // infos
        printf("\n");                         // infos
    }
// ....

Maex2808

Ähm, ehrlich gesagt sehe ich in der Version keinerlei Unterschied zu meiner.

Kann mir jmd. auf die Sprünge helfen?

NDEBUG

(a) Dann lies meinen Post nocheinmal Wort für Wort von oben bis unten.

EDIT: Es gibt einen Unterschied in unseren Versionen. Gehe zu (a).

Maex2808

Ah, jetz seh ichs auch. Oh man. Danke dir.

NDEBUG

Ich hab mich etwas unglücklich ausgedrückt. Es gibt genau 2 Unterschiede in unseren Versionen. Einen offentsichtlichen und einen eher subtilen, aber wichtigen. Wenn du also ingesamt 2 Unterschiede gefunden hast, bist du am Ende. Ansonsten vergleich noch mal gaaanz genau und gehe zu (a).

Maex2808

Das überflüssige Semikolon und das <=. Danke dir.

NDEBUG

Maex2808

Allerdings ist

for (i=start+1; i<=end; i++)

korrekt. ^^

EDIT: Verwendet man <, bleibt das letzte Element unsortiert.

NDEBUG

Kommt drauf an wie du zählst. Zählst du in Array Notation dann hast du Recht und du solltest auf kleiner, gleich testen.