В чем преимущество Shell Sort по сравнению с Insertion / Bubble Sort?

Question

Мой профессор дал мне следующее определение «Сортировка оболочки».Я также включил алгоритмы Bubble и Insertion Sort.

В чем преимущество использования Shell Sort по сравнению с обычной сортировкой Insertion Sort или Bubble Sort с gap=1?В конце концов, Shell Sort все равно сводится к этому, верно?

Я не прошу вас делать мою домашнюю работу.Я законно запутался и хочу понять, что происходит.

Кроме того, я уже посетил Википедию и увидел таблицу сложности времени, и я уже знаю, что они говорят.Я ищу почему , а не что .

def shell(a, n):
    gap = n / 2

    while gap >= 1:
            insertion(a, n, gap) # or bubble
            gap /= 2

def bubble(a, n, gap=1):
    for i in range(n):
            for j in range(n-i-gap):
                    if a[j] > a[j+gap]:
                            swap(a, j, j+1)

def insertion(a, n, gap=1):
    for i in range(1,n):
            x = a[i]
            j = i-gap

            while j>=0 and  a[j]>x:
                    a[j+gap] = a[j]
                    j-=gap

            a[j+gap]=x

Answer 1

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

Записи в Википедии

• http://en.wikipedia.org/wiki/Shell_sort
• http://en.wikipedia.org/wiki/Insertion_sort
• http://en.wikipedia.org/wiki/Bubble_sort

охватывают различия.

Редактировать:

Представьте, что у вас есть кучакарты в вашей руке и карты почти в порядке, за исключением того, что первая и последняя поменялись местами.пузырчатая сортировка была бы проблемой, потому что было бы около 2n перестановок, сортировка вставки была бы лучше с n перестановками, но сортировка оболочки могла бы сделать это в 1. (количество перестановок изменяется в зависимости от реализации алгоритма, это простопример)

Answer 2

Логика сортировки оболочки заключается в сортировке записей, которые находятся дальше. С учетом частично отсортированного списка вы можете в теории сортировать намного быстрее, чем O (n ^ 2). Также, учитывая большой несортированный массив, высока вероятность того, что ваша окончательная отсортированная позиция будет далеко от вашей текущей позиции. Так что логически имеет смысл использовать больший зазор. Но главное в сортировке оболочек на самом деле не ее производительность, а простота алгоритма и низкое использование стековой памяти.

Учитывая, что в среднем он работает лучше, чем O (n ^ 2) (зависит от последовательности пробелов), небольших размеров кода и использования стека, он очень популярен во встроенных приложениях, где ограничения памяти являются фактором.

Answer 3

Разница - это эффективность.

Сортировка вставки и сортировка по пузырям - O (n ^ 2), в то время как сортировка вставки - O (n log n).

Это означает, что если выиметь коллекцию, состоящую из 100 элементов, количество операций с сортировкой Bubble и Insert составляет K * 100 ^ 2 = K * 10000 операций, где K зависит от других факторов, но в основном постоянно.

Использование командной консолиСортировка, необходимых операций будет Q * 100 * Log 100 = Q * 100 * 2 = Q * 2000 операций, где Q зависит от других факторов и в основном постоянна.