Python RSS Python RSS

Sorting in Python

Thread Solved
Reply

•
•
Join Date: Aug 2005
Posts: 148
Reputation: Micko is on a distinguished road 
Solved Threads: 6
Micko Micko is offline Offline
Junior Poster

Sorting in Python

 
0
  #1
Nov 27th, 2005
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:
Python Syntax (Toggle Plain Text) 
  1. struct node
  2. {
  3.     int data;
  4.     struct node * link;
  5. };
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:
Python Syntax (Toggle Plain Text) 
  1. import random #modul random used for generating random numbers
  2.  
  3. N = 100 #defining number of elements
  4. lista = [] #defining list of elements
  5.  
  6. for i in range ( 0, N ) : #popuna liste slucajnim brojevima
  7.   lista.append ( int ( random.uniform ( 0, 100 ) ) )
  8.  
  9. #sort functions definitions 
  10. #bubble_sort
  11. def bubble_sort ( lista ) :
  12.   swap_test = False
  13.   for i in range ( 0, len ( lista ) - 1 ):
  14.     for j in range ( 0, len ( lista ) - i - 1 ):
  15.       if lista[j] > lista[j + 1] :
  16.         lista[j], lista[j + 1] = lista[j + 1], lista[j] #elegentan way of swap
  17.         swap_test = True
  18.     if swap_test == False:
  19.       break
  20.  
  21. #selection sort
  22. def selection_sort ( lista ):
  23.   for i in range ( 0, len ( lista ) ):
  24.     min = i
  25.     for j in range ( i + 1, len ( lista ) ):
  26.       if lista[j] < lista[min] :
  27.         min = j
  28.     lista[i], lista[min] = lista[min], lista[i]
  29.  
  30. #insertion sort
  31. def insertion_sort ( lista ):
  32.   for i in range ( 1, len ( lista ) ):
  33.     save = lista[i]
  34.     j = i
  35.     while ( j > 0 and lista [j - 1] > save ):
  36.       lista[j] = lista[j - 1];
  37.       j -= 1
  38.     lista[j] = save 
  39.  
  40. #quick sort
  41. def quick_sort ( lista ):
  42.   quick_sort_r ( lista, 0, len ( lista ) - 1 )
  43. #end quick_sort
  44.  
  45. #quick_sort_r, rekurzivna funkcija  
  46. def quick_sort_r ( lista , first, last ):
  47.   if last > first :
  48.     pivot = partition ( lista, first, last )
  49.     quick_sort_r ( lista, first, pivot - 1 )
  50.     quick_sort_r ( lista, pivot + 1, last )
  51. #end quick_sort_r
  52.  
  53. #funkcija partition
  54. def partition ( lista, first, last ):
  55.   #prvo ide median of three biranje pocetnog pivota
  56.   sred = ( first + last ) / 2
  57.   if lista[first] > lista [sred] :
  58.     lista[first], lista [sred] = lista [sred], lista[first]
  59.   if lista[first] > lista [last] :
  60.     lista[first], lista[last] = lista[last], lista[first]
  61.   if lista[sred] > lista[last] :
  62.     lista[sred], lista[last] = lista[last], lista[sred]   
  63.   lista [sred], lista [first] = lista[first], lista[sred]
  64.  
  65.   pivot = first
  66.   i = first + 1
  67.   j = last
  68.  
  69.   while ( True ):
  70.     while ( i <= last and lista[i] <= lista [pivot] ):
  71.       i += 1
  72.     while ( j >= first and lista[j] > lista[pivot] ):
  73.       j -= 1
  74.     if i >= j :
  75.       break
  76.     else:
  77.       lista[i], lista[j] = lista[j], lista[i]  
  78.   lista[j], lista[pivot] = lista[pivot], lista[j]
  79.   return j
  80. #end partition
  81.  
  82. #heap sort
  83. def heap_sort ( lista ):
  84.   first = 0;
  85.   last = len ( lista ) - 1;
  86.   create_heap ( lista, first, last )
  87.   for i in range ( last, first, -1 ):
  88.     lista[i], lista[first] = lista[first], lista[i]
  89.     establish_heap_property ( lista, first, i - 1 )
  90. #kraj f-je heap_sort
  91.  
  92. #create heap
  93. def create_heap ( lista, first, last ):
  94.   i = last / 2;
  95.   while ( i >= first ):
  96.     establish_heap_property ( lista, i, last )
  97.     i -= 1
  98. #end create_heap
  99.  
  100. #establish heap property
  101. def establish_heap_property ( lista, first, last ):
  102.   while 2 * first + 1 <= last :
  103.     k = 2 * first + 1;
  104.     if k < last and lista[k] < lista[k + 1] :
  105.       k += 1
  106.     if lista[first] >= lista[k] :
  107.       break
  108.     lista[first], lista[k] = lista[k], lista[first]
  109.     first = k
  110. #end establish_heap_property
  111.  
  112. #merge sort
  113. def merge_sort ( lista ):
  114.   merge_sort_r ( lista, 0, len ( lista ) -1 )
  115. #end merge_sort_r
  116.  
  117. #merge sort rekurzivna f-ja
  118. def merge_sort_r ( lista, first, last ):
  119.   if first < last:
  120.     sred = ( first + last ) / 2
  121.     merge_sort_r ( lista, first, sred )
  122.     merge_sort_r ( lista, sred + 1, last )
  123.     merge ( lista, first, last, sred )
  124. #end merge_sort_r
  125.  
  126. #merge
  127. def merge ( lista, first, last, sred ):
  128.   helper_list = []
  129.   i = first
  130.   j = sred + 1
  131.   while ( i <= sred and j <= last ):
  132.     if lista [i] <= lista [j] :
  133.       helper_list.append ( lista[i] )
  134.       i += 1
  135.     else:
  136.       helper_list.append ( lista [j] )
  137.       j += 1
  138.   while ( i <= sred ):
  139.     helper_list.append ( lista[i] )
  140.     i +=1
  141.   while ( j <= last ):
  142.     helper_list.append ( lista[j] )
  143.     j += 1
  144.  
  145.   for k in range ( 0, last - first + 1):
  146.     lista[first + k] = helper_list [k]
  147. #end merge
  148.  
  149. #test if script is executed or module is imported
  150. if __name__ == "__main__" :  
  151.   merge_sort ( lista )
  152.   print lista
  153.   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
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2004
Posts: 3,862
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 870
Moderator
vegaseat's Avatar
vegaseat vegaseat is offline Offline
DaniWeb's Hypocrite

