Need sort algorithm that takes linear time on a sorted list

Need sort algorithm that takes linear time on a sorted list

Post by Jamie Loki » Thu, 22 Jul 1993 09:52:52



We need to sort a set of numbers, in such a way that the sort takes
linear time in the number of elements if the list is already sorted, and
no worse than O(n log n) time otherwise.  We are implementing this in
hardware, and need to minimise the number of memory access.  Because of
this, an array is probably a better representation than a linked list,
but maybe not.

We can see that examining the list first, then doing a merge-sort if
there are any elements out of order, but we would prefer not to do this.
In particular, we would rather like the algorithm to spend O(n log n)
time operating on any unsorted sub-lists, while still managing O(n) time
on the rest.  I.e., any time that it takes in addition to the time it
takes on a sorted list should depend only on those clusters of elements
that are out of order.

This is for a multiple polygon rendering algorithm: the hardware
maintains a list of x-coordinates in order, to run-length encode the
pixel colour changes occurring on a single horizontal scan line, which
are dispatched to pixel rendering hardware.  As the scan line move down
vertically, the x-coordinates move by (different) small amounts.
Occasionally, a few move past the others.  The sorting algorithm is
needed to maintain the sorted order of these pixels.  Because we don't
expect the sequence order to change much from one scan line to the next,
an algorithm that takes linear time when most of the elements are
already in order would be ideal.

Insertion sort is pretty fast when most of the elements are in order,
but takes O(n^2) time in the worst case (which can happen with our
polygon rendering).  Merge sort is pretty good all round.  Quick sort is
good almost all the time, but a good implementation is probably too
complicated to implement in the amount of hardware we have available.

We are thinking of some kind of hybrid of merge sort and insertion sort,
but no particular algorithm has suggested itself :-)

Does anyone know of a suitable sorting algorithm?

Thank,

Jamie

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Timothy Connal Delan » Thu, 22 Jul 1993 22:23:55


   You can always try the Combsort (god ... people will think I'm an
advocate of this thing ...). While not as fast generally as the
quicksort, it usually outperforms anything else. As well, it *never*
slows down ... the worst time is on a completely random list. Any
partially-sorted list speeds it up. Unfortunately, it never actually
becomes an O(n) sort as it compares until it has a gap of 1. Try it out ...
it may be what you want. Here's some info and code.

   The combsort is an optimised version of the bubble sort. It uses a
decreasing gap in order to compare values of more than one element apart.
By decreasing the gap the array is gradually "combed" into order ...
like combing your hair. First you get rid of the large tangles, then the
smaller ones ...

   There are a few particular things about the combsort. Firstly, the optimal
shrink factor is 1.3 (worked out through a process of exhaustion by the guys
at BYTE magazine). Secondly, by never having a gap of 9 or 10, but always
using 11, the sort is faster.

   This sort approximates an n log n sort - it's faster than any other sort
I've seen except the quicksort (and it beats that too sometimes ... have you
ever seen a quicksort become an (n-1)^2 sort ... ?). The combsort does not
slow down under *any* circumstances. In fact, on partially sorted lists
(including *reverse* sorted lists) it speeds up.

   Hope it's of use to you. I find it's the one I use most - it's fast and
takes very little time to program. I can't always remember how to program
a quicksort, but this one's no problem at all (except on late nights ...).

   If you want any more information on this, it's in BYTE magazine,
April 1991.

   Disclaimer : I've got absolutely *no* connection with BYTE magazine. I'm
                just a poor first-year university student.

program CombSort;

const
   MaxElement = 100;                      { Some arbitrary number ...       }

type
   IntArray   = array [1..MaxElement] of Integer;

var
   theArray   : IntArray;

{ ****************** The important bit ... ******************************** }

procedure CombSort11 (var theArray : IntArray);

const
   ShrinkFactor = 1.3;                    { Optimal shrink factor ...       }

var
   gap          : Integer;
   i            : Integer;
   temp         : Integer;
   finished     : Boolean;

