# Finding the kth smallest element of an array using DAC [closed]

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<q):
if(lst[p]>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<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))

• Reviewing your Python code for bugs is outside the scope of this site. This site is for conceptual questions about computer science, not about code review or programming/coding questions.
– D.W.
Commented Sep 14, 2015 at 6:29

The problem is in your rand_partition(p,q) function.

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 < q):                #keep invariants (this would be better with a for loop):
if(lst[j] <= pivot):     # lst[p...s] <= pivot,
s+=1                 # lst[s+1...j-1] > 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]
#...

• That I knew. But can it be fixed without taking pivot to the end of the array. Commented Sep 13, 2015 at 11:04