Sorting in Python

[Micko]

Hello people of Python community,
I'm back with (so far) strong will to learn Python, just like you.
I remember once, Narue told me that good way to learn different prog. languages
is to concetrate on algorithms and data structures and their implementation in
language of choice. That way, she said, one can learn both algorithms and data structrues
which are language independent but also at the same time can learn the programming language.
I tried to follow her advice and by reading her tutorials, I manage to implement most of sorting
algorithms in C. Also, I didn't have tough time with BST and linked lists. And yesterday I
decided to implement a couple algorithms and data structures in Python. I manage to implement
sorting algorithms well. here is what I have done. I think someone will find it usefull.
I know that this can be don in more elegant way using some Python trait's but I tried to avoid
thing that are Python's specific because of the following reasons:

1. I don't know nearly enough Python as I'd like to
2. These implementations are very similar to those in C and can be easily rewritten in other
programming language.

Of course, problem is how to implement, say a linked list in Python, since it doesn't have
pointers, or even static types so how this could be implemented is pretty unclear to me:

struct node
{
    int data;
    struct node * link;
};

I know, because of very powerfull data structures that exists like built in types this
is not neccessary but still...
Anyway I want to share my sort implementations:

import random #modul random used for generating random numbers

N = 100 #defining number of elements
lista = [] #defining list of elements

for i in range ( 0, N ) : #popuna liste slucajnim brojevima
  lista.append ( int ( random.uniform ( 0, 100 ) ) )

#sort functions definitions 
#bubble_sort
def bubble_sort ( lista ) :
  swap_test = False
  for i in range ( 0, len ( lista ) - 1 ):
    for j in range ( 0, len ( lista ) - i - 1 ):
      if lista[j] > lista[j + 1] :
        lista[j], lista[j + 1] = lista[j + 1], lista[j] #elegentan way of swap
        swap_test = True
    if swap_test == False:
      break

#selection sort
def selection_sort ( lista ):
  for i in range ( 0, len ( lista ) ):
    min = i
    for j in range ( i + 1, len ( lista ) ):
      if lista[j] < lista[min] :
        min = j
    lista[i], lista[min] = lista[min], lista[i]
      
#insertion sort
def insertion_sort ( lista ):
  for i in range ( 1, len ( lista ) ):
    save = lista[i]
    j = i
    while ( j > 0 and lista [j - 1] > save ):
      lista[j] = lista[j - 1];
      j -= 1
    lista[j] = save 
  
#quick sort
def quick_sort ( lista ):
  quick_sort_r ( lista, 0, len ( lista ) - 1 )
#end quick_sort

#quick_sort_r, rekurzivna funkcija  
def quick_sort_r ( lista , first, last ):
  if last > first :
    pivot = partition ( lista, first, last )
    quick_sort_r ( lista, first, pivot - 1 )
    quick_sort_r ( lista, pivot + 1, last )
#end quick_sort_r

#funkcija partition
def partition ( lista, first, last ):
  #prvo ide median of three biranje pocetnog pivota
  sred = ( first + last ) / 2
  if lista[first] > lista [sred] :
    lista[first], lista [sred] = lista [sred], lista[first]
  if lista[first] > lista [last] :
    lista[first], lista[last] = lista[last], lista[first]
  if lista[sred] > lista[last] :
    lista[sred], lista[last] = lista[last], lista[sred]   
  lista [sred], lista [first] = lista[first], lista[sred]
  
  pivot = first
  i = first + 1
  j = last
  
  while ( True ):
    while ( i <= last and lista[i] <= lista [pivot] ):
      i += 1
    while ( j >= first and lista[j] > lista[pivot] ):
      j -= 1
    if i >= j :
      break
    else:
      lista[i], lista[j] = lista[j], lista[i]  
  lista[j], lista[pivot] = lista[pivot], lista[j]
  return j
#end partition

#heap sort
def heap_sort ( lista ):
  first = 0;
  last = len ( lista ) - 1;
  create_heap ( lista, first, last )
  for i in range ( last, first, -1 ):
    lista[i], lista[first] = lista[first], lista[i]
    establish_heap_property ( lista, first, i - 1 )
#kraj f-je heap_sort

#create heap
def create_heap ( lista, first, last ):
  i = last / 2;
  while ( i >= first ):
    establish_heap_property ( lista, i, last )
    i -= 1
#end create_heap

#establish heap property
def establish_heap_property ( lista, first, last ):
  while 2 * first + 1 <= last :
    k = 2 * first + 1;
    if k < last and lista[k] < lista[k + 1] :
      k += 1
    if lista[first] >= lista[k] :
      break
    lista[first], lista[k] = lista[k], lista[first]
    first = k
#end establish_heap_property

#merge sort
def merge_sort ( lista ):
  merge_sort_r ( lista, 0, len ( lista ) -1 )
#end merge_sort_r

