Pure implementation of comb sort algorithm in Python :param collection: some mutable ordered collection with heterogeneous comparable items inside :return: the same collection ordered by ascending Examples: >>> comb_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> comb_sort([])
(data)
| 13 | """ |
| 14 | |
| 15 | def comb_sort(data): |
| 16 | """Pure implementation of comb 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 | Examples: |
| 21 | >>> comb_sort([0, 5, 3, 2, 2]) |
| 22 | [0, 2, 2, 3, 5] |
| 23 | >>> comb_sort([]) |
| 24 | [] |
| 25 | >>> comb_sort([-2, -5, -45]) |
| 26 | [-45, -5, -2] |
| 27 | """ |
| 28 | shrink_factor = 1.3 |
| 29 | gap = len(data) |
| 30 | swapped = True |
| 31 | i = 0 |
| 32 | |
| 33 | while gap > 1 or swapped: |
| 34 | # Update the gap value for a next comb |
| 35 | gap = int(float(gap) / shrink_factor) |
| 36 | |
| 37 | swapped = False |
| 38 | i = 0 |
| 39 | |
| 40 | while gap + i < len(data): |
| 41 | if data[i] > data[i+gap]: |
| 42 | # Swap values |
| 43 | data[i], data[i+gap] = data[i+gap], data[i] |
| 44 | swapped = True |
| 45 | i += 1 |
| 46 | |
| 47 | return data |
| 48 | |
| 49 | |
| 50 | if __name__ == '__main__': |