Re: More Informed Sort

[Bill Denney]

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
-------------------------------------------------------------