[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: More Informed Sort
From: |
Bill Denney |
Subject: |
Re: More Informed Sort |
Date: |
Sat, 11 Feb 2006 08:51:12 -0500 (EST) |
On Sat, 11 Feb 2006, David Bateman wrote:
The octave soring class is based on a mergesort and given partially
sorted lists will be significantly faster than other types of sorts. The
matlab sorting class is based on quicksort so is better for random
lists. This being the case just using octave sort function should give
near optimum performance.
Unfortunately, the C++ below doesn't make much sense to me. After looking
at the wikipedia page on mergesort
(http://en.wikipedia.org/wiki/Merge_sort), I came to the conclusion that
I'm looking for direct access to the merge functionality of mergesort. Is
that what your code below says?
My idea of what I'm wanting to do in .m syntax for a trivial case would
look something like
sortedlist = 1:100;
unsortedlist = rand(10,1);
unsortedlist = sort(unsortedlist);
sortedlist = merge(unsortedlist, sortedlist);
function [list, idx] = merge(list1, list2)
list = zeros(length(list1) + length(list2),1);
idx = list;
ll1 = length(list1);
list1cntr = 1;
list2cntr = 1;
for i = 1:length(list)
if (list1(list1cntr) <= list2(list2cntr))
list(i) = list1(list1cntr);
idx(i) = list1cntr;
list1cntr = list1cntr + 1;
if (list1cntr > length(list1))
list(i+1:end) = list2(list2cntr:end);
idx(i+1:end) = ll1 + list2cntr:length(list2);
break;
endif
else
list(i) = list2(list2cntr);
list2cntr = list2cntr + 1;
idx(i) = ll1 + list2cntr;
if (list2cntr > length(list2))
list(i+1:end) = list1(list1cntr:end);
idx(i+1:end) = list1cntr:length(list1);
break;
endif
endif
endfor
endfunction
Bill
Additionally as the octave sort function is written as a class you can easily
apply it to sort other types of data in an oct-file. For example to sort an
octave_idx_type vector and also return the vector of indices you can do
something like
class
octave_idx_vector_sort
{
public:
octave_idx_type i;
octave_idx_type idx;
};
bool
octave_idx_vector_comp (octave_idx_vector_sort* i,
octave_idx_vector_sort* j)
{
return (i->i < j->i);
}
template class octave_sort<octave_idx_vector_sort *>;
int main (void){
...
OCTAVE_LOCAL_BUFFER (octave_idx_vector_sort *, sidx, n);
OCTAVE_LOCAL_BUFFER (octave_idx_vector_sort, sidxX, n);
for (octave_idx_type i = 0; i < n; i++)
{
sidx[i] = &sidxX[i];
sidx[i]->i = lhs_idx.elem(i);
sidx[i]->idx = i;
}
octave_sort<octave_idx_vector_sort *> sort
(octave_idx_vector_comp);
sort.sort (sidx, n);
...
}
Where sidx[i]->i returns the data and sidx[i]->idx returns the list of
indices..
Regards
David
--
David Bateman address@hidden
Motorola Labs - Paris +33 1 69 35 48 04 (Ph) Parc Les
Algorithmes, Commune de St Aubin +33 6 72 01 06 33 (Mob) 91193
Gif-Sur-Yvette FRANCE +33 1 69 35 77 01 (Fax)
The information contained in this communication has been classified as:
[x] General Business Information [ ] Motorola Internal Use Only [ ] Motorola
Confidential Proprietary
-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.
Octave's home on the web: http://www.octave.org
How to fund new projects: http://www.octave.org/funding.html
Subscription information: http://www.octave.org/archive.html
-------------------------------------------------------------
--
"Those who do not study history are doomed to repeat it."
"Yes, and those who do study history are doomed to watch in frustration
as it is unwittingly repeated by those who do not."
-- address@hidden
-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.
Octave's home on the web: http://www.octave.org
How to fund new projects: http://www.octave.org/funding.html
Subscription information: http://www.octave.org/archive.html
-------------------------------------------------------------