Sorting in Python
 

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

Re: Sorting in Python
 

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.

Re: Sorting in Python
 

>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

Re: Sorting in Python
 

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.

Re: Sorting in Python
 

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

Re: Sorting in Python
 

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.

Re: Sorting in Python
 

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

Re: Sorting in Python
 

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!