def sort(l, x)
if len(l) <= 1: ### if my list is smaller than 1, simply return l
return l
else:

### Here is the problem i don't know how to solve - how to find smallest element within a list using recursion? I've tried to call another function in which i wanted to find smallest element...long story short - it didn't work ###

The easiest solution is to use min(), which finds the object in a list that sorts lowest. You can then use remove() on the original list and call selsort() on the remaining part of the original, which can be added to the sorted list with the extend() method.

The min() function finds the smallest element of a list. If you type min([4, 3, 5, 7, 11, 9, 22]) , at the Python interactive prompt, it returns 3. So you can use it to find the smallest element, as you are saying.

With the selection sort, the idea is not to compare the smallest value with the other values - you already know it is the smallest - but to replace the lowest element with the smallest, then the next lowest with the next smallest, and so on until you have a sorted list. In this case, it is easiest to make a new list rather than moving the elements around, because lists are so inexpensive in Python.

def select(number,a)
pivot=len(number)//2 # the element at position len(lst)//2
smallerlst=number[0] # all elements of number smaller than pivot
largerlst=[] #all elements of number larger than
count=pivot+1 # the number of occurances of pivot in number
m # size of smallerlst
if len(number)==0:
return
for x in number:
if x< number[pivot]:
smallerlst=smallerlst+x
else:
return largerlst
m=len(smallerlst)
if k>= m and k <m+count:
return pivot
elif m>k:
return k_select(smallerlst,k)
else:
return k_select(largerlst,k-m-count)

def select(number,a)
pivot=len(number)//2 # the element at position len(lst)//2
smallerlst=number[0] # all elements of number smaller than pivot
largerlst=[] #all elements of number larger than
count=pivot+1 # the number of occurances of pivot in number
m # size of smallerlst
if len(number)==0:
return
for x in number:
if x< number[pivot]:
smallerlst=smallerlst+x
else:
return largerlst
m=len(smallerlst)
if k>= m and k <m+count:
return pivot
elif m>k:
return k_select(smallerlst,k)
else:
return k_select(largerlst,k-m-count)

Notice that because of recursion limit of Python, you can sort only very short lists with recursive algorihm. Therefore iterative version would be lot better (and best would be the built in sort).

import random
def it_selsort(seq):
result = []
while seq:
min_in_seq = min(seq)
seq.remove(min_in_seq)
result.append(min_in_seq)
return result
tosort= range(1000)
random.shuffle(tosort)
print tosort
print it_selsort(tosort)