#merge sort rekurzivna f-ja
def merge_sort_r ( lista, first, last ):
  if first < last:
    sred = ( first + last ) / 2
    merge_sort_r ( lista, first, sred )
    merge_sort_r ( lista, sred + 1, last )
    merge ( lista, first, last, sred )
#end merge_sort_r

#merge
def merge ( lista, first, last, sred ):
  helper_list = []
  i = first
  j = sred + 1
  while ( i <= sred and j <= last ):
    if lista [i] <= lista [j] :
      helper_list.append ( lista[i] )
      i += 1
    else:
      helper_list.append ( lista [j] )
      j += 1
  while ( i <= sred ):
    helper_list.append ( lista[i] )
    i +=1
  while ( j <= last ):
    helper_list.append ( lista[j] )
    j += 1
  
  for k in range ( 0, last - first + 1):
    lista[first + k] = helper_list [k]
#end merge

#test if script is executed or module is imported
if __name__ == "__main__" :  
  merge_sort ( lista )
  print lista
  raw_input ( "Press Enter to continue..." )

I didn't commented or explain code in detail since really valueable and detail explanations
can be found on
www.eternallyconfuzzled.com
and I, with my poor English and programming skills, don't have minimum chance to write somthing good like that.

If you like this code, or find it useful in any way, I'd be happy, if not, sorry because wasting your time
and wasting space on this forum...

Regards,
Micko

[vegaseat]

Looks like you met Narue on the C/C++ forum, she is the best!

Your Python code is great, works well. It would be a fabulous addition to the Python Snippets.

It depends how you look at it, Python variables are all pointers or references to a heap memory location. Take a look at the Python Tutorials here, I have tried to take a closer look at some variables and structures.

[Narue]

>problem is how to implement, say a linked list in Python, since it doesn't have
>pointers, or even static types so how this could be implemented is pretty unclear to me
Python is kind of screwy if you're used to a strongly typed language like C++ (or even C!). To make a node, create a class:

class node:
  def __init__ ( self, data = None, link = None ):
    self.data = data
    self.link = link

[vegaseat]

Didn't I tell you, she is the best!

Well, anyway I took your sorting algorithms and timed them. Increased elements to 1000 to get better times.

# timing Micko's 6 sorting algorithms 11/27/2005

import random  # for generating random numbers
import time    # for timing each sort function with time.clock()

N = 1000     # number of elements
lista = []   # list of comparable elements

for i in range ( 0, N ) :
  lista.append ( int ( random.uniform ( 0, N ) ) )

def print_timing(func):
  def wrapper(*arg):
    t1 = time.clock()
    res = func(*arg)
    t2 = time.clock()
    print '%s took %0.3fms.' % (func.func_name, (t2-t1)*1000.)
    return res
  return wrapper

# declare the @ decorator just above each sort function, invokes print_timing()
@print_timing
def bubble_sort( lista ):
  swap_test = False
  for i in range ( 0, len ( lista ) - 1 ):
    for j in range ( 0, len ( lista ) - i - 1 ):
      if lista[j] > lista[j + 1] :
        lista[j], lista[j + 1] = lista[j + 1], lista[j] # swap
        swap_test = True
    if swap_test == False:
      break

# selection sort
@print_timing
def selection_sort( lista ):
  for i in range ( 0, len ( lista ) ):
    min = i
    for j in range ( i + 1, len ( lista ) ):
      if lista[j] < lista[min] :
        min = j
    lista[i], lista[min] = lista[min], lista[i]
      
# insertion sort
@print_timing
def insertion_sort( lista ):
  for i in range ( 1, len ( lista ) ):
    save = lista[i]
    j = i
    while ( j > 0 and lista [j - 1] > save ):
      lista[j] = lista[j - 1];
      j -= 1
    lista[j] = save
  
# quick sort
@print_timing
def quick_sort( lista ):
  quick_sort_r( lista, 0, len ( lista ) - 1 )
# end quick_sort

# quick_sort_r, recursive (used by quick_sort)
def quick_sort_r( lista , first, last ):
  if last > first :
    pivot = partition ( lista, first, last )
    quick_sort_r ( lista, first, pivot - 1 )
    quick_sort_r ( lista, pivot + 1, last )
# end quick_sort_r

# partition (used by quick_sort_r)
def partition( lista, first, last ):
  sred = ( first + last ) / 2
  if lista[first] > lista [sred] :
    lista[first], lista [sred] = lista [sred], lista[first]
  if lista[first] > lista [last] :
    lista[first], lista[last] = lista[last], lista[first]
  if lista[sred] > lista[last] :
    lista[sred], lista[last] = lista[last], lista[sred]
  lista [sred], lista [first] = lista[first], lista[sred]
  
  pivot = first
  i = first + 1
  j = last
  
  while ( True ):
    while ( i <= last and lista[i] <= lista [pivot] ):
      i += 1
    while ( j >= first and lista[j] > lista[pivot] ):
      j -= 1
    if i >= j :
      break
    else:
      lista[i], lista[j] = lista[j], lista[i]
  lista[j], lista[pivot] = lista[pivot], lista[j]
  return j
