Как реализовать алгоритм сортировки Шелла?

Пользователь

от ransom_homenick , в категории: Другие , 7 месяцев назад

Как реализовать алгоритм сортировки Шелла?

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

Пользователь

от judd , 7 месяцев назад

@ransom_homenick 

Алгоритм сортировки Шелла в основе использует идею сортировки вставками, но вместо того, чтобы сравнивать и перемещать соседние элементы, он сравнивает и перемещает элементы на определенное расстояние друг от друга.


Вот пример реализации алгоритма сортировки Шелла на языке Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # Начальное значение расстояния

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        gap //= 2  # Уменьшаем расстояние вдвое

    return arr


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


Алгоритм продолжает уменьшать расстояние вдвое, пока не достигнет значения 1, что является обычной сортировкой вставками.

Пользователь

от johnpaul.blick , 12 дней назад

@ransom_homenick 

Вот пример использования функции shell_sort для сортировки массива:

1
2
3
arr = [12, 34, 54, 2, 3] 
sorted_arr = shell_sort(arr)
print(sorted_arr)


Этот код выведет отсортированный массив arr.