Rekursiver InsertionSort



  • Hi Leute!

    Ich hab hier einen rekursiven InsertionSort programmiert, der auch soweit funktioniert, nur einen kleinen Fehler, den ich nicht finde. Der Algorithmus läuft beim rekursive Aufstig immer um einen Schritt zu weit und will mir so ein nicht vorhandenes Element an die Stelle 0 schreiben. Ich vermutete den Fehler in der Abbruchbedingung, was er aber nicht war 😞 Und jetzt bin ich ziemlich ratlos...

    int InsertionSort_Rekursiv(int a[], int n)
    {
    	int i, key;
    
    	if(n == 0)
    	{
    		return a[n];
    	}
    
    	InsertionSort_Rekursiv(a, n-1);
    
    	key = a[n];
    	i = n-1;
    
    	while (i >= 0 && a[i] > key)
    	{
    		a[i+1] = a[i];
    		i = i-1;
    	}
    
    	a[i+1] = key;
    }
    


  • Und wie rufst du das ganze auf?
    Zeig mal dein main dazu.



  • Wie sollen wir wissen, wie man das aufruft? Die augenscheinlichste Möglichkeit ist:

    int InsertionSort_Rekursiv(int a[], int n);
    Sortiert die ersten n Einträge des Arrays a der Größe nach.

    Dann ist allerdings die Zeile 14 in Deinem Code falsch, wenn n die Gesamtzahl der Elemente in a ist.

    Was ist die Bedeutung des Rückgabewerts?



  • DirkB: Der Aufruf findet so statt:

    int main()
    {
    	int feld[] = {-5,13,-32,7,-3,17,23,12,-35,19};
    
    	InsertionSort_Rekursiv(feld, 10);
    
    	Output(feld, 10);
    
    return 0;
    }
    

    Die Bedeuting vom return innerhalb des if's ist, dass hier das Feld a zurückgegeben wird. So hätt ich das jetzt beschrieben.
    Das n ist in der Tat die Gesamtanzahl der Elemente im Array a. Sie wird mit 10 übergeben. Bisher habe ich den Vorgang des einfügens, also bei mir quasi das while, immer so gemacht, dass eine Stelle weiter gegriffen wird und dann mit der eigentlich Stelle verglichen wird. Genau das macht aber mein Algo. an dieser Stelle auch! Er greift in erstem Durchlauf auf Stelle 1 erniedrigt dann n um eins schreibt das in die Laufvariable i und tauscht ggf. aus.

    Edit: Wenn ich den Funktionsaufruf mit 9 anstatt 10 mache, funktioniert der Algo. Was ich aber ja eigentlich nicht darf, da ich ja wirklich 10 Elemente im Feld a gespeichert hab! Wo muss ich also in der Funktion das n künstlich um 1 verringern?



  • Die Index bei einem Array fängt bei 0 an. Wenn du also 10 Elemente hast, laufen die von 0 bis 9.
    Das Element mit dem Index 10 existiert nicht.
    Aber darauf greifst du in Zeile 14 und Zeile 19 (im ersten Durchgang) zu.
    Du hast da zwar i = n-1; aber danach auch a[i+1] = a[i];

    Dein Rückgabewert nutzt überhaupt nichts.
    1. fehlt in Zeile 24 ein Rückgabewert
    2. Gibst du a[0] zurück, der aber in Zeile 11 auch verworfen wird.
    3. wird das Array auch so verändert.



  • int InsertionSort_Rekursiv(int a[], int n)
    {
    	int i, key;
    
    	if(n == 0)
    	{
    		return a[n];
    	}
    	else
    	{
    		InsertionSort_Rekursiv(a, n-1);
    	}
    
    	key = a[n];
    	i = n-1;
    
    	while (i >= 0 && a[i] > key)
    	{
    		a[i+1] = a[i];
    		i = i-1;
    	}
    
    	a[i+1] = key;
    
    	return a[n];
    }
    

    Ich hab jetzt mal versucht deine Tips umzusetzen. Ich weiß nich ob du mein Edit gelesen hast. Wenn ich die Funktion aus der main mit n=9 anstatt n=10 starte, dann funktioniert das Ganze übrigens. So wie der Code jetzt nun steht, funktioniert alles so wie bisher. Er läuft mir immer um eins zu weit!



  • bandchef schrieb:

    Ich weiß nich ob du mein Edit gelesen hast.

    Nein

    bandchef schrieb:

    Wenn ich die Funktion aus der main mit n=9 anstatt n=10 starte, dann funktioniert das Ganze übrigens.

    Lies meinen ersten Satz von meinem letzten Post

    bandchef schrieb:

    So wie der Code jetzt nun steht, funktioniert alles so wie bisher. Er läuft mir immer um eins zu weit!....
    Edit: Wenn ich den Funktionsaufruf mit 9 anstatt 10 mache, funktioniert der Algo. Was ich aber ja eigentlich nicht darf, da ich ja wirklich 10 Elemente im Feld a gespeichert hab! Wo muss ich also in der Funktion das n künstlich um 1 verringern?

    Wie wärs ganz am Anfang der Funktion? Zeile 4 oder so.



  • Ahso. Du meinst also, dass der ganze Algo in Ordnung ist, nur bis auf den Fehler, dass ich den Algo mit dem falschen n aufrufe. Dann hab ich also quasi die ganze Zeit einen Fehler gesucht, den es gar nicht gab... Schön dumm 😃


Log in to reply