3 ms·

I wonder which type of Shell sort you were looking at. In my experience, it is fairly simple to implement gap sequence that is faster than O(n^2). Sure it is no

• 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
• graycat 4y ago
  ' Function obj_heap_insert ' Object heap insert to use the heap algorithm to maintain ' a 'priority queue'. ' ' So, suppose for positive integer n we have x(i) for i = ' 1, 2, ..., n and for positive integer m <= n we want the ' m largest of the x(i). So, we allocate an array y(j), j ' = 1, 2, ..., m. ' ' Suppose we regard y as an ascending heap, e.g., so that ' y(1) <= y(j), j = 2, ..., k <= m where the number of ' locations of y in use so far is integer k where 0 <= k <= ' m. ' ' Then for i = 1, 2, ..., n, we consider inserting x(i) ' into the heap. ' ' If k < m, then we set k = k + 1 and set y(k) = x(i) and ' 'sift' to 'promote' the value in y(k) until we have a ' heap again. ' ' If k = m, then we compare x(i) and y(1). If x(i) <= y(1), ' then we are done with x(i). Else, x(i) > y(1) and y(1) is ' not among the m largest and, to 'remove' value y(1) we ' set y(1) = x(i) and 'sift' the value in y(1) to create a ' heap again. ' ' After i = n, y contains the m largest of x(i), i = 1, 2, ' ..., n. ' ' The advantage of this routine is speed: When k = m, the ' effort to insert x(i) is proportional to log(m). When k ' < m, the effort to insert x(i) may be proportional just ' to k. The worst case would be when the array x was in ' ascending order since then x(i) would have to be inserted ' for each i. Similarly, in the case the array x is in ' descending order, after m inserts, no more inserts will ' be done. For the order of array x 'random', once a ' relatively large fraction of the m largest are in the ' heap, additional inserts become relatively rare. ' ' This routine is to be 'polymorphic', that is, to work for ' essentially any user defined class my_class1 where ' ' Dim m, n As Int32 ' Dim x( n ) As my_class1 ' Dim y( m ) As my_class1 ' ' This routine can build an ascending heap, as discussed ' above, or a descending heap. The only difference is how ' the comparisons are made in the class used for the ' interface. ' ' The interface IComparer is used. If the usual class ' Comparer is used for this interface, then this function ' builds an ascending heap, that is, where upon return ' ' y( 1 ) <= y( j ), ' ' for j = 2, 3, ..., m. Function obj_heap_insert( _ x As Object, _ y() As Object, _ ByRef k As Int32, _ m As Int32, _ compare As IComparer) As Int32 Dim routine_name As String = "obj_heap_insert" Dim error_code As Int32 Dim return_code As Int32 = 0 ' Dim result_code As Int32 Dim message_tag As Int32 Dim i_father As Int32 Dim i_child0 As Int32 Dim i_child1 As Int32 Dim i_child2 As Int32 Dim i_2 As Int32 = 2 Try error_code = 1001 message_tag = 1001 If console_msg_level >= console_routine_messages2 Then _ Console.WriteLine( routine_name & " " & message_tag & _ ": Started ..." ) error_code = 1002 If m <= 0 Then return_code = 1001 Goto out End If If k < 0 Then return_code = 1002 Goto out End If If k > m Then return_code = 1003 Goto out End If If y.GetUpperBound(0) < m Then return_code = 1004 Goto out End If error_code = 1003 If k < m Then i_child0 = k + 1 k = i_child0 error_code = 1004 Do ' Sift value of x into correct position. If i_child0 < 2 Then Exit Do i_father = i_child0 \ i_2 error_code = 1005 If compare.Compare( x, y( i_father ) ) >= 0 Then Exit Do y( i_child0 ) = y( i_father ) i_child0 = i_father Loop ' Sift value of x into correct position. error_code = 1006 y( i_child0 ) = x Goto out End If error_code = 1007 If compare.Compare( x, y( 1 ) ) <= 0 Then Goto out i_father = 1 error_code = 1008 Do ' Delete value of y( 1 ) and sift x to correct position ' starting at location y( 1 ) If i_father > m \ i_2 Then Exit Do i_child1 = i_father + i_father If i_child1 < m Then i_child2 = i_child1 + 1 error_code = 1009 If compare.Compare( y( i_child1 ), y( i_child2 ) ) < 0 Then i_child0 = i_child1 Else i_child0 = i_child2 End If Else i_child0 = i_child1 End If error_code = 1010 If compare.Compare( x, y( i_child0 ) ) <= 0 Then Exit Do y( i_father ) = y( i_child0 ) i_father = i_child0 Loop ' Delete value of y( 1 ) and sift x to correct position ' starting at location y( 1 ) y( i_father ) = x Catch Console.WriteLine( " " ) message_tag = 1002 Console.WriteLine( routine_name & " " & message_tag & _ ": Error condition raised. " & vbCrLf & _ ": error_code = " & error_code & vbCrLf & _ ": err.number = " & err.number & vbCrLf & _ ": err.source = " & err.source & vbCrLf & _ ": err.description = " & err.description ) message_tag = 1003 Console.WriteLine( routine_name & " " & message_tag & _ ": Raising error condition with error_code = " & error_code ) err.raise(error_code, routine_name) End Try out: message_tag = 1004 If console_msg_level >= console_routine_messages2 Then _ Console.WriteLine( routine_name & " " & message_tag & _ ": Returning." ) Return return_code End Function ' Function obj_heap_insert