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)]

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))]``````
5
Contributors
6
Replies
12
Views
7 Years
Discussion Span
Last Post by jamd200

Better Gnome sort:

``````def gnomesort(seq):
i = 0
while i < len(seq):
if i == 0 or seq[i-1] <= seq[i]:
i += 1
else:
seq[i], seq[i-1] = seq[i-1], seq[i]
i -= 1``````

Edited by -ordi-: n/a

need timsort, merge sort to complete it.

Also Bogosort for luls :P

I would do two variable assignment instead of temp variables needed in other languages. Looks nice code inspite of this point. Irritates me though that there seems not be faster way to split list for quicksort than doing two passes of list with complement conditions.

mmmmmmmmmmmmm not bad. I jus dont see any real life need for this algo. besides There should be a better way than this.
:)

need timsort, merge sort to complete it.

Also Bogosort for luls :P

I'm not skilled enough yet to do timsort, but Bogosort (limited to 10 tries) is below, and it actually sorted a list once.

``````import random

def is_sorted(lst): #Determines if a list is sorted
signal = 0
for i in range(len(lst)-1):
if lst[i] > lst[i+1]:
signal += 1
else:
signal = signal
return signal == 0

def bogosort(lst): #Bogosorts the list
for number in range(10):
random.shuffle(lst)
if is_sorted(lst):
return lst
else:
print "Not sorted."``````

If I used the sort() method for Timsort, I kinda feel like that would be cheating, but the heapsort is not much better since I used the built-in functions. As for the use of this, it isn't necessary for real-life situations (unless you want greater control over the efficiency of the sorts you implement), but this can be an educational tool to teach CS and IT students different sorting algorithms and how they're implemented.