Re: Generic In-Place Sort

From: Rob Kennedy (me_at_privacy.net)
Date: 03/25/04 

Date: Wed, 24 Mar 2004 23:53:29 -0600

Duncan McNiven wrote:
> Some initial reactions:
>
> There is a bug in that you get an Access Violation if you sort an empty
> set.

Right. The QuickSort procedure doesn't do any checking to see whether
the indices it was given are actually valid. So with an empty array, the
first call to Compare has arguments of 0 and 0, which are invalid for an
empty array. The next call to Compare is potentially worse: Its
arguments will be -1 and 0. You'll get either an access violation or a
range-checking error, depending on the $R compiler option.

InsertionSort and BubbleSort are fine. They check that their low indices
are strictly less than their high indices before proceding.

> It seems potentially wasteful of time and memory to have to load all
> data into a Sorter object. Did you consider a design that sorts, say,
> arrays that are external to the class so that it is not necessary to
> duplicate data in order to sort it?

That's what TVirtualSorter is for. All that class does is sort the
indices. It uses event handlers to know what the low and high indices
are, to do the comparison, and to do the swap. Bruce provided
specializations for sorting arrays of Integers and arrays of strings.

Also, the specializations merely hold a reference to a dynamic array of
items. They don't have their own internal copies. (Dynamic arrays are
reference counted, but they do not have the copy-on-write semantics that
AnsiStrings have.) That is, until you set the object's Length property.

> I don't like the way the various sort methods are implemented as nested
> routines. I would prefer seperate methods that I could override, to add
> events to show progress or add code to measure performance for example.

I agree. Not really much point in having a virtual Sort method if
there's nothing there to override, either. The Sort procedure has no
parameters and no local variables, so the local procedures aren't really
sharing anything with their container.

> BTW, what is the reason for the blank line before each routine BEGINs?
> It is an unusual format (at least I have not seen it used elsewhere) and
> I am curious what advantage you get from it.

You've obviously never seen any of Mike Lischke's code. Blank lines
before every procedure's "begin," a separator line between every method,
and comments written with a right margin of 120 characters. 

-- 
Rob

Relevant Pages

  • Re: Help with Array(s)
    ... I would think XML would return in something with an XML schema and you could ... Array.Sort sorts one-dimentional arrays, but don't think it will 2dim arrays ... to sort list by second int value and display. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: does C# have any collection objects that support sort functionality so that I dont have to writ
    ... the IComparable interface. ... Also, since arrays are strongly typed, you know that all elements are of the ... for ArrayLists. ... The Sort() method will utilize each object's IComparable ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: IsAnagram
    ... Sort both words and compare both arrays. ... So I am looking for the most efficient algorithm. ... Sort both sounds like the most efficient. ... array first. ...
    (comp.lang.c)
  • Re: Arrays
    ... > Arrays are very rich objects in CL. ... > copying some sort of object, or testing one for equality, there are ... > The Lisp reader does a lot of this when reading strings and symbols. ...
    (comp.lang.lisp)
  • Re: Patrick, Evil REV, SMBalloon
    ... empty they were that they had to invent a world where any sort of ... excitement was taboo, ...
    (rec.music.artists.springsteen)