Bulle Trier récursivement

Question

J'ai cherché Google et je ne trouve rien pour cela. Je cherchais différents types de sortes (comme vous pouvez le voir dans une de mes précédentes questions) et je me demandais si quelqu'un connaissait un code de tri à bulles récursif. Pour moi, l'idée semble ridicule, mais je veux être préparé pour les choses et je suis curieux de savoir si cela peut être fait ou non. Je suis sûr que c'est possible, comme un de mes professeurs l'a demandé à ses étudiants par le passé. Je ne pense pas qu'il va répéter des questions, mais je suis devenu curieux et je voulais savoir s'il y avait du code pour un tri à bulles récursivement.

Answer 1

Il est certainement possible de le faire, car n'importe quel algorithme itératif peut être converti en un algorithme récursif et vice-versa.

Voici une façon de procéder. Pour simplifier, j'utilise C++ et suppose que les entrées sont toutes des entiers.

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); 
    } 
} 

Fait intéressant, chaque fonction récursive est ici récursive, donc un bon compilateur d'optimisation devrait être en mesure de générer un code non récurrent. En d'autres termes, un bon compilateur devrait générer à peu près le même code que si nous l'avions écrit de manière itérative. Si j'ai le temps, je vérifierai si cela se produit réellement. :-)