Finding the kth smallest element of an array using DAC
The problem is in your rand_partition(p,q) function.

I made some changes with comments.

def rand_partition(p,q):   
    i=randint(p,q)               # get a random index between p and q 
    swap(i,q)                    # move the pivot element to the end 
                                 # after now, do the same as normal partitioning 
    pivot=lst[q]                 # save pivot
    s=p-1
    j=p
    while(j &lt; q):                #keep invariants (this would be better with a for loop):
        if(lst[j] &lt;= pivot):     # lst[p...s] &lt;= pivot,
            s+=1                 # lst[s+1...j-1] &gt; pivot
            swap(s,j)        
        j+=1

    swap(s+1,q)                  # put the pivot in the correct place
    return s+1


Also, you can set a base case for select(p,q,k) (although this is not critical):

def select(p,q,k):
    if (p==q):
        return lst[p]
    #...


For more info: Introduction to Algorithms (Cormen, Leiserson, Rivest &amp; Stein)