• undefined 21 hours ago
    [deleted]
    • khedoros1 21 hours ago

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

      • Jtsummers 21 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.
      • pestatije 21 hours ago

        [flagged]