selection sort use recursion

[newbieha]

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:])

[Schol-R-LEA]

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.

[newbieha]

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.

[Schol-R-LEA]

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.

[newbieha]

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

[newbieha]

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

[Schol-R-LEA]

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?

[TrustyTony]

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)

[TrustyTony]

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