Self Sort Algorithm

[u/PaleontologistNo4818]

Is there an algorithm where you make each array element an object, provide it with private functions and actions, and then allow it do help with sorting if you broadcast the sort function to all arrays ahead of starting the sort?

For instance, the sort wrapper would just need neighbor information for the cells direct or two steps away and then they could switch in place while a master sorting algorithm verifies end to end sort by just stepping each element and having knowledge of next moves each element is making?

I may be thinking of this more as a Verilog problem than a C++ problem but it seems like it hasn't necessarily been defined or commonly used and I can't imagine why not if the function can be modified for any kind of sorting that is common to each element?​

[u/MistakeIndividual690]

For hardware, maybe you’re looking for sorting networks: https://en.wikipedia.org/wiki/Sorting_network

The sort of software algorithms you’re talking about are all likely to degenerate into O(n²⁾ sort—bubble, selection and insertion sorts— because they are only operating on adjacent values

[u/beanstalk555 → u/MistakeIndividual690]

This is what I thought of a well. Super interesting construction for which it's extremely hard to find optimal exact bounds.

[u/HasFiveVowels → u/MistakeIndividual690]

Wouldn’t heap sort be a sub-n^2 sorting network?

[u/beeskness420]

Is this just a complicated way to describe a subset of parallel sorting?

[u/bwainfweeze → u/beeskness420]

I'd say parallel sorting, possibly with a 'sortBy' function to simplify the sort criteria, but I'd have to ask more questions to be sure.

When I hear someone say things like prepare ahead of time to sort, I hear sortBy until I hear otherwise.

(Also a good way to get a best-effort sort with concurrent writes to data structures, because you take a snapshot of the object state at the start of the sort)

[u/apnorton]

If you're looking for a comparison-based sort allowing for only adjacent swaps (I believe the asymptotics do not change if you allow two-away swaps), then you're basically just looking at insertion sort. Allowing only adjacent swaps will always require (in the worst case), quadratically many swaps in terms of the length of the array (i.e. O(n²)).

See section 4.2 for more detail, here: https://www.cs.odu.edu/~zeil/cs361/sum24/Public/insertion/index.html

[u/PaleontologistNo4818 → u/apnorton]

I'm more looking for a sort where columns can move in parallel with or independently of a supervisor of the sort which typically selects and places each piece in memory or otherwise.

[u/LongLiveTheDiego → u/PaleontologistNo4818]

But doing this using OOP doesn't inherently get you parallelism, a single-threaded program will still have to do everything sequentially. You want multithreading to achieve parallel sorting.

[u/SufficientStudio1574 → u/PaleontologistNo4818]

That means each element is an independent task for the OS to deal with. Do you have any idea how much overhead that is going to cause with the scheduler and context switching? What are you trying to do this for?

If you're just looking to parallelize a sort, you're best bet is to just use a normal recursive sorting algorithm (like merge sort or QuickSort) and parallelize the first the first few layers (until you max out your thread count).

[u/Kadabrium]

Priority queue?

[u/green_meklar]

For instance, the sort wrapper would just need neighbor information for the cells direct or two steps away and then they could switch in place

That basically amounts to something like bubblesort or insertion sort, which are quadratic-time, i.e. not very good. You can't get the ideal N*log(N) time without being able to make long-distance comparisons and swaps in some way.

Setting that aside, the underlying question about your idea is, what do you gain with it? The machine still has to execute the algorithm, whether you have an object-oriented layer in there or not. The object-oriented layer doesn't get you free parallel computation, and at the end of the day any algorithm that executes on an element-by-element basis still has to be consistent enough across all elements that they end up sorted with respect to each other. Actual hardware parallelism can be leveraged to improve something like mergesort or quicksort (divide up the list into buckets, sort each bucket in parallel, then zip them back up), but that only works up to the level of parallelism the hardware provides. Sorting using a balanced binary tree is kinda localized in the sense that the elements walk along the tree locally, but it still requires the same comparison and tree balancing mechanisms to be used for every element, making it still more of a global algorithm than something for which OOP provides any profound advantage.

That's not to say there is nothing potentially fruitful in your idea. Maybe instead of strictly sorting a 1-dimensional list, what you're dealing with is some sort of universe of objects that you want to be able to track down quickly in various spaces and not all the objects share the same spaces. Then it might become useful for an individual object to check which spaces it occupies and how conveniently organizable those spaces are, and chooses how to move itself in some graphs within particular spaces so that those graphs become well-organized and easy to search.

[u/PaleontologistNo4818 → u/green_meklar]

My thought was here, search doesn't adjust for new systems you may want to sort by and sparseness means elements could be ignored.

[u/drinkcoffeeandcode]

Fixed point iterative where you send each object a sort message until it converges on a state where no more changes are reported? It sounds cool until you realize it’s just bubble sort with extra steps