Re: Sorting in Python

 
0
  #2
Nov 27th, 2005
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.
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2004
Posts: 7,541
Reputation: Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute Narue has a reputation beyond repute 
Solved Threads: 704
Team Colleague
Narue's Avatar
Narue Narue is offline Offline
Code Goddess

Re: Sorting in Python

 
0
  #3
Nov 27th, 2005
>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:
Python Syntax (Toggle Plain Text) 
  1. class node:
  2.   def __init__ ( self, data = None, link = None ):
  3.     self.data = data
  4.     self.link = link
I'm here to prove you wrong.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2004
Posts: 3,862
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 870
Moderator
vegaseat's Avatar
vegaseat vegaseat is offline Offline
DaniWeb's Hypocrite

Re: Sorting in Python

 
0
  #4
Nov 27th, 2005
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.
python Syntax (Toggle Plain Text) 
  1. # timing Micko's 6 sorting algorithms 11/27/2005
  2.  
  3. import random  # for generating random numbers
  4. import time    # for timing each sort function with time.clock()
  5.  
  6. N = 1000     # number of elements
  7. lista = []   # list of comparable elements
  8.  
  9. for i in range ( 0, N ) :
  10.   lista.append ( int ( random.uniform ( 0, N ) ) )
  11.  
  12. def print_timing(func):
  13.   def wrapper(*arg):
  14.     t1 = time.clock()
  15.     res = func(*arg)
  16.     t2 = time.clock()
  17.     print '%s took %0.3fms.' % (func.func_name, (t2-t1)*1000.)
  18.     return res
  19.   return wrapper
  20.  
  21. # declare the @ decorator just above each sort function, invokes print_timing()
  22. @print_timing
  23. def bubble_sort( lista ):
  24.   swap_test = False
  25.   for i in range ( 0, len ( lista ) - 1 ):
  26.     for j in range ( 0, len ( lista ) - i - 1 ):
  27.       if lista[j] > lista[j + 1] :
  28.         lista[j], lista[j + 1] = lista[j + 1], lista[j] # swap
  29.         swap_test = True
  30.     if swap_test == False:
  31.       break
  32.  
  33. # selection sort
  34. @print_timing
  35. def selection_sort( lista ):
  36.   for i in range ( 0, len ( lista ) ):
  37.     min = i
  38.     for j in range ( i + 1, len ( lista ) ):
  39.       if lista[j] < lista[min] :
  40.         min = j
  41.     lista[i], lista[min] = lista[min], lista[i]
  42.  
  43. # insertion sort
  44. @print_timing
  45. def insertion_sort( lista ):
  46.   for i in range ( 1, len ( lista ) ):
  47.     save = lista[i]
  48.     j = i
  49.     while ( j > 0 and lista [j - 1] > save ):
  50.       lista[j] = lista[j - 1];
  51.       j -= 1
  52.     lista[j] = save
  53.  
  54. # quick sort
  55. @print_timing
  56. def quick_sort( lista ):
  57.   quick_sort_r( lista, 0, len ( lista ) - 1 )
  58. # end quick_sort
  59.  
  60. # quick_sort_r, recursive (used by quick_sort)
  61. def quick_sort_r( lista , first, last ):
  62.   if last > first :
  63.     pivot = partition ( lista, first, last )
  64.     quick_sort_r ( lista, first, pivot - 1 )
  65.     quick_sort_r ( lista, pivot + 1, last )
  66. # end quick_sort_r
  67.  
  68. # partition (used by quick_sort_r)
  69. def partition( lista, first, last ):
  70.   sred = ( first + last ) / 2
  71.   if lista[first] > lista [sred] :
  72.     lista[first], lista [sred] = lista [sred], lista[first]
  73.   if lista[first] > lista [last] :
  74.     lista[first], lista[last] = lista[last], lista[first]
  75.   if lista[sred] > lista[last] :
  76.     lista[sred], lista[last] = lista[last], lista[sred]
  77.   lista [sred], lista [first] = lista[first], lista[sred]
  78.  
  79.   pivot = first
  80.   i = first + 1
  81.   j = last
  82.  
  83.   while ( True ):
  84.     while ( i <= last and lista[i] <= lista [pivot] ):
  85.       i += 1
  86.     while ( j >= first and lista[j] > lista[pivot] ):
  87.       j -= 1
  88.     if i >= j :
  89.       break
  90.     else:
  91.       lista[i], lista[j] = lista[j], lista[i]
  92.   lista[j], lista[pivot] = lista[pivot], lista[j]
  93.   return j
  94. # end partition
  95.  
  96. # heap sort
  97. @print_timing
  98. def heap_sort( lista ):
  99.   first = 0;
  100.   last = len ( lista ) - 1;
  101.   create_heap ( lista, first, last )
  102.   for i in range ( last, first, -1 ):
  103.     lista[i], lista[first] = lista[first], lista[i]
  104.     establish_heap_property ( lista, first, i - 1 )
  105. # end heap_sort
  106.  
  107. # create heap (used by heap_sort)
  108. def create_heap( lista, first, last ):
  109.   i = last / 2;
  110.   while ( i >= first ):
  111.     establish_heap_property ( lista, i, last )
  112.     i -= 1
  113. # end create_heap
  114.  
  115. # establish heap property (used by create_heap)
  116. def establish_heap_property ( lista, first, last ):
  117.   while 2 * first + 1 <= last :
  118.     k = 2 * first + 1;
  119.     if k < last and lista[k] < lista[k + 1] :
  120.       k += 1
  121.     if lista[first] >= lista[k] :
  122.       break
  123.     lista[first], lista[k] = lista[k], lista[first]
  124.     first = k
  125. # end establish_heap_property
  126.  
  127. # merge sort
  128. @print_timing
  129. def merge_sort( lista ):
  130.   merge_sort_r ( lista, 0, len ( lista ) -1 )
  131. # end merge_sort_r
  132.  
  133. # merge sort recursive (used by merge_sort)
  134. def merge_sort_r( lista, first, last ):
  135.   if first < last:
  136.     sred = ( first + last ) / 2
  137.     merge_sort_r ( lista, first, sred )
  138.     merge_sort_r ( lista, sred + 1, last )
  139.     merge ( lista, first, last, sred )
  140. # end merge_sort_r
  141.  
  142. # merge (used by merge_sort_r)
  143. def merge( lista, first, last, sred ):
  144.   helper_list = []
  145.   i = first
  146.   j = sred + 1
  147.   while ( i <= sred and j <= last ):
  148.     if lista [i] <= lista [j] :
  149.       helper_list.append ( lista[i] )
  150.       i += 1
  151.     else:
  152.       helper_list.append ( lista [j] )
  153.       j += 1
  154.   while ( i <= sred ):
  155.     helper_list.append ( lista[i] )
  156.     i +=1
  157.   while ( j <= last ):
  158.     helper_list.append ( lista[j] )
  159.     j += 1
  160.  
  161.   for k in range ( 0, last - first + 1):
  162.     lista[first + k] = helper_list [k]
  163. # end merge
  164.  
  165.  
  166. # run test if script is executed
  167. if __name__ == "__main__" :
  168.   print "timing the 6 sorting algorithms with a list of 1000 integers:"
  169.   bubble_sort( lista )
  170.   heap_sort( lista )
  171.   insertion_sort( lista )
  172.   merge_sort( lista )
  173.   quick_sort( lista )
  174.   selection_sort( lista )
  175.  
  176.   raw_input( "Press Enter to continue..." )
  177.  
  178. """
  179. typical results:
  180. bubble_sort took 426.132ms.
  181. heap_sort took 28.322ms.
  182. insertion_sort took 1.091ms.
  183. merge_sort took 34.000ms.
  184. quick_sort took 6.494ms.
  185. selection_sort took 177.234ms.
  186. """
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.
Last edited by vegaseat; Aug 15th, 2008 at 7:21 pm. Reason: replaced non functioning php code tags
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 148
Reputation: Micko is on a distinguished road 
Solved Threads: 6
Micko Micko is offline Offline
Junior Poster

