Speeding up Sort Algorithm by removing ismember
3 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Dan Page
el 12 de Dic. de 2018
Respondida: Bruno Luong
el 13 de Dic. de 2018
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
4 comentarios
Bruno Luong
el 12 de Dic. de 2018
Editada: Bruno Luong
el 12 de Dic. de 2018
Permuting the second array signal exatly the same way like time.
Respuesta aceptada
Bruno Luong
el 13 de Dic. de 2018
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
0 comentarios
Más respuestas (1)
Jan
el 12 de Dic. de 2018
Editada: Jan
el 12 de Dic. de 2018
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.
4 comentarios
Jan
el 12 de Dic. de 2018
Editada: Jan
el 12 de Dic. de 2018
@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.
Ver también
Categorías
Más información sobre Shifting and Sorting Matrices en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!