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