Remix.run Logo
khedoros1 a day ago

Hmm. I guess I wouldn't have thought it would take 10's of thousands of lines.

Jtsummers a day ago | parent [-]

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.