Пузырьковая сортировка рекурсивно - PullRequest
Новая
       10

Пузырьковая сортировка рекурсивно

1 голос
/ 16 декабря 2010

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

1 Ответ

0 голосов
/ 26 августа 2015

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

Вот один из способов, которым мы можем это сделать. Для простоты я использую 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);
    }
}

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

...