[Gretl-devel] sorting string arrays
As far as I know, we don't have a function for sorting string arrays, so I
implemented quicksort in hansl as shown below.
As you can see, the function sorts the array and returns a vector of
integers so that you can map the old positions to the new ones if needed.
Performance is not at all bad, I'd say.
I'm thinking: would it be worthwhile to add this to the "extra" package?
Or should we have a native C implementation? Also: is this imaginable for
other array types? I can't think of an obvious way to sort bundles or
matrices, but perhaps someone has a clever idea.
<hansl>
set verbose off
function void swap(strings *a, matrix *ndx, scalar i, scalar j)
string s = a[j]
scalar x = ndx[j]
string a[j] = a[i]
scalar ndx[j] = ndx[i]
string a[i] = s
scalar ndx[i] = x
end function
function scalar part(strings *a, matrix *ndx, scalar lo, scalar hi, bool reverse)
string pivot = a[hi]
scalar i = lo
loop j = lo .. (hi-1) --quiet
cmp = strncmp(a[j], pivot)
if (reverse ? cmp > 0 : cmp < 0)
swap(&a, &ndx, i++, j)
endif
endloop
swap(&a, &ndx, i, hi)
return i
end function
function void real_sqsort(strings *a, matrix *ndx, scalar lo, scalar hi, bool reverse)
if lo < hi
p = part(&a, &ndx, lo, hi, reverse)
real_sqsort(&a, &ndx, lo, p-1, reverse)
real_sqsort(&a, &ndx, p+1, hi, reverse)
endif
end function
function matrix strings_sort(strings *A, bool reverse[0])
scalar n = nelem(A)
if n == 1
return {1}
endif
matrix s = seq(1, n)
real_sqsort(&A, &s, 1, n, reverse)
return s
end function
###
### example
###
clear
x = defarray("alpha", "foo", "X", "bar",
"baz", "")
print x
ord = strings_sort(&x)
print x ord
</hansl>
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------