Sortierung mit Rekursion

Question

Ich habe die folgende Funktion, um ein ungeordnetes Array zu sortieren, um gerade Zahlen in der Front und ungerade Zahlen in der Rückseite zu haben. Gibt es eine Möglichkeit, dies ohne Schleifen zu erreichen?

//front is 0, back =array.length-1;
arrangeArray (front, back);

public static void arrangeArray (int front, int back)
{
    if (front != back || front<back)
    {
        while (numbers [front]%2 == 0)
            front++;

        while (numbers[back]%2!=0)
            back--;

        if (front < back)
        {
            int oddnum = numbers [front];
            numbers[front]= numbers[back];
            numbers[back]=oddnum;

            arrangeArray (front+1, back-1);
        }
    }
}

Answer 1

Mergesort ist ohne Schleifen recht trivial zu kodieren:

void mergesort(int lo, int hi)
{
    if (lo<hi)
    {
        int m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}

Ich überlasse es dem Leser, eine gerade/ungerade Sortierung vorzunehmen :)

(Klingt wie Hausaufgaben)

Answer 2

Bei einer Rekursion gibt es einen Basisschritt und einen rekursiven Schritt.

In diesem Fall ist die Grundbedingung, dass vorne == hinten ist, denn man beginnt an den Rändern und endet in der Mitte. Wenn man in der Mitte angekommen ist, weiß man, dass es fertig ist.

Bevor Sie den rekursiven Schritt machen, müssen Sie ein wenig sortieren. Sie sortieren immer nur einen Schritt nach dem anderen, also kümmern Sie sich erst einmal nur um die Elemente in array[front] und array[back]. Nachdem Sie diese an der richtigen Stelle angeordnet haben, führen Sie einen rekursiven Aufruf durch.

Das Ergebnis sieht dann etwa so aus:

public static void arrangeArray (int front, int back)
{
   if(front >= back) return;
   int f = numbers[front];
   int b = numbers[back];
   if(f%2 == 0) {
      front++;
   } else {
      numbers[back] = f;
      back--;
   }
   if (b%2 == 0) {
      numbers[front] = b;
      front++;
   } else {
      back--;
   }  
   arrangeArray(front, back);                                         
}

Es ist ungetestet und funktioniert wahrscheinlich nicht für Randbedingungen, aber es ist ein guter Anfang :)

Answer 3

Wäre das nicht einfach:

//front is 0, back =array.length-1; 
arrangeArray (front, back); 

public static void arrangeArray (int front, int back) 
{ 
    if (front != back || front<back)
    { 
        if (numbers [front]%2 == 0) 
            arrangeArray (front+1, back); 
        else
        if (numbers[back]%2!=0) 
            arrangeArray (front, back-1); 
        else
        if (front < back) 
        { 
            int oddnum = numbers [front]; 
            numbers[front]= numbers[back]; 
            numbers[back]=oddnum; 

            arrangeArray (front+1, back-1); 
        } 
    } 
} 

?

Answer 4

Darf ich dieses Python-Snippet empfehlen, um das Denken auf hohem Niveau anzuregen?

compare = lambda x,y: x - y if x%2 == y%2 else y%2 - x%2
>>> sorted([3,4,2,1,5,6,7,90,23,44], cmp=compare)
[1, 3, 5, 7, 23, 2, 4, 6, 44, 90]

Ich denke, man muss eine Komparatorfunktion erstellen, die negativ, 0 und positiv zurückgibt, und diese verwenden.

Answer 5

Was Sie tun möchten, ist

arrangeArray(front, back, bool recursed=false) {
    if (recursed) {
        arrangeArray(front, back/2, true);
        return arrangeArray(back/2, back, true);
    }
    // Do stuff here.
}