begin

   gap := ShrinkFactor;
   repeat

      finished := true;

      gap := trunc(gap/ShrinkFactor);
      if gap < 1 then                     { Gap must *never* be less than 1 }
         gap := 1
      else if gap in [9, 10] then         { Optimises the sort ...          }
         gap := 11;

      for i := 1 to (MaxElements - gap) do
         if theArray[i] < theArray[i+gap] then begin
            temp := theArray[i];
            theArray[i] := theArray[i+gap];
            theArray[i+gap] := temp;
            finished := false;
         end;

   until (gap = 1) and finished;

end;

{ ************************************************************************* }

begin

   { Code ... }

   CombSort11(theArray);

   { Other code ... }

end.

                                         _/_/_/_/
   _/_|  _/_|       _/_|     _/_/_/        _/_|     _/_/_/
  _/ _| _/ _|     _/  _|   _/            _/  _|   _/    _/
 _/  _|_/  _|   _/_/_/_|  _/   _/_/_/  _/_/_/_|  _/    _/
_/   _|    _| _/      _|  _/_/_/_/   _/      _|  _/_/_/



 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Nick Engla » Fri, 23 Jul 1993 00:40:49


How about a bubble sort ? Isn't that what the original Watkins box
used 20 years ago for exactly this same problem ? :-)

Dare I say it - Sutherland, Sproull, and Schumacker is still a good paper
to read on sorting and graphics.
Computing Surveys 6(1) March 1974 pp 1-55.

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Mark Ha » Fri, 23 Jul 1993 01:42:58


)How about a bubble sort ? Isn't that what the original Watkins box
)used 20 years ago for exactly this same problem ? :-)

   bubblesort doesn't qualify for the 'and no worse than O(n log n)
on an unsorted list'.

   How about

   1) linear walk through the list until you find an out-of-order
     element.

     If you get to the end, you're done in O(n) time.

     else  
   2) use your favorite O(n log n) worst case sort algorithm.

)
)Dare I say it - Sutherland, Sproull, and Schumacker is still a good paper
)to read on sorting and graphics.
)Computing Surveys 6(1) March 1974 pp 1-55.

   still an excellent reference.

  - mark

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Morten Welind » Fri, 23 Jul 1993 02:52:03



>How about a bubble sort ? Isn't that what the original Watkins box
>used 20 years ago for exactly this same problem ? :-)
>Dare I say it - Sutherland, Sproull, and Schumacker is still a good paper
>to read on sorting and graphics.
>Computing Surveys 6(1) March 1974 pp 1-55.

Bubble sort and its look-alike shaker sort are O(N*N), I suspect you ment
to say "insertion sort".

For an excellent analysis of sorting, see

        Knuth: The Art of Computer Programming

the volume about searching and sorting.

Morten Welinder

--
-------------------------------------------------------------------------
Visit the lyrics archive at ftp.uwp.edu (mirrored to nic.funet.fi, a site
in Finland). All kinds of lyrics available -- upload "yours" and join.

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Ozan S. Yig » Fri, 23 Jul 1993 04:47:26


Quote:Jamie Lokier writes:

   We need to sort a set of numbers, in such a way that the sort takes
   linear time in the number of elements if the list is already sorted, and
   no worse than O(n log n) time otherwise. [etc ...]

how about radix sort?

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Kenneth Slo » Fri, 23 Jul 1993 04:35:45




>>How about a bubble sort ? Isn't that what the original Watkins box
>>used 20 years ago for exactly this same problem ? :-)

>>Dare I say it - Sutherland, Sproull, and Schumacker is still a good paper
>>to read on sorting and graphics.
>>Computing Surveys 6(1) March 1974 pp 1-55.

>Bubble sort and its look-alike shaker sort are O(N*N), I suspect you ment
>to say "insertion sort".

while "insertion sort" is the right thing to do (even though it doesn't
meet the specifications of the original poster) - I would bet that if
Nick says that's what the original Watkins box used, then that's what he
"ment to say".  And...unless I had the original specs in hand, I'd tend
to bet that he was right.

--
Kenneth Sloan                   Computer and Information Sciences

(205) 934-2213                  115A Campbell Hall, UAB Station
(205) 934-5473 FAX              Birmingham, AL 35294-1170

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Nick Engla » Fri, 23 Jul 1993 05:54:59





