Speeding up Sort Algorithm by removing ismember

I am trying to make a sorting algorithim, that doesnt use the built in sort function, that sorts 1 vector from smallest to largest then applies the same changes to a second vector.

For example

time =  [ 1  3  2  4  7];
signal= [12 14 11 13 16];

time_sorted =  [ 1  2  3  4  7];
signal_sorted= [12 11 14 13 16];

My code to do this is:

function [time,signal_sorted] = mysortdata(time,signal)

% Makes a copy of time
time1 = time;

%make sure we have more than one element
if numel(time) <= 1
  return
end

%Picking the end of time to be a place where time is split in two
PivotTime = time(end);

% Removes this point from time
time(end) = [];
 
%create 4 arrays:
% LessTime/LessSignal: values in the array less than    the pivot
% MoreTime/MoreSignal: values in the array greater than the pivot
LessTime = time(time <= PivotTime);
MoreTime = time(time >  PivotTime);

LessSignal = time(time <= PivotTime);
MoreSignal = time(time >  PivotTime);

%  input Less and More into this function again 
Less = mysortdata(LessTime,LessSignal);
More = mysortdata(MoreTime,MoreSignal);

%Put time back together again
time = [Less, PivotTime, More];

% Gets the index of time compared to time_sorted
[~,idx] = ismember(time,time1);

% Sorts signal according to this index
signal_sorted = signal(idx);

return
end

I was wondering if anyone would be able to speed this up as the ismember fuction is quite slow.

Thank you

[John D'Errico]

Why do you feel the need to do this? Since it is trivial to use sort to also sort a second vector/array that goes along with your sorted input, this task seems a poor choice to invest your efforts.

And since you actually use a high level tool like ismember, it cannot be that for some reason, sort is not "allowed", as ismember would logically then also be disallowed.

Writing your own basic routines like sort is almost never a good idea. Are you trying to learn basic sorting techniques? If so, then why are you so worried about efficiency?

Anyway, you are then trying to do this using recursive calls to your function. The recursion will probably be quite expensive in itself, as then you cause MATLAB to create multiple instances of your function, all with subtly changing data. This is something I would expect to be not efficient at all, and of course, those constant calls to ismember will add up considerably. I'd even claim that deep recursions are only rarely a good choice of algorithm in MATLAB.

[Bruno Luong]

Use ISMEMBER is cheating since it "sorts" somewhat internally.

[Dan Page]

Can you think of alternativ without ismember?

[Bruno Luong]

Permuting the second array signal exatly the same way like time.

Answer 1

[Bruno Luong]

time =  [ 1  3  2  4  7];
signal= [12 14 11 13 16];
[time, signal] = mysortdata(time, signal)

%%
function [time, signal] = mysortdata(time, signal)
if numel(time) <= 1
  return
end
PivotTime = time(end);
PivotSignal = signal(end);
time(end) = [];
signal(end) = [];
less     = (time <= PivotTime);
%  input Less and More into this function again 
[LessTime, LessSignal] = mysortdata(time(less), signal(less));
[MoreTime, MoreSignal] = mysortdata(time(~less), signal(~less));
time  = [LessTime, PivotTime, MoreTime];
signal = [LessSignal, PivotSignal, MoreSignal];
end

Answer 2

[Jan]

LessTime = time(time <= PivotTime);

LessSignal = time(time <= PivotTime);

This redundant. I guess you mean:

indexLess  = time <= PivotTime;
LessTime   = time(indexLess);
MoreTime   = time(~indexLess);
LessSignal = signal(indexLess);  % Not time() again

Then sort the Signal accordingly:

PivotTime   = time(end);
PivotSignal = singal(end);

time(end) = [];
signal(end) = [];

and

[LessTime2, LessSignal2] = mysortdata(LessTime, LessSignal);
[MoreTime2, MoreSignal2] = mysortdata(MoreTime, MoreSignal);

Well, I admit I'm not sure which sorting algorithm this is. It seems like sorting two arrays is not meaningful. You have to sort the indices instead, such that you can apply the index vector to the signal afterwards also:

function [time, index] = mysortdata(time, index)
if numel(time) <= 1
  return
end

PivotTime = time(end);
time(end) = [];

less     = (time <= PivotTime);
LessTime = time(less);
MoreTime = time(~less);
LessIndex = index(less);
MoreIndex = index(~less);

%  input Less and More into this function again 
[LessTimeSorted, LessIndexStorted] = mysortdata(LessTime, LessSignal);
[MoreTimeSorted, MoreIndexStorted] = mysortdata(MoreTime, MoreSignal);

time  = [LessTimeSorted, PivotTime, MoreTimeSorted];
index = [LessIndexSorted, PivotIndex, MoreIndexSorted];
end

Call it like:

[time, index] = mysortdata(time, 1:length(time))
signal = signal(index);

But, well, this seems to be an inefficient algorithnm. The recursion will waste memory massively.

[Dan Page]

Thank you for going to the time to do this, but i cant get this to work

[Bruno Luong]

"Well, I admit I'm not sure which sorting algorithm this is. "

Quicksort.

[Jan]

@Bruno: Thanks. We call it "tomatos on the eyes" in German.

@Dan: Please note that "can't get it to work" does not allow to understand, which problems you have. It is hard to guess how we can help you. I assume, that my code does not run without adjustments, because I tried to demonstrate the idea and to stay almost at your code. Search for "quicksort Matlab" to find more compact and working implementations.

[Bruno Luong]

Jan, "Tomaten auf den Augen haben"? hah hah ...