rekursion



  • hallo,
    habe ein Problem....
    Musste ein Programm schreiben...welches Zahlen mit dem MergeSort verfahren sortiert...oben drauf soll es rekursiv geschehen.

    Das habe ich alles denke ich Gut hinbekommen, nur leider stolpere ich an der letzten Anforderung:

    Die Rekursion soll schon abbrechen, wenn nicht mehr als
    drei Komponenten zu sortieren sind.

    Habe schon Freunde gefragt, die konnten mir leider ned helfen

    Würde mich freuen
    danke

    CODE:

    void m_sort(int numbers[], int groesse){
      int b[MAX_ELEMS];
      int i,j,k,m,r;
    
      if (groesse > 1) {
        //Die Grenzen der beiden Teilfelder berechnen ... 
        m = groesse / 2; 
        r = m;
        if (groesse % 2) 
        r++;
    
        // Teilfelder rekursiv sortieren.
        m_sort(&numbers[0],m); 
        m_sort(&numbers[m],r);
    
        //Die beiden vorsortierten Felder umkopieren ... 
        for (i = 0; i < m; i++) 
        b[i] = numbers[i];
        for (j = m; j < groesse; j++) 
        b[groesse-j+m-1] = numbers[j];
    
        // ... und mischen. 
        i = 0; j = groesse -1;
        for (k = 0; k < groesse; k++) {
          if (b[i] < b[j]) numbers[k] = b[i++];
          else             numbers[k] = b[j--];
        }
      }  
      return;
    }
    


  • dann musst du nur die abbruchbedingung aendern. oder ist es das nicht?



  • habe gar keinen ansatzpunkt...ich weiss ned wie ich das machen soll



  • doubleAction schrieb:

    Die Rekursion soll schon abbrechen, wenn nicht mehr als
    drei Komponenten zu sortieren sind.

    Wenn du das als Abbruchbedingung haben willst, mußt du es auch so formulieren:

    if(groesse <= 3)
    {
      //Sonderbehandlung "nicht mehr als drei Komponenten"
    }
    else
    {
      //normale mergesort-Sortierung
    }
    


  • if (groesse <= 3)  { //müsste dann groesse >1 stehen und dann mit dem DreiecksTausch alle 3unsortierten...sortieren.
      	if(numbers[0]>= numbers[1]){
      		hilf=numbers[0];
      		numbers[0]=numbers[1]
      		numbers[1]=hilf;
      	}
      	if(numbers[1]>= numbers[2]){
      		hilf=numbers[1];
      		numbers[1]=numbers[2]
      		numbers[2]=hilf;
      	}
      	if(numbers[0]>= numbers[2]){
      		hilf=numbers[1];
      		numbers[1]=numbers[2]
      		numbers[2]=hilf;
      	}
    

    wäre das in dieser Form richtig??? weil ich kann ja nichts ausgeben und dann auch nicht sehen...obs soweit stimmt....

    danke nochmal...



  • Erstens kannst du nicht davon ausgehen, dass groesse genau 3 ist. Es kann auch 1 oder 2 sein. Zweitens musst du bei der dritten Prüfung nochmal [0] und [1] testen, sonst kann das schiefgehen.


Log in to reply