4 ms·
> In fact, I'm not aware of an algorithm that is as simple as Shell sort, and at the same time much faster than O(n^2). My favorite is heap sort, guaranteed O(
by graycat 4y ago
> In fact, I'm not aware of an algorithm
that is as simple as Shell sort, and at
the same time much faster than O(n^2).
My favorite is heap sort, guaranteed O(n
log(n)) average case and worst case, meets
the Gleason bound and, thus, is the
fastest possible sort based on comparing
pairs of keys (in one of volumes of D.
Knuth, The Art of Computer Programming).
You mentioned simple: The logic of the
heap data structure and its corresponding
code seem to be relatively simple.
Of course, radix sort does not work by
"comparing pairs of keys", may be regarded
as O(n), and, check this, may also be
stable. Of course, radix sort was the
algorithm of the IBM punched card
sorting machine so maybe goes back to
before 1900 and, thus, is likely the
oldest of the common sorting algorithms.
Below (in a separate post) is code for
ai_heap_sort02
which is an (ascending integer) heap sort
routine.
Right, this code is for only ascending,
integers, and arrays and, thus, is far
from the practice of generic code, e.g.,
as in
https://en.wikipedia.org/wiki/Generic_programming https://en.wikipedia.org/wiki/Generic_programming
The advantages of generic code my work
doesn't really need. Once I wrote some
generic code, and that experience was
enough!
The code is in Microsoft's Visual Basic
.NET.
Why Visual Basic .NET?
I have written some C code. There are
claims that the programming language C has
idiosyncratic syntax. Whatever it has,
I don't like its syntax. I.e., supposedly
i = ++j+++++k++
is legal -- increase j and k by 1, add the
results, assign the result to i, and then
increase j and k by 1 again -- but when I
tested this on two different C compilers I
got different results. If the compilers
can't agree on the syntax, I don't want to
try to understand it! Besides, C is
supposed to be really simple, close to
assembly language, and highly portable,
and ambiguity I observed for
i = ++j+++++k++
conflicts with those attributes! Besides,
that syntax gets the grand prize for not
just idiosyncratic but obscure,
ugly, outrageous,
etc.!
Maybe C and C++ are essential for Windows
internals and for Windows applications
that make direct use of the System32 API,
but I've never written such code since my
background is applied math software.
Thus, also I don't like the related syntax
of C++ or C#.
The syntax of Visual Basic .NET (VB) is
more traditional, more like the original
Basic, then Fortran, Algol, Pascal, and
PL/I (maybe my favorite).
Thus, VB is relatively easy to teach,
learn, read, and write, and these
attributes might be considered important
in a large project!
Whatever the syntax of VB is, there are
claims that VB and C# have equivalent
semantics and differ only in syntactic
sugar. I.e., supposedly there is a
source code translator program than can
translate code in either of VB or C# to
the other.
So, for my project, code to run on
Windows, I am writing in VB instead of C#.
Also below (in a separate post)
is code
Function obj_heap_insert
Here I use the heap data structure, the
main idea in heap sort, to maintain a
priority queue. So, with this code can
look at 20 million objects one at a time
and end up with, e.g., the 20 largest.
Uh, how else to do that???!!!
Right, this code starts to be a little big
generic.
Right, operating on the heap data
structure can hurt possibly desired main
memory and cache memory locality of
reference, but there is at least one
modification of modifying operations on a
heap that speed up what otherwise might be
the case of a heap large enough to need
virtual memory.
All this code appears to run correctly. I
have later versions modified, longer, less
easy to read, to use an error handling
technique I cooked up -- really simple, I
wouldn't recommend for large projects and
it will likely become a case of technical
debt if my work grows a lot!
Uh, my view, a judgment call, is that the
article and my post here go deeper into
sorting than we should. I want to declare
sorting as a plenty well enough
understood, solved problem and move on to
other challenges.
- graycat 4y ago' Ascending integer (Int32) heap sort. ' ' For i = 1, 2, ..., n, sort components of key_array(i) ' into ascending order using heap sort. ' ' We check parameters for reasonable values and, in case of ' a error, raise the error condition. ' ' Upon return, for i = 1, 2, ..., n - 1, ' ' key_array( i ) <= key_array( i + 1 ) ' ' The code here is 'structured' in the sense of E. Dijkstra ' and, thus, is without the GOTO statements of own Watson ' PL/I heap sort code. ' ' The array subscript logic here is done carefully enough ' that it should never overflow even for the largest ' possible value of n. ' ' For some constant k (depending on the computer, compiler, ' etc. but not depending on the parameters) the execution ' time is guaranteed to be closely just ' ' k*n*log(n) ' ' in the worst case. ' ' The code here needs a 'sift' loop in two places; the code ' is the same in both places. ' ' The work here is 'in place', that is, uses no storage ' whose size depends on the passed parameters. ' Sub ai_heap_sort02( _ ByRef key_array() As Int32, _ ByVal n As Int32 ) Dim routine_name As String = "ai_heap_sort02" Dim error_code As Int32 = 0 Dim i_2 As Int32 = 2 Dim i_first, i_middle, i_last As Int32 Dim i_father0 As Int32 Dim i_father, i_child1, i_child2, i_max_child As Int32 ' We need one working location of data type the same as the ' components of parameter key_array(): Dim key_father As Int32 Try ' Get started: error_code = 1001 If n <= 0 Then err.raise(error_code, routine_name) error_code = 1002 If key_array.GetUpperBound(0) < n Then err.raise(error_code, routine_name) End If error_code = 1003 i_first = 1 i_last = n i_middle = i_last \ i_2 i_father0 = i_middle + 1 ' Build heap Do i_father0 = i_father0 - 1 If i_father0 < i_first Then Exit Do key_father = key_array( i_father0 ) i_father = i_father0 ' Sift Do If i_father < i_middle Then i_child1 = i_father + i_father i_child2 = i_child1 + 1 If key_array( i_child1 ) > key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If If key_array( i_max_child ) > key_father Then key_array( i_father ) = key_array( i_max_child ) i_father = i_max_child Continue Do Else key_array( i_father ) = key_father Exit Do End If Else ' i_father >= i_middle If i_father > i_middle Then key_array( i_father ) = key_father Exit Do End If i_child1 = i_father + i_father ' i_father = i_middle If i_child1 < i_last Then i_child2 = i_child1 + 1 If key_array( i_child1 ) > key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If Else ' i_child1 = i_last i_max_child = i_child1 End If If key_array( i_max_child ) > key_father Then key_array( i_father ) = key_array( i_max_child ) key_array ( i_max_child ) = key_father Else key_array ( i_father ) = key_father End If Exit Do End If Loop ' End of sift loop Loop ' End of build heap loop ' Sort heap i_first = 1 i_last = n Do key_father = key_array( i_last ) key_array( i_last ) = key_array( i_first ) key_array( i_first ) = key_father i_father = i_first i_last = i_last - 1 If i_last <= i_first Then Exit Do i_middle = i_last \ 2 ' Sift Do If i_father < i_middle Then i_child1 = i_father + i_father i_child2 = i_child1 + 1 If key_array( i_child1 ) > key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If If key_array( i_max_child ) > key_father Then key_array( i_father ) = key_array( i_max_child ) i_father = i_max_child Continue Do Else key_array( i_father ) = key_father Exit Do End If Else ' i_father >= i_middle If i_father > i_middle Then key_array( i_father ) = key_father Exit Do End If i_child1 = i_father + i_father ' i_father = i_middle If i_child1 < i_last Then i_child2 = i_child1 + 1 If key_array( i_child1 ) > key_array( i_child2 ) Then i_max_child = i_child1 Else i_max_child = i_child2 End If Else ' i_child1 = i_last i_max_child = i_child1 End If If key_array( i_max_child ) > key_father Then key_array( i_father ) = key_array( i_max_child ) key_array ( i_max_child ) = key_father Else key_array ( i_father ) = key_father End If Exit Do End If Loop ' End of sift loop Loop ' End of sort heap loop Catch err.raise(error_code, routine_name) End Try out: Return End Sub