Yes you are correct, I didn't. It was not my priority, this was just a personal project, plus any amount of graphs I did could always be shown I was missing a sample set test graph. While I am working on it I wanted to focus on understanding the algorithm before making it public, and comparing it to everything else out there.
Plus giving ppl a stable/workable framework to download and test on any dataset they want seems a better approach. From all my testing, here is the stat I think that is most relevant when it comes to Condor sorting algorithm.
Quicksort : 34182 swaps vs Condor : 21810 swaps on same 10,000 item data set. The is pretty much regardless of data set, ordered, unordered, reversed, same values, limited values, at least in my tests. The framework will work on iOS, MacOS, simulator, device and both Objective C and Swift. I am still working on a swift version. It took me a couple of days just to decide how I wanted to build it since the Objective C version works on C arrays and Objective C objects.
This is what the entry point for the Swift version I am working on looks like right now. All just tests and tweaks. The first version used protocols and I hated it cause it meant objects and structs had to be changed to conform. Finding this discussion is awesome since now I can understand more use cases than my own and then maybe be able to build something that is usable for others.
let output = condorSort.sort(array:array, descending: false, property: { Int32($0.condorId) })
Thanks for bringing this topic back up @thomasrunner! I'd love to see the code for your sort when you're finished with it.
With regards to this pitch, I think that we should probably write it up at some point. We have an partial implementation by @nnnnnnnn (I'm not sure if it's complete, though, so we might have to work on it), so now might be a good time to work on a formal proposal. I'm up to do it if nobody's worked on this.
Sorry for the very delayed response. I do plan to make it more public I as work through the missing functionality like double, 64bit Ints and native swift framework. It is a side project so I get to it whenever I can. Good thing I came across this discussion otherwise I would have just wasted my time probably making silly animated gif's of it sorting ;)
Hi @saagarjha ā I don't think it makes sense for anyone to be writing a proposal separate from the implementation. The proposal is honestly the simple part. What is needed is an investigation of what implementations are possible, how a stable sort can compare performance-wise to our current sort with different types and inputs, and whether even greater gains can be made with an unstable sort to justify a second sort function in the std lib. Whoever works works on the candidate implementation (possibly multiple collaborators) should then be co-authors of the proposal but I don't think we should separate those into different tasks.
@Ben_Cohen that clarity helps. I just have a work in progress algorithm that has shown to outperform all those mentioned in previous points which I thought might be of interest to the community. @saagarjha I have just finished Double and Int64 support in ObjC, so now I can fully focus on the Swift version. While I am working on the Swift version I will run my usually small mountain of data set tests on both Doubles and Int64 to ensure their accuracy and stability (ensure not crashing, not sort stability). Performance for both is so impressive that I now fully believe this can also be used on fixed length strings as well with exceptional performance.
No more than a RADIX algorithm. It is not a pure comparative algorithm.
The algorithm grew from me testing smaller data values usually 16bit (for another side project), and quite honestly I wasn't sure if it would work so I kept testing different types.
Um, I don't think that will work out. We're going to have to rely on comparisons since sort() is generic over elements that are Comparable; we can't guarantee anything more about the elements.
no problems, thought I would at least share. I will still finish the Swift and Objc frameworks and make it available to anyone who has that specific need and can be type specific. I would think that narrowing the options of algorithms to either stable or unstable and exclusively comparative seems very restrictive and limiting in available algorithms to discuss.
Although it does raise the possibility of a āRadixSortableā protocol, which would be to Comparable what Hashable is to Equatable. This new protocol would define an Int property that must be compatible with the ordering from Comparable, though collisions are allowed.
Then we could implement a specialized version of Sort for āRadixSortableā types, which might be faster.
I tried the protocol implementation, which seems like overkill demand on devs. The line above accomplishes the same thing with just a closure just like the sort method but with a single property rather than comparing 2 generics.
RADIX uses a lot of memory and has issues sorting a lot of repeated numbers.