пузырьковая сортировка рекурсивно без петель - PullRequest
Новая
       15

пузырьковая сортировка рекурсивно без петель

0 голосов
/ 15 февраля 2020

Возможно ли вообще выполнять пузырьковую сортировку без каких-либо глобальных переменных / переменных c, только с одним массивом и без циклов? Мне интересно, возможно ли это, и если да, то сложно?

моя функция будет принимать массив только с числами и размером.

int bubble_sort_asc_rec(int tab[], int size)

Ответы [ 2 ]

0 голосов
/ 02 апреля 2020

Вот реализация, использующая Python. Однако вместо функции, имеющей длину массива в качестве второго аргумента, она имеет переменную count. Я также включил два теста. 

def get_largest(arr, count):
    if len(arr) <= 1:
        return arr
    if arr[0] >= arr[1]:
        temp = arr[0]
        arr[0] = arr[1]
        arr[1] = temp
        return get_largest(arr, count)
    else:
        return [arr[0]] + get_largest(arr[1:], count)

def bubblesort(arr, count):
    if count == len(arr):
        return arr
    arr = get_largest(arr, count)
    return bubblesort(arr, count + 1)

arr_test = [item for item in reversed(range(1,10))]
arr_test2 = [3, 5, 1, 7, 8, 9, 4]

print('First Test Array: ', arr_test)
print('Sorted: ', bubblesort(arr_test, 0))

print('Second Test Array: ', arr_test2)
print('Sorted: ', bubblesort(arr_test2, 0))
0 голосов
/ 15 февраля 2020 
#include <stdio.h>

int bubble_sort_pass(int array[], int size)
{
    /* We return the number of swaps in this iteration. */
    int swaps = 0;

    /* If the array contains 0 or 1 elements, it is already sorted. */
    if (size < 2) {
        return swaps;
    }

    /* Array contains at least 2 elements. */
    if (array[0] > array[1]) {
        /* First two elements are in wrong order. We need to swap them. */
        printf("Swap value %d with value %d\n", array[0], array[1]);
        int temp = array[0];
        array[0] = array[1];
        array[1] = temp;
        swaps += 1;
    }

    /* Recursively bubble sort the array starting at the 2nd element. */
    swaps += bubble_sort_pass(array + 1, size - 1);
    return swaps;
}

void bubble_sort(int array[], int size)
{
    /* Do one pass of bubble sorting the entire array. */
    printf("Start a bubble sort pass.\n");
    int swaps = bubble_sort_pass(array, size);

    /* If there was at least one swap, we have to do another pass. */
    if (swaps >= 1) {
        bubble_sort(array, size);
    }

}


int main()
{
    int numbers[] = {10, 8, 3, 7, 2, 1, 4, 6, 5, 9};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    bubble_sort(numbers, count);
    for(int i=0; i<count; ++i) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }
    return 0;
}

В C вы бы обычно не реализовали сортировку пузырьками таким образом; вместо этого вы бы использовали итеративный подход (т.е. циклы).

Эта рекурсивная реализация предназначена исключительно для учебных целей. Некоторые так называемые «чисто функциональные» языки не имеют циклов, они имеют только рекурсию. Одним из таких языков является Erlang.

Обратите внимание, что рекурсивный вызов bubble_sort является последним оператором в bubble_sort. Это называется «хвостовой рекурсией» и позволяет компилятору оптимизировать проталкивание адреса возврата в стек. C компилятор (скорее всего) не будет выполнять такую ​​оптимизацию хвостовой рекурсии, но функциональный компилятор (например, компилятор Erlang) сделает это.

Рекурсивный вызов bubble_sort_pass в bubble_sort_pass в настоящее время не является вызовом хвостовой рекурсии, но его можно легко превратить в вызов рекурсии хвоста (убедитесь сами!)

...