Bubble Сортировка рекурсивно

Question

Я искал Google, и я ничего не могу найти для этого. Я искал разные типы (как вы можете видеть в моем предыдущем вопросе), и мне было интересно, знает ли кто-нибудь о рекурсивном коду сортировки пузырьков. Для меня идея звучит смешно, но я хочу быть готовым к вещам, и мне любопытно, можно ли это сделать. Я уверен, что это возможно, поскольку мой профессор в прошлом спросил об этом своих учеников. Я не думаю, что он будет повторять вопросы, но мне стало любопытно и хотелось узнать, был ли рекурсивно найден код для пузырьковой сортировки.

Answer 1

Это, безусловно, можно сделать, поскольку любой итерационный алгоритм может быть преобразован в рекурсивный и наоборот.

Вот один из способов, которым мы можем это сделать. Для простоты я использую C++ и предполагаю, что входные данные являются целыми числами.

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

Интересно, что каждая рекурсивная функция здесь хвостовая рекурсия, поэтому хороший оптимизирующий компилятор должен быть способен генерировать нерекурсивный код. Другими словами, хороший компилятор должен генерировать почти такой же код, как если бы мы написали это итеративно. Если у меня будет время, я проверю, действительно ли это происходит. :-)