user
20 hours ago
[deleted]
20 hours ago
20 hours ago
Hmm. I guess I wouldn't have thought it would take 10's of thousands of lines.
20 hours ago
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
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:
[(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)]
If that's in a data structure called layers: for layer in layers:
for a, b in layer:
if l[a] > l[b]: l[a], l[b] = l[b], l[a]
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.20 hours ago
[flagged]