python/algorithms/sorting/shell_sort.py at master · ImadBel-code/python · GitHub

35 lines (23 loc) · 768 Bytes

"""This is a Python implementation of the shell sort algorithm

Shell sort is a variation of insertion sort. This method starts by sorting

pairs of elements far away from each other, then progressively reducing the

gap between elements to be compared.

"""

from random import randint

def shell_sort(arr):

n = len(arr)

gap = n//2

while gap > 0:

for i in range(gap, n):

tmp = arr[i]

j = i

while j >= gap and arr[j-gap] > tmp:

arr[j] = arr[j-gap]

j -= gap

arr[j] = tmp

gap //= 2

return arr

# Tests

if __name__ == '__main__':

print(shell_sort([randint(0, 1000) for _ in range(10)]))

print(shell_sort([randint(-500, 500) for _ in range(10)]))

Expand file tree