>>>How about a bubble sort ? Isn't that what the original Watkins box
>>>used 20 years ago for exactly this same problem ? :-)

>>>Dare I say it - Sutherland, Sproull, and Schumacker is still a good paper
>>>to read on sorting and graphics.
>>>Computing Surveys 6(1) March 1974 pp 1-55.

>>Bubble sort and its look-alike shaker sort are O(N*N), I suspect you ment
>>to say "insertion sort".

>while "insertion sort" is the right thing to do (even though it doesn't
>meet the specifications of the original poster) - I would bet that if
>Nick says that's what the original Watkins box used, then that's what he
>"ment to say".  And...unless I had the original specs in hand, I'd tend
>to bet that he was right.

Thanks for the faith !!

*For this application*, the order of the run-length segments doesn't
change often, and when it does it is almost always a simple swap of
adjacent items (when edges cross). Also, an active edge list (bucket
sort works great for this - only 512-1024 scan lines) is usually
maintained and a merge (insertion?) of the new edges with the old edge
list is easy. This avoids the case where bubble sort might get messy.

So, in practice, a combination of techniques has been shown to work
quite well for this particular graphics application. Sorry, but I
still say Sutherland, Sproull, and Schumacker is a better reference
than Knuth in this case.

best regards,
Nick England, Vintage Graphics Hardware Afficianado

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Kenneth Slo » Fri, 23 Jul 1993 08:13:05



>Nick England, Vintage Graphics Hardware Afficianado

is that: (Vintage Graphics Hardware) Afficianado,
     or: Vintage (Graphics Hardware Afficianado)?

--
Kenneth Sloan                   Computer and Information Sciences

(205) 934-2213                  115A Campbell Hall, UAB Station
(205) 934-5473 FAX              Birmingham, AL 35294-1170

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Samuel S. Pa » Fri, 23 Jul 1993 09:46:21



Quote:>   You can always try the Combsort (god ... people will think I'm an

How does this differ from a Shell sort?  (I guess that was rhetorical)

Shell sorts empirically have average case behavior of O(1 + fraction).
[I must admit, shell sorts seem to have been _real_ popular back in my
AppleSoft Basic days, when there was no recursion and emulating a
stack was rather expensive]

Sam Paik

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by David Kastr » Fri, 23 Jul 1993 15:30:23




>>How about a bubble sort ? Isn't that what the original Watkins box
>>used 20 years ago for exactly this same problem ? :-)
>Bubble sort and its look-alike shaker sort are O(N*N), I suspect you ment
>to say "insertion sort".

Which is only O(N*N)...
--

 Tel: +49-241-72419 Fax: +49-241-79502
 Goethestr. 20, D-52064 Aachen
 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by William Nayl » Fri, 23 Jul 1993 13:47:06


Quote:>Insertion sort is pretty fast when most of the elements are in order,
>but takes O(n^2) time in the worst case (which can happen with our
>polygon rendering).  Merge sort is pretty good all round.  Quick sort is
>good almost all the time, but a good implementation is probably too
>complicated to implement in the amount of hardware we have available.

>We are thinking of some kind of hybrid of merge sort and insertion sort,
>but no particular algorithm has suggested itself :-)

>Does anyone know of a suitable sorting algorithm?

Have you considered a "radix sort"?  A radix sort takes O(n) time on
all lists, whether sorted or not.  It is ideal for sorting a list of
fixed-length integers.

I can provide you C code, if you wish.

Good luck.

--

                          mail: Canon Information Systems Research Australia  
phone: + (61-2) 805-2921        P.O. Box 313 North Ryde, NSW 2113
fax:   + (61-2) 805-2929        Australia

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Mike Gleas » Fri, 23 Jul 1993 22:49:17


Quote:> program CombSort;

[...]

Anyone already convert this to C, adhering to qsort() calling conventions?

--

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Kenneth Slo » Sat, 24 Jul 1993 00:11:28





>>>How about a bubble sort ? Isn't that what the original Watkins box
>>>used 20 years ago for exactly this same problem ? :-)

