1
$\begingroup$

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))
$\endgroup$

closed as off-topic by D.W. Sep 14 '15 at 6:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – D.W.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 14 '15 at 6:29
1
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ That I knew. But can it be fixed without taking pivot to the end of the array. $\endgroup$ – Atinesh Sep 13 '15 at 11:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.