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 ###

l.append(smallest)
return selsort(l[1:])

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 …

## All 8 Replies

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.

I don't get sorry. I am new.
what I am thinking about is to find the smallest element then compare to other elements, but I don't know how to do it.

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.

Here is my code, but it doesn't work. output "[]"

``````def select(number,a)
pivot=len(number)//2 # the element at position len(lst)//2
smallerlst=number # 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)``````

Here is my code, but it doesn't work. output "[]"

``````def select(number,a)
pivot=len(number)//2 # the element at position len(lst)//2
smallerlst=number # 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)``````

OK, I'm confused; you appear to have switched suddenly from selection sort to quicksort. Any particular reason?

Selection sort is considerably simpler to implement. Here's a simple variant of it:

``````def selectionSort(unsorted):
if len(unsorted) <= 1:
return unsorted
else:
sorted = list()
element = min(unsorted)
sorted.append(element)
unsorted.remove(element)
sorted.extend(selectionSort(unsorted))
return sorted``````

Whereas what you're doing now is more like this:

``````def qsort(unsorted):
if len(unsorted) <= 1:
return unsorted

pivotPos = len(unsorted) // 2
pivot = unsorted[pivotPos]
smallerlist = list()
largerlist = list()

unsorted.remove(pivot)

for x in unsorted:
if x <= pivot:
smallerlist.append(x)
else:
largerlist.append(x)

sorted = list()
sorted.extend(qsort(smallerlist))
sorted.append(pivot)
sorted.extend(qsort(largerlist))
return sorted``````

Any particular reason for the switch?

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)``````

My previous iterative sort emptied the original list, so here a version that copies the list first:

``````import random
def it_selsort(seq):
result = []
seq = seq[:]
while seq:
min_in_seq = min(seq)
seq.remove(min_in_seq)
result.append(min_in_seq)
return result

tosort= range(100)+range(10)
random.shuffle(tosort)
print tosort
print it_selsort(tosort)

print tosort``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.