>>Bubble sort and its look-alike shaker sort are O(N*N), I suspect you ment
>>to say "insertion sort".
>Which is only O(N*N)...

Not for this application.  Virtually all of the lists are almost
completely sorted.  A properly implemented Insertion Sort fairly screams
in this environment.

If you want speed in this application - use Insertion Sort.

If you need realtime guarantees, and are willing to sacrifice raw speed
for predictability...use Heap Sort (guaranteed to achieve the upper
bound almost always in this environment).

If you want predictability, but don't want to give up raw speed...you
need hybrid methods.  But first - verify that sorting the edge list is
*really* your bottleneck.  If it's not, then perhaps even Bubble Sort is
OK.

The problem with Bubble Sort is that it's more difficult to get right
than Insertion Sort [all those who are now laughing at this outrageous
statement have never taught the course!]  Insertion Sort should be in
everyone's toolbox because:

    *it's the easiest sort to write, and debug
    *it's very fast in environments where you incrementally
     update a large sorted list
    *it's very useful as the last stage in complex "hybrid" sorts

for example - if your taste runs towards QuickSort, then you should know
that it is very useful to *not* sort sublists below a certain size.
This gives a list in which every item is "close to"
it's final position.  One pass of InsertionSort (some books recommend
invoking InsertionSort on each small sublist - it's often better to
simply InsertionSort the entire "almost sorted" list) will finish off
the sort, in linear time (the constant factor is the size of the largest
sublist that you choose *not* to sort with
YetAnotherRecursiveApplication of QuickSort.

So...InsertionSort strictly dominates BubbleSort, and it's actually a
useful tool.  In some applications, it's the best pure choice.  In
others, it's a useful component in a hybrid.

But...returning to the point...it wouldn't surprise me a bit to find
that a 20year old hardware design included a bubble sort.

--
Kenneth Sloan                   Computer and Information Sciences

(205) 934-2213                  115A Campbell Hall, UAB Station
(205) 934-5473 FAX              Birmingham, AL 35294-1170

 
 
 

Need sort algorithm that takes linear time on a sorted list

Post by Timothy Connal Delan » Sat, 24 Jul 1993 00:33:09


   Please note ... I let a slight bug slip through here (late night coding).

It should read ...

Quote:>program CombSort;
>const
>   MaxElement = 100;                      { Some arbitrary number ...       }
>type
>   IntArray   = array [1..MaxElement] of Integer;
>var
>   theArray   : IntArray;
>{ ****************** The important bit ... ******************************** }
>procedure CombSort11 (var theArray : IntArray);
>const
>   ShrinkFactor = 1.3;                    { Optimal shrink factor ...       }
>var
>   gap          : Integer;
>   i            : Integer;
>   temp         : Integer;
>   finished     : Boolean;
>begin
>   gap := ShrinkFactor;

           ^^^^^^^^^^^^   --> wrong

    gap := {length of array};

- Show quoted text -

>   repeat
>      finished := true;
>      gap := trunc(gap/ShrinkFactor);
>      if gap < 1 then                     { Gap must *never* be less than 1 }
>         gap := 1
>      else if gap in [9, 10] then         { Optimises the sort ...          }
>         gap := 11;
>      for i := 1 to (MaxElements - gap) do
>         if theArray[i] < theArray[i+gap] then begin
>            temp := theArray[i];
>            theArray[i] := theArray[i+gap];
>            theArray[i+gap] := temp;
>            finished := false;
>         end;
>   until (gap = 1) and finished;
>end;
>{ ************************************************************************* }
>begin
>   { Code ... }
>   CombSort11(theArray);
>   { Other code ... }
>end.
>                                         _/_/_/_/
>   _/_|  _/_|       _/_|     _/_/_/        _/_|     _/_/_/
>  _/ _| _/ _|     _/  _|   _/            _/  _|   _/    _/
> _/  _|_/  _|   _/_/_/_|  _/   _/_/_/  _/_/_/_|  _/    _/
>_/   _|    _| _/      _|  _/_/_/_/   _/      _|  _/_/_/