This program allows one to use many different sorting algorithms to sort an iterable.
from time import*
from random import*
#GNOME SORT
def gnome_sort(lst):
pos = 1
while pos < len(lst):
if lst[pos] >= lst[pos-1]:
pos = pos+1
else:
temp = lst[pos]
lst[pos] = lst[pos-1]
lst[pos-1] = temp
if pos > 1:
pos = pos - 1
else:
pos = pos + 1
return lst
#SELECTION SORT
def smallest(lst):
"""Finds the smallest element in the list."""
small = lst[0]
for i in range(len(lst)):
if lst[i] < small:
small = lst[i]
else:
small = small
return small
def selection_sort(lst):
"""Sorts the list through selection sort. Selection sort is
done by finding the smallest element in the unsorted list, removing
it from the unsorted list, placing it into the sorted list, and then
repeating this with the rest of the unsorted list."""
sorted_lst = []
def smallest_insert(lst):
sorted_lst.append(smallest(lst))
lst.remove(smallest(lst))
for i in range(len(lst)):
smallest_insert(lst)
return sorted_lst
#INSERTION SORT
def insert(el, lst):
if lst == []:
return [el]
elif el <= lst[0]:
return [el]+lst
else:
return [lst[0]]+insert(el, lst[1:])
def insertion_sort(lst):
return foldr(insert, [], lst)
#BUBBLE SORT
def bubble_sort(lst):
"""This sorts the list through bubble sort. Bubble sort is done
by going through each element in the list, checking if the next element
is greater than the one being checked, and swapping them. This is then
repeated over and over until the list is fully sorted."""
for i in range(len(lst)):
for j in range(len(lst)-1):
if lst[j] > lst[(j+1)]:
temp = lst[j]
lst[j] = lst[j+1]
lst[j+1] = temp
else:
lst[j] = lst[j]
return lst
#SHELL SORT (sequence: 4,3,2,1)
def shell_sort(lst):
diff = 4
for i in range(len(lst)-4):
if lst[i] > lst[i+diff]:
temp = lst[i]
lst[i] = lst[i+diff]
lst[i+diff] = temp
else:
lst[i] = lst[i]
diff = 3
for i in range(len(lst)-3):
if lst[i] > lst[i+diff]:
temp = lst[i]
lst[i] = lst[i+diff]
lst[i+diff] = temp
else:
lst[i] = lst[i]
diff = 2
for i in range(len(lst)-2):
if lst[i] > lst[i+diff]:
temp = lst[i]
lst[i] = lst[i+diff]
lst[i+diff] = temp
else:
lst[i] = lst[i]
diff = 1
for i in range(len(lst)-1):
if lst[i] > lst[i+diff]:
temp = lst[i]
lst[i] = lst[i+diff]
lst[i+diff] = temp
else:
lst[i] = lst[i]
return lst
#QUICK SORT
def quick_sort(lst):
"""Quick sort chooses a pivot element, places the elements greater than
and less than the pivot into places relative to the pivot, and are then
recursively sorted."""
lst1 = [x for x in lst[1:] if x <= lst[0]]
lst2 = [y for y in lst if y > lst[0]]
if len(lst) == 0:
return lst
elif len(lst) == 1:
return lst
else:
return quick_sort(lst1) + [lst[0]] + quick_sort(lst2)
#SIMPLE MERGE SORT
def split(lst):
"""This splits a list into sublists of pairs of elements."""
split_list = []
x = 0
if len(lst) % 2 == 0:
while x < len(lst):
split_list.append([lst[x], lst[x+1]])
x = x + 2
return split_list
else:
while x < len(lst)-1:
split_list.append([lst[x], lst[x+1]])
x = x + 2
return split_list + [lst[len(lst)-1]]
def merge(lst1, lst2):
"""This merges two lists into one."""
lst = lst1 + lst2
return selection_sort(lst)
def foldr(combiner, base, lst):
if lst == []:
return base
else:
return combiner(lst[0], foldr(combiner, base, lst[1:]))
def simple_merge_sort(lst):
"""This does the simple merge sort. The list is split into sublists,
each sublist is selection-sorted recursively, and the sorted sublists are
then re-merged."""
if len(lst) == 1:
return lst
elif len(lst)%2 == 0:
return foldr(merge, [], split(lst))
else:
popped = lst[0]
lst.pop(0)
return selection_sort([popped] + foldr(merge, [], split(lst)))
#MERGE SORT
def merge_sort(lst):
"""Splits the list into two sublists, sorts the sublists
recursively and merges them back together."""
if len(lst) == 1:
return lst
else:
sublist1 = lst[0:len(lst)/2]
sublist2 = lst[len(lst)/2:]
return merge(merge_sort(sublist1), merge_sort(sublist2))
#COUNTING SORT (up to 30)
lst = [randint(1,11) for number in range(10)]
def counting_sort(lst):
C = [] #counting array
target = [] #target array
for i in range(31):
C.append(lst.count(i))
for k in range(len(C)):
if C[k] == 0:
target = target
else:
for number in range(C[k]):
target.append(k)
return target
#COUNTER SORT (BASED ON COUNTING SORT)
lst1 = [randint(1,21) for number in range(20)]
def less_than(a, b):
return a < b or a == b
def counter_sort(lst):
"""In this algorithm, the final list is populated with zeroes;
the number of elements less than or equal to each element in the list is
counted by comparing the element (stored in a temporary list)
with each other element in the list (taking its own occurence into account);
the element is then placed in the final list, and
using the number of occurences of said element, its duplicates
are placed in the consecutive positions before its own in the final list."""
final_lst = []
for num in range(len(lst)):
final_lst.append(0)
for i in range(len(lst)):
store_lst, count, counter = [lst[i]], 0, lst.count(lst[i])
for j in range(len(lst)):
if less_than(lst[j], store_lst[0]):
count = count + 1
else:
count = count
if counter > 1:
for k in range(counter):
final_lst[(count-1) - k] = store_lst[0]
else:
final_lst[count-1] = store_lst[0]
store_lst.pop(0)
return final_lst
#RADIX SORT (for three significant figures)
lst2 = [randint(100,999) for number in range(10)]
def radix_sort(lst):
lst3 = [str(x) for x in lst]
temp = merge_sort([x[2]+x[1]+x[0] for x in lst3])
temp1 = merge_sort([x[1]+x[0]+x[2] for x in temp])
temp2 = merge_sort([x[2]+x[0]+x[1] for x in temp1])
final_lst = [int(x) for x in temp2]
return final_lst
#BUCKET SORT (up to 30)
def bucket_sort(lst):
bucket, bucket1, bucket2 = [], [], [] #The three empty buckets
#Populating the buckets with the list elements
for i in range(len(lst)):
if lst[i] in range(11):
bucket.append(lst[i])
elif lst[i] in range(21):
bucket1.append(lst[i])
elif lst[i] in range(31):
bucket2.append(lst[i])
#Prints the buckets and their contents
print "Bucket:",bucket
print "Bucket1:",bucket1
print "Bucket2:",bucket2
#The actual sorting
bucket.sort()
bucket1.sort()
bucket2.sort()
final_lst = bucket + bucket1 + bucket2
print "Sorted list:",final_lst
"""Below is a function that performs heap-sort on a list."""
import heapq
def heap_sort(lst):
heap = []
for i in lst:
heapq.heappush(heap, i) #Pushes an element into the heap
#Pops an element from the sorted heap
return [heapq.heappop(heap) for i in range(len(heap))]
