Sorting 7 elements using only if-else statements in Python

5 pointsposted 20 hours ago
by sharon_golan

4 Comments

user

20 hours ago

[deleted]

khedoros1

20 hours ago

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

Jtsummers

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.