Thread Subject:

Sorting Arrays

Hi everyone,
my problem is I basically need to sort arrays without using the sort function. I decided I should use insertion sort method. Here is the code I have come up with so far:


function new=insertionsort(orig)
i=1;
sz=length(orig);
while i <=sz
new=insert(new,orig(i,1));
i=i+1;
end

function orig=insert(orig,v)
i=1;
sz=length(orig);
done=false;
while i<=sz
if lt(v,orig(i,1))
done=true;
orig=[orig(1:i-1);v;orig(i:end)];
break;
end
i=i+1
end
if~done
orig(sz+1,1)=v;
end


I understand that I need to basically have two arrays, the original one that I use min to find the minimum value and move it to the new array. The problem is that I'm not sure how to do this. Any guidance or assistance would be greatly appreciated.

matlabn00b <kkemmerich@hotmail.com> wrote in message <1998266770.62444.1292434700329.JavaMail.root@gallium.mathforum.org>...
> Hi everyone,
> my problem is I basically need to sort arrays without using the sort function. I decided I should use insertion sort method. Here is the code I have come up with so far:
>
>
> function new=insertionsort(orig)
> i=1;
> sz=length(orig);
> while i <=sz
> new=insert(new,orig(i,1));
> i=i+1;
> end
>
> function orig=insert(orig,v)
> i=1;
> sz=length(orig);
> done=false;
> while i<=sz
> if lt(v,orig(i,1))
> done=true;
> orig=[orig(1:i-1);v;orig(i:end)];
> break;
> end
> i=i+1
> end
> if~done
> orig(sz+1,1)=v;
> end
>
>
> I understand that I need to basically have two arrays, the original one that I use min to find the minimum value and move it to the new array. The problem is that I'm not sure how to do this. Any guidance or assistance would be greatly appreciated.

Seems like an awful lot of extra work to me.
You know the sizes of the two matrices so you should use for-loop rather than a while loop. Then extract the minimum value one at a time.

%%%
A = rand(1,10);
B = zeros(size(A));
for ii = 1:length(B)
    [B(ii) idx] = min(A);
    A(idx) = [];
end
issorted(B)
%SCd
%%%

 
> %%%
> A = rand(1,10);
> B = zeros(size(A));
> for ii = 1:length(B)
> [B(ii) idx] = min(A);
> A(idx) = [];
> end
> issorted(B)
> %SCd
> %%%

And for speed, instead of removing the minimum element, set it to the max.
A = rand(1,1000);
B = zeros(size(A));
mx = max(A);
for ii = 1:length(B)
    [B(ii) idx] = min(A);
    A(idx) = mx;
end
issorted(B)

I'm sorry, I forgot to mention that the code is supposed to work for any length vector. I don't understand why you set b to be zeros. Also I have never come across the term "idx" in Matlab and doing a quick google search didn't tell me either. Thanks for the quick response!

matlabn00b <kkemmerich@hotmail.com> wrote in message <70596055.63024.1292441166858.JavaMail.root@gallium.mathforum.org>...
> I'm sorry, I forgot to mention that the code is supposed to work for any length vector. I don't understand why you set b to be zeros. Also I have never come across the term "idx" in Matlab and doing a quick google search didn't tell me either. Thanks for the quick response!

It would work for any length vector. I chose 10 because I wanted to make it clear and easy for you to see what was going on. Try it with 1000 if you wish. In fact with a little index manipulation you could get it to work for matrices along any dimension etc. It's your job to turn it into a function and make it usable for you needs.

I preallocated B with zeros for speed. You don't have to do this if you don't wish but it's good programming practice and as n gets big it will make a significant timing difference.

idx is a variable name I created, and you should be able to ascertain, it stands for index. If you type:
doc min
into the MATLAB command window, you'll see what the second output from min is and how it relates to the problem at hand.

If you type idx into the search for this newsgroup you'll most likely receive thousands of hits since it's a common variable name for that use.

The term _idx_ in Sean's code is a generic variable name, kinda like the term _done_ and _new_ in "your" code.

matlabn00b wrote:
> I'm sorry, I forgot to mention that the code is supposed to work for
> any length vector. I don't understand why you set b to be zeros.
> Also I have never come across the term "idx" in Matlab and doing a
> quick google search didn't tell me either. Thanks for the quick
> response!

Read the code along with...

doc size
doc length
doc min % Nota bene optional output value for the idx mystery

--

Thank you guys so much for the help. If I wanted to input two arrays of equal length and sort it by the first array using the previous method and keep the "pairs" the same how would that work? Any hints or help? Thanks again.
EX:
array1=[4,2,6,1,3] %orig array before sort
array2=[2,4,7,1,5] %the "paired" array
newarray1=[1,2,3,4,6] %orig array just sorted
newarray2=[1,4,5,2,7] %second array sorted according to
%the first array

If you really wrote the code shown in your first post this second question should be a piece of cake.