let consider following pseudo code
quickselect(a, k) let r chosen uniformly @ random in range 1 length(a) let pivot = a[r] let a1, a2 new arrays # split pile a1 of small elements , a2 of big elements = 1 n if a[i] < pivot append a[i] a1 else if a[i] > pivot append a[i] a2 else # nothing end if k <= length(a1): # it's in pile of small elements return quickselect(a1, k) else if k > length(a) - length(a2) # it's in pile of big elements return quickselect(a2, k - (length(a) - length(a2)) else # it's equal pivot return pivot i have wrote following code in matlab
function []=quickselect(a,k); % a-unsorted array %k-we want return kth largest element % let r chosen uniformly @ random in range 1 length(a) i=1; %initialize index j=1; %initialize index n=length(a);%length of array r=floor(1+(n-1)*rand);%random index pivot=a(r); % choose pivot a(r); a1=zeros(1,n); %create additional arrays a2=zeros(1,n);%create additional arrays m=1:n if a(m)<k a1(i)=a(m); i=i+1; else if a(m)>k a2(j)=a(m); j=j+1; end end end if k <= numel(a1) return quickselect(a1,k); else if k > (length(a) - length(a2)) return quickselect(a2, k - (length(a) - length(a2))); else return pivot; end end end >> a=[2 1 4 3 6 5 7 9 8 10 11 13 21 12]; >> quickselect(a,3) error: file: quickselect.m line: 23 column: 10 unexpected matlab expression. i dont understand reason of error, can't use recursive property in matlab? in advance
okay, here's what's wrong code. i've commented replacing pivot k, after looking @ code more closely found few more errors. @anderbiguri identified couple of problems, , i'll mention here completeness.
function []=quickselect(a,k); as ander mentioned, need return value. i'm going directly use pivot. , function declarations don't need ; after them. you're creating blank first line.
function pivot = quickselect(a,k) you had me confused second comments:
% a-unsorted array %k-we want return kth largest element % let r chosen uniformly @ random in range 1 length(a) the pseudocode gave finds kth smallest element. in list [1, 2, 3, 4, 5], 1 smallest element, 2 second-smallest element, , 5 fifth smallest-element.
i=1; %initialize index j=1; %initialize index n=length(a);%length of array r=floor(1+(n-1)*rand);%random index i don't know why you're not using randi here. not wrong way you're doing it, it's clearer, more concise randi.
r=randi(n); % random index note % create additional arrays portion here:
pivot=a(r); % choose pivot a(r); a1=zeros(1,n); % create additional arrays a2=zeros(1,n); % create additional arrays these arrays created same size a , have same size a. addressed ander in comment , become important later.
now for loop:
for m=1:n if a(m)<k your pseudocode says:
if a[i] < pivot pivot value of element chosen pivot , you're trying split a 2 lists: 1 elements less pivot, , elements greater pivot. k index of element value you're looking for. pseudocode correctly uses pivot, code should be:
if a(m)<pivot the same thing goes a(m)>k. should a(m)>pivot. also, in matlab, keyword elseif, no space. i'm deviating bit method of commenting on individual lines occur, wanted leave next section uninterrupted point out else.
a1(i)=a(m); i=i+1; else if a(m)>k a2(j)=a(m); j=j+1; end end end see first end? end? it's better if @ whole code, last end ends for loop. second-to-last end ends if-elsif. first end wrong , should removed. actually, , i'm surprised ander didn't mention this, if had indented code never have created bug. in fact, entire code should re-indented consistently reason readability. for loop section should this:
m=1:n if a(m)<pivot a1(i)=a(m); i=i+1; elseif a(m)>pivot a2(j)=a(m); j=j+1; end end now it's quite obvious blocks ends go , how many need.
the next line in code is:
if k <= numel(a1) this bug referred above that's mentioned in ander's comment. numel(a1) equal numel(a), because that's way created array. therefore, k always less or equal size of input array. (well, should be, there's no explicit check in pseudocode or code, oh well.)
so number of elements added a1? well, go for loop using i index of next element added a1 , j index of next element added a2. means valid length of a1 i-1 , valid length of a2 j-1. if statement should be:
if k <= (i-1) next have:
return quickselect(a1,k); ander biguri mentioned one. matlab not return values way; set value of return variable defined in function declaration. used pivot, take value returned our recursive call quickselect , assign our copy of pivot. when function ends, value of variable automatically becomes return value.
now parameters you're passing recursive call. i've said numel(a1) == numel(a). if recursively call quickselect on a1, you're not reducing size of array. want pass valid portion of a1 , since know has i-1 valid elements, can take first i-1 elements, i.e. a1(1:i-1).
the correct line is:
pivot = quickselect(a1(1:i-1),k); now run length problem again, , you've switched using numel using length. not wrong, far goes, bad style.
else if k > (length(a) - length(a2)) return quickselect(a2, k - (length(a) - length(a2))); this zero. length of a minus length of same length a zero. valid length of a2 j-1. also, know size of a, it's n way there @ beginning. corrected lines:
elseif k > (n - (j-1)) pivot = quickselect(a2(1:j-1), k - (n - (j-1))); and come end of our code:
else return pivot; end end end as mentioned, return doesn't set return value, returns function. since we're @ end of function anyway, there's no need return. once again, proper indentation show there end here well. need 1 if-elseif block, , 1 end function itself, third 1 extraneous.
if make these changes have working quickselect function.
Comments
Post a Comment