Pure implementation of shell sort algorithm in Python :param collection: Some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending >>> shell_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> shell_sort([]) []
(collection)
| 13 | |
| 14 | |
| 15 | def shell_sort(collection): |
| 16 | """Pure implementation of shell sort algorithm in Python |
| 17 | :param collection: Some mutable ordered collection with heterogeneous |
| 18 | comparable items inside |
| 19 | :return: the same collection ordered by ascending |
| 20 | |
| 21 | >>> shell_sort([0, 5, 3, 2, 2]) |
| 22 | [0, 2, 2, 3, 5] |
| 23 | |
| 24 | >>> shell_sort([]) |
| 25 | [] |
| 26 | |
| 27 | >>> shell_sort([-2, -5, -45]) |
| 28 | [-45, -5, -2] |
| 29 | """ |
| 30 | # Marcin Ciura's gap sequence |
| 31 | gaps = [701, 301, 132, 57, 23, 10, 4, 1] |
| 32 | |
| 33 | for gap in gaps: |
| 34 | i = gap |
| 35 | while i < len(collection): |
| 36 | temp = collection[i] |
| 37 | j = i |
| 38 | while j >= gap and collection[j - gap] > temp: |
| 39 | collection[j] = collection[j - gap] |
| 40 | j -= gap |
| 41 | collection[j] = temp |
| 42 | i += 1 |
| 43 | |
| 44 | return collection |
| 45 | |
| 46 | if __name__ == '__main__': |
| 47 | try: |