Доброго часу доби, дорогі читачі!
Сьогоднішню статтю я б хотів присвятити ще одному чудовому алгоритму сортування, що носить ім'я Дональда Шелла.
Не секрет, що сортування Шелла часто працює повільніше, ніж швидке сортування (сортування Хоара), яку я розглядав в одній з попередніх статей. Однак, швидке сортування швидко сповільнюється до квадратичної складності при невдалому наборі даних, що є найгіршим результатом, ніж найгірший час для сортування Шелла.
При сортуванні ми порівнюємо і сортуємо елементи в масиві, віддалені один від одного на n осередків. Далі n зменшується і процедура повторюється знову з оновленим значенням n. Так до тих пір, поки n не зменшиться до 1.
Після вибору послідовності відстаней можна приступити до реалізації.
Як і завжди, в функцію сортований масив будемо передавати по посиланню. Для прикладу я буду зменшувати крок вдвічі на кожній ітерації.
У тілі циклу ми збираємо подмассів значень, ключі яких відстоять один від одного на крок, зазначений в циклі, і сортуємо їх простий вставкою.
Результат сортування такий можна подивитися тут:
За сім на сьогодні все! Безпомилкового Вам коду!
Навігація по публікаціям
Я на GeekBrains
Powered by