# end partition

# heap sort
@print_timing
def heap_sort( lista ):
  first = 0;
  last = len ( lista ) - 1;
  create_heap ( lista, first, last )
  for i in range ( last, first, -1 ):
    lista[i], lista[first] = lista[first], lista[i]
    establish_heap_property ( lista, first, i - 1 )
# end heap_sort

# create heap (used by heap_sort)
def create_heap( lista, first, last ):
  i = last / 2;
  while ( i >= first ):
    establish_heap_property ( lista, i, last )
    i -= 1
# end create_heap

# establish heap property (used by create_heap)
def establish_heap_property ( lista, first, last ):
  while 2 * first + 1 <= last :
    k = 2 * first + 1;
    if k < last and lista[k] < lista[k + 1] :
      k += 1
    if lista[first] >= lista[k] :
      break
    lista[first], lista[k] = lista[k], lista[first]
    first = k
# end establish_heap_property

# merge sort
@print_timing
def merge_sort( lista ):
  merge_sort_r ( lista, 0, len ( lista ) -1 )
# end merge_sort_r

# merge sort recursive (used by merge_sort)
def merge_sort_r( lista, first, last ):
  if first < last:
    sred = ( first + last ) / 2
    merge_sort_r ( lista, first, sred )
    merge_sort_r ( lista, sred + 1, last )
    merge ( lista, first, last, sred )
# end merge_sort_r

# merge (used by merge_sort_r)
def merge( lista, first, last, sred ):
  helper_list = []
  i = first
  j = sred + 1
  while ( i <= sred and j <= last ):
    if lista [i] <= lista [j] :
      helper_list.append ( lista[i] )
      i += 1
    else:
      helper_list.append ( lista [j] )
      j += 1
  while ( i <= sred ):
    helper_list.append ( lista[i] )
    i +=1
  while ( j <= last ):
    helper_list.append ( lista[j] )
    j += 1
  
  for k in range ( 0, last - first + 1):
    lista[first + k] = helper_list [k]
# end merge


# run test if script is executed
if __name__ == "__main__" :
  print "timing the 6 sorting algorithms with a list of 1000 integers:"
  bubble_sort( lista )
  heap_sort( lista )
  insertion_sort( lista )
  merge_sort( lista )
  quick_sort( lista )
  selection_sort( lista )

  raw_input( "Press Enter to continue..." )

"""
typical results:
bubble_sort took 426.132ms.
heap_sort took 28.322ms.
insertion_sort took 1.091ms.
merge_sort took 34.000ms.
quick_sort took 6.494ms.
selection_sort took 177.234ms.
"""

I understand that the Python interpreter gives repeated function calls a time penalty. That makes your recursives look worse than they should. By the way, the Python internal list sort of this particular list takes 0.082ms.

For your information the Python list container does behave like an array, but it may slow external sorting down. You can get true array modules for scientific stuff, it may be interesting to test these out. Google for NumArray.

[Micko]

Your Python code is great, works well. It would be a fabulous addition to the Python Snippets.

I you like add it there if it is OK with Narue, since most of the code in C (as initial idea ) is hers...
Cheers

- Micko

[ddc]

Your "typical results" for timing are typical results for timing a sorted list. Only bubble sort sorts a random list. Try putting listb = list( lista ) before each sort call and then sort listb. This creates a fresh copy of the original unsorted lista. Here are typical results:

timing the 6 sorting algorithms with a list of 1000 integers:
bubble_sort took 269.410ms.
heap_sort took 10.810ms.
insertion_sort took 139.228ms.
merge_sort took 14.764ms.
quick_sort took 7.494ms.
selection_sort took 118.048ms.

Note that insertion and selection sorts are now way slower than heap, merge, and quick --as they should be-- and heap and merge are about the same.

[vegaseat]

Your "typical results" for timing are typical results for timing a sorted list. Only bubble sort sorts a random list. Try putting listb = list( lista ) before each sort call and then sort listb. This creates a fresh copy of the original unsorted lista. Here are typical results:

timing the 6 sorting algorithms with a list of 1000 integers:
bubble_sort took 269.410ms.
heap_sort took 10.810ms.
insertion_sort took 139.228ms.
merge_sort took 14.764ms.
quick_sort took 7.494ms.
selection_sort took 118.048ms.

Note that insertion and selection sorts are now way slower than heap, merge, and quick --as they should be-- and heap and merge are about the same.

Micko and I came to the same conclusion. For the finished version of this, posted about two months ago, see:
http://www.daniweb.com/code/snippet452.html

[Ene Uran]

I am starting to learn Python and have a good crasp of C++ from school. I must say, that I find this thread very interesting information. Thanks all of you who contributed!