Re: Sorting in Python

 
0
  #5
Nov 27th, 2005
•
•
•
•
Originally Posted by vegaseat
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
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2006
Posts: 1
Reputation: ddc is an unknown quantity at this point 
Solved Threads: 1
ddc ddc is offline Offline
Newbie Poster

Re: Sorting in Python

 
0
  #6
Mar 27th, 2006
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2004
Posts: 3,862
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 870
Moderator
vegaseat's Avatar
vegaseat vegaseat is offline Offline
DaniWeb's Hypocrite

Re: Sorting in Python

 
0
  #7
Mar 27th, 2006
•
•
•
•
Originally Posted by 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.
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
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 1,514
Reputation: Ene Uran has a spectacular aura about Ene Uran has a spectacular aura about 
Solved Threads: 168
Ene Uran's Avatar
Ene Uran Ene Uran is offline Offline
Posting Virtuoso

Re: Sorting in Python

 
0
  #8
Mar 29th, 2006
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!
drink her pretty
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Python Forum
Thread Tools Search this Thread



accessdenied advanced aliased anydbm app beginner bits calling casino cipher clear command conversion convert coordinates corners count csv cturtle cursor curves def definedlines development dynamic dynamically event events excel feet file float format frange function google handling homework i/o iframe input jaunty keyboard keycontrol lapse line linux list lists loan loop matching mouse multiple newb number numbers obexftp output parsing path prime programming projects py py2exe pygame pymailer pyopengl python random rational raw_input recursion recursive return searchingfile signal string strings tails text time tlapse tooltip tuple type ubuntu unicode url urllib urllib2 valueerror variable voip web-scrape whileloop word wxpython xlwt
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC