Bubble Sort rekursiv

Question

Ich habe Google gesucht und ich kann nichts dafür finden. Ich suchte nach verschiedenen Arten von Arten (wie Sie in einer meiner vorherigen Fragen sehen können) und ich fragte mich, ob jemand eine rekursive Blasenkodierung kannte. Die Idee klingt für mich lächerlich, aber ich möchte auf Dinge vorbereitet sein und bin gespannt, ob das möglich ist oder nicht. Ich bin mir sicher, dass es möglich ist, wie ein Professor von mir das von seinen Schülern in der Vergangenheit gefragt hat. Ich glaube nicht, dass er Fragen wiederholen wird, aber ich wurde neugierig und wollte wissen, ob Code für eine Blasensorte rekursiv vorhanden war.

Answer 1

Es ist sicherlich möglich, dies zu tun, da jeder iterative Algorithmus in einen rekursiven umgewandelt werden kann und umgekehrt.

Hier ist eine Möglichkeit, wie wir dies tun können. Der Einfachheit halber verwende ich C++ und nehme an, dass die Eingaben alle Ganzzahlen sind.

void bubbleSort(std::vector<int>& list) { 
    /* Make one pass of swapping elements. If anything was swapped, 
    * repeat this process. 
    */ 
    if (swapPass(list)) { 
     bubbleSort(list); 
    } 
} 

/* Does a pass over the array, swapping adjacent elements if they're 
* out of place. Returns true if anything was swapped and false 
* otherwise. 
*/ 
bool swapPass(std::vector<int>& list) { 
    return recSwapPass(list, 0, false); 
} 

/* Does a swap pass starting from index given information about 
* whether a swap was made on the pass so far. Returns true if across 
* the entire pass a swap was made and false otherwise. 
*/ 
bool recSwapPass(std::vector<int>& list, unsigned index, 
       bool wasSwapped) { 
    /* Base case: If we're at the end of the array, then there's 
    * nothing to do and we didn't swap anything. 
    */ 
    if (index + 1 >= list.size()) return wasSwapped; 

    /* Compare the current element against the next one and see if 
    * they need to swap. 
    */ 
    if (list[index] > list[index + 1]) { 
     std::swap(list[index], list[index + 1]); 
     return recSwapPass(list, index + 1, true); 
    } else { 
     return recSwapPass(list, index + 1, wasSwapped); 
    } 
} 

Interessanterweise hier jede rekursive Funktion ist Schwanz-rekursiv, so dass ein guter optimierenden Compiler sollte in der Lage sein, nicht-rekursive Code zu generieren. Mit anderen Worten, ein guter Compiler sollte so ziemlich den gleichen Code erzeugen, wie wenn wir dies iterativ geschrieben hätten. Wenn ich die Zeit bekomme, überprüfe ich, ob das tatsächlich passiert. :-)