Write a python program to Implement Radix sort and print the sorted list for the below list
def radix_sort(alist, base=10):
if alist == []:
return
def key_factory(digit, base):
def key(alist, index):
return ((alist[index]//(base**digit)) % base)
return key
largest = max(alist)
exp = 0
while base**exp <= largest:
alist = counting_sort(alist, base - 1, key_factory(exp, base))
exp = exp + 1
return alist
def counting_sort(alist, largest, key):
c = [0]*(largest + 1)
for i in range(len(alist)):
c[key(alist, i)] = c[key(alist, i)] + 1
c[0] = c[0] - 1
for i in range(1, largest + 1):
c[i] = c[i] + c[i - 1]
result = [None]*len(alist)
for i in range(len(alist) - 1, -1, -1):
result[c[key(alist, i)]] = alist[i]
c[key(alist, i)] = c[key(alist, i)] - 1
return result
alist = [2, 3, 5, 6, 4, 5]
sorted_list = radix_sort(alist)
print('Sorted list: ', end='')
print(sorted_list)
Write a python program to Implement Bucket sort and print the sorted list for the below list
def bucket_sort(alist):
largest = max(alist)
length = len(alist)
size = largest/length
buckets = [[] for _ in range(length)]
for i in range(length):
j = int(alist[i]/size)
if j != length:
buckets[j].append(alist[i])
else:
buckets[length - 1].append(alist[i])
for i in range(length):
insertion_sort(buckets[i])
result = []
for i in range(length):
result = result + buckets[i]
return result
def insertion_sort(alist):
for i in range(1, len(alist)):
temp = alist[i]
j = i - 1
while (j >= 0 and temp < alist[j]):
alist[j + 1] = alist[j]
j = j - 1
alist[j + 1] = temp
alist = [2, 3, 5, 6, 4, 5]
sorted_list = bucket_sort(alist)
print('Sorted list: ', end='')
print(sorted_list)
Write a python program to Implement Gnome sort and print the sorted list for the below list
def gnome_sort(alist):
for pos in range(1, len(alist)):
while (pos != 0 and alist[pos] < alist[pos - 1]):
alist[pos], alist[pos - 1] = alist[pos - 1], alist[pos]
pos = pos - 1
alist = [2, 3, 5, 6, 4, 5]
gnome_sort(alist)
print('Sorted list: ', end='')
print(alist)
Write a python program to Implement Cocktail Shaker sort and print the sorted list for the below list
def cocktail_shaker_sort(alist):
def swap(i, j):
alist[i], alist[j] = alist[j], alist[i]
upper = len(alist) - 1
lower = 0
no_swap = False
while (not no_swap and upper - lower > 1):
no_swap = True
for j in range(lower, upper):
if alist[j + 1] < alist[j]:
swap(j + 1, j)
no_swap = False
upper = upper - 1
for j in range(upper, lower, -1):
if alist[j - 1] > alist[j]:
swap(j - 1, j)
no_swap = False
lower = lower + 1
alist = [2, 3, 5, 6, 4, 5]
cocktail_shaker_sort(alist)
print('Sorted list: ', end='')
print(alist)
Write a python program to Implement Comb sort and print the sorted list for the below list
def comb_sort(alist):
def swap(i, j):
alist[i], alist[j] = alist[j], alist[i]
gap = len(alist)
shrink = 1.3
no_swap = False
while not no_swap:
gap = int(gap/shrink)
if gap < 1:
gap = 1
no_swap = True
else:
no_swap = False
i = 0
while i + gap < len(alist):
if alist[i] > alist[i + gap]:
swap(i, i + gap)
no_swap = False
i = i + 1
alist = [2, 3, 5, 6, 4, 5]
comb_sort(alist)
print('Sorted list: ', end='')
print(alist)
Write a python program to Implement Shell sort and print the sorted list for the below list
def gaps(size):
length = size.bit_length()
for k in range(length - 1, 0, -1):
yield 2**k - 1
def shell_sort(alist):
def insertion_sort_with_gap(gap):
for i in range(gap, len(alist)):
temp = alist[i]
j = i - gap
while (j >= 0 and temp < alist[j]):
alist[j + gap] = alist[j]
j = j - gap
alist[j + gap] = temp
for g in gaps(len(alist)):
insertion_sort_with_gap(g)
alist = [2, 3, 5, 6, 4, 5]
shell_sort(alist)
print('Sorted list: ', end='')
print(alist)
