Finding the kth smallest element of an array using DAC I'm trying to find the $k^{th}$ smallest element of an array by using Randomized Quicksort, But below code giving erroneous result can anybody help.

from random import randint

lst=[1,3,5,2,4,6]
k=6
n=6

def swap(i,j):
    t=lst[i]
    lst[i]=lst[j]
    lst[j]=t

def rand_partition(p,q):
    # i is the pivot position    
    i=randint(p,q)
    while(p&lt;q):
        if(lst[p]&gt;lst[i]):
            swap(p,p+1)
            p+=1
        else:
            p+=1

    swap(p,q)
    return q

def select(p,q,k):
    r = rand_partition(p,q)
    t = r-p+1

    if(k==t):
        return lst[r]
    elif(k&lt;t):
        return select(p,r-1,k)
    else:
        return select(r+1,q,k-t)

res=select(0,n-1,k)

print('%dth Smallest Element = %d' %(k,res))
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)