Earlier quoted context omitted.
I used Timsort in a class around 2010 and it had been in Python for “a long time” at that point. I also tripped on this article’s claim that it didn’t exist yet in 2008.
TIL.
I corrected the article.
Sorting algorithms that don’t hate you
71–80 of 84 posts
Re: Sorting algorithms that don’t hate you
#72[dead]
Re: Sorting algorithms that don’t hate you
#73Any comparison based sorting algo can be made stable. Consider position as a tie breaker.
Most can be done in place with some effort.
Then you need to worry not about asymptotics, but the constant factors. Quicksort has significantly lower operation count than heap sort, even though both are O(nlog n). For small numbers bubble sort is quicker than both (and many good sorts leverage this via hybrid methods). Caches add another massive game changing performance dial to fiddle with.
Taking stock at this level, ignoring that many of the non-green field he chose can be made green, misses important nuance.
Re: Sorting algorithms that don’t hate you
#74Earlier quoted context omitted.
Obviously it may never crash, and it never did, even with a bad comparison function. But the JS engine does not protect against the page containing JS code that loops forever. How would it even do that? Edit: Perhaps some misunderstanding: V8 "just used Quicksort", but it never used the qsort function from the C library. That would not have worked with garbage collection, since you can have a garbage collection in th…
Prior to chrome every browser had a “terminate js after x seconds” option that didn’t mean “kill the process”. But the point is that the general quicksort algorithm does a bunch of unsafe memory accesses if the comparator is unstable (either directly or by modification of the sorted data). As demonstrated by every qsort implementation going wrong in unsafe ways in such a scenario. Now maybe you used a version of qsor…
V8's Quicksort was written in JS so going out of bounds on an array access did the same as it would in any other JS program. As I recall, JS isn't super helpful about out of bounds accesses, but there's nothing memory-unsafe about it.
Re: Sorting algorithms that don’t hate you
#75Let n be a non-negative integer. A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order. Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is…
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 not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. 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).
> 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
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
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++
i = ++j+++++k++
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.
Re: Sorting algorithms that don’t hate you
#76Earlier quoted context omitted.
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 not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. 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).
> 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…
' 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_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 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 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 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 SubRe: Sorting algorithms that don’t hate you
#77Let n be a non-negative integer. A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order. Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is…
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 not a stable sort. But it is really simple (a few lines of code), doesn't use recursion, and is fairly fast. 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).
' 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 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
' = console_routine_messages2 Then _
Console.WriteLine( routine_name & " " & message_tag & _
": Started ..." )
error_code = 1002
If m m Then
return_code = 1003
Goto out
End If
If y.GetUpperBound(0) = 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 ) ) m \ i_2 Then Exit Do
i_child1 = i_father + i_father
If i_child1 = console_routine_messages2 Then _
Console.WriteLine( routine_name & " " & message_tag & _
": Returning." )
Return return_code
End Function ' Function obj_heap_insertRe: Sorting algorithms that don’t hate you
#78Earlier quoted context omitted.
Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
No, there could be unsortable properties that are nonetheless different. Or the use case could really require that the original order is relevant. But yeah, I don't usually need stability either.
Forgive me for sounding like an idiot but how can two properties be different, yet unsortable?
Re: Sorting algorithms that don’t hate you
#79Earlier quoted context omitted.
Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.
I'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.
And allocating O(N) extra memory isn't expensive?