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

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 5 Years Ago by -ordi-: n/a

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.

This question has already been answered. Start a new discussion instead.