Generalized sorting function with user defined (template-)criterion

1 view (last 30 days)
Jürgen
Jürgen on 20 Jan 2022
IIs there a build in function for sorting cell arrays with a user-defined comparison function(-handle) like qsort in ANSI-C (or corresponding template-based technique in C++/STL... or other modern languages)?
To make it clear what I search for, I added an elementary handmade C-Code-example, that I tested with MS-VS-2015:
Below the code a screenshot of the output. One can see that it is possible with this technique to sort according to arbitrary criteria. In the example, the elements are sorted with respect to the character ascending as a primary criterion and with respect to the numeric element in descending order as a secondary criterion (applied when different elements have the same character).
I hoped that such approaches might also be available as Matlab-build-in concepts for more general fields of data-structures?
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
struct myStrDef {
int num;
char lit;
};
void myStrPrint(myStrDef* myStr) {
printf("%c | %d\n", (*myStr).lit, (*myStr).num);
return;
}
int myCmpfunc(const void * a, const void * b) {
int judgement;
myStrDef v, w;
v = *(myStrDef*)a;
w = *(myStrDef*)b;
judgement = v.lit - w.lit; // sort in alphabetic order
if (0 == judgement) {
judgement = -(v.num - w.num); // minus = in desc. order
}
return judgement;
}
int main() {
int idx;
myStrDef myStrucList[5];
myStrucList[0] = { 10, 'y' };
myStrucList[1] = { 10, 'x' };
myStrucList[2] = { 1, 'z' };
myStrucList[3] = { 100, 'a' };
myStrucList[4] = { 10000, 'a' };
printf("before sorting:\n");
for (idx = 0;idx < 5; idx++) {
myStrPrint(&myStrucList[idx]);
}
qsort(myStrucList, 5, sizeof(myStrDef), myCmpfunc);
printf("\nafter sorting:\n");
for (idx = 0;idx < 5; idx++) {
myStrPrint(&myStrucList[idx]);
}
return(0);
}

Answers (2)

Bruno Luong
Bruno Luong on 28 Mar 2022
Edited: Bruno Luong on 29 Mar 2022
AFAIK there is no such thing in stock function in MATLAB, the main reason is MATLAB function calling mechanism will kill the performance with user-defined comparison.
However it is not hard to write your own quicksort algorithm. My implementation below has another drawback since swapping elements requires deep-copy (?) which is slow.
% Example:
s=arrayfun(@(x) sprintf("%d",x), randi(200,1,20))
s = 1×20 string array
"140" "124" "121" "91" "44" "63" "130" "142" "168" "132" "179" "48" "108" "139" "45" "181" "156" "198" "59" "23"
ss=qsort(s, @(x,y) sign(double(x)-double(y)))
ss = 1×20 string array
"23" "44" "45" "48" "59" "63" "91" "108" "121" "124" "130" "132" "139" "140" "142" "156" "168" "179" "181" "198"
(EDIT: optimize qsort function)
function [A, is] = qsort(A, cmpfun)
% function [As, is] = qsort(A, cmpfun)
%
% A: vector array or vector cell array
% cmpfun: comparison function for form @(x,y)
% return -1 if x<y
% return +1 if x>y
% return 0 otherwise
% where x and y are (cell)elements of A
% OUTPUTS:
% As: A, but sorted, i.e. so that cmpfun(A(i),A(j)) <= 0 for any i<=j
% is: index vector so that A(is) is equal to As.
%
% Example:
% s=arrayfun(@(x) sprintf("%d",x), randi(200,1,20))
% ss=qsort(s, @(x,y) sign(double(x)-double(y)))
n = length(A);
is = 1:n;
if nargin < 2
cmpfun = @(x,y) sign(x-y);
end
is = qsort_helper(A, cmpfun, is);
A = A(is);
end % qsort
%%
% quicksort recursive engine
function idx = qsort_helper(A, cmpfun, idx)
if ~isempty(idx)
[p, idx] = partition(A, cmpfun, idx);
idx(1:p-1) = qsort_helper(A, cmpfun, idx(1:p-1));
idx(p+1:end) = qsort_helper(A, cmpfun, idx(p+1:end));
end
end
%%
function [p, idx] = partition(A, cmpfun, idx)
% idx(1:n) is selft-permutation such that
% pivot = A(idx(p));
% all(A(idx(1:p-1))<=pivot) && all(A(idx(p+1:n))>=pivot)
n = size(idx,2);
p = 1;
if ~isempty(idx)
% pivot index: strategy median-of-three
% A(idx(mid)) <= A(idx(1)) <= A(idx(n))
mid = floor((1 + n) / 2);
if cmpfun(A(idx(mid)),A(idx(n))) > 0
idx = swap(idx, n, mid);
end
if cmpfun(A(idx(mid)),A(idx(1))) > 0
idx = swap(idx, 1, mid);
end
if cmpfun(A(idx(1)),A(idx(n))) > 0
idx = swap(idx, 1, n);
end
pivot = A(idx(p));
i = p+1;
j = n;
% Loop to satisfied pivot condition
while true
while i<n && cmpfun(A(idx(i)),pivot) <= 0
i = i + 1;
end
while j>1 && cmpfun(A(idx(j)),pivot) >= 0
j = j - 1;
end
if i < j
idx = swap(idx, i, j);
i = i + 1;
j = j - 1;
else
% i is first element of right segment
if j > 1
% Last swap to put the pivot as the last element of the left subdivision
idx = swap(idx, 1, j);
p = j;
end
return
end
end
end
end
%%
function idx = swap(idx, i, j)
% swapt two elements idx, indexes by i and j
temp = idx(i);
idx(i) = idx(j);
idx(j) = temp;
end
  6 Comments
Prasanna Konyala
Prasanna Konyala on 1 Apr 2022
Hi
@Bruno Luong Thanks for the suggested approach
@Jürgen I understand, you want to sort the data using template-based sorting. Currently, this functionality is not available in MATLAB. I have brought this issue to the notice of the concerned people and it might be considered for a future release.

Sign in to comment.


Prasanna Konyala
Prasanna Konyala on 28 Mar 2022
From my understanding, you are trying to sort values on custom criteria. This can be done using sortrows().
value={10,'y';
10,'x';
1,'z';
100,'a';
1000,'a'
};
a=sortrows(value,[2,1],{'ascend','descend'});
This sorts the cell array based on 2nd column as primary criteria in ascending order and 1st column as secondary criteria in descending order
"Please refer to the documentation of sortrows() for more information".
  1 Comment
Jürgen
Jürgen on 28 Mar 2022
Hi Prasanna,
I know sortrows, but it is still to restricted and does not cover the options that are provided by template-technique that we know from C/qsort or more advanced from C++/STL. Assume, e.g. a slight extension of the above problem:
value={10,'cyabddd';
10,'bxcv';
1,'azqwe';
100,'mac1';
1000,'zaa9'
};
If the taks is to sort it descending according to the second and third character, then any such thing in arbitrary complexity it can be realized with the generic 'comparison-function' approach. To my experience I could solve it in Matlab only wiht loops... and mapping the sort-column intermediately to a column of sortable properties.
Maybe by applying something like arrayfun... but this twists my brain and I guess it will hardly be feasible.
I guess something like STL or Java/C#-Collectioons would still be a helpful paradigm also to include in Matlab. This would allow to avoid loops and run the sorting under the hood of Mathworks excellent memory management and utilize the natural strength of the template concept.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!