8 points | by sharon_golan a day ago ago
4 comments
Hmm. I guess I wouldn't have thought it would take 10's of thousands of lines.
It doesn't, the actually sorting steps take 16 comparisons and up to 16 swaps. This can be implemented with a sorting network as shown here: https://bertdobbelaere.github.io/sorting_networks_extended.h...
In Python, you can use parallel assignments which let you express it easily with something like:
def sort7(l): if l[0] > l[6]: l[0], l[6] = l[6], l[0] # repeat for each comparison return l
You could even just generate the code or run the network using the representation from that site:
[(0,6),(2,3),(4,5)] [(0,2),(1,4),(3,6)] [(0,1),(2,5),(3,4)] [(1,2),(4,6)] [(2,3),(4,5)] [(1,2),(3,4),(5,6)]
for layer in layers: for a, b in layer: if l[a] > l[b]: l[a], l[b] = l[b], l[a]
[flagged]
Hmm. I guess I wouldn't have thought it would take 10's of thousands of lines.
It doesn't, the actually sorting steps take 16 comparisons and up to 16 swaps. This can be implemented with a sorting network as shown here: https://bertdobbelaere.github.io/sorting_networks_extended.h...
In Python, you can use parallel assignments which let you express it easily with something like:
That'd be 16 lines + 1 for the function definition + 1 for the return.You could even just generate the code or run the network using the representation from that site:
If that's in a data structure called layers: I'm also pretty sure that a brute force "unrolling" of bubble sort would have resulted in fewer lines. There shouldn't be more than 21 comparisons needed for 7 elements.[flagged]