positionsorter.py

#! python

# Format: (y, x, [userdata], ..)
# Sorterer i stigande rekkefølge
positions = [ (1.0 , 1.1, 1),
              (10.0 , 50.0, 2),
              (9.0 , 39.0, 3),
              (30.0 , 5.0, 4),
              (40.0 , 10.0, 5),
            ]

sorted = []

i = 0
length = len(positions)

# Høgda og vidda som definerer nøyaktigheita på gridden, eller
# kor mykje forskjel mellom posisjon som skal til før det blir rekna
# som om dei ligg i forskjellige gridpunkt.
height = 10
width  = 10

steps = 0

while i < length:
  steps += 1

  sorted.append (positions[i])

  j = i - 1

  c = positions[i] # Current

  while True:
    if j < 0: break

    steps += 1

    p = sorted[j]  # Previous

    if (c[0] < (p[0] - height)):
      # Swap
      tmp = sorted[j]
      sorted[j] = sorted[j+1]
      sorted[j+1] = tmp
      j -= 1
      continue # Check against new previous

    elif ( c[0] >= (p[0] - height) and (c[0] <= (p[0] + height)) ):
      if (p[1] > c[1]):
        # Swap
        tmp = sorted[j]
        sorted[j] = sorted[j+1]
        sorted[j+1] = tmp
        j -= 1
        continue # Check against new previous

      else:
        break # Correct position relative to current previous
    else:
      break # Correct position relative to current previous

  i += 1


print ("Original list:")
for p in positions:
  print (p)

print ()
print ("Sorted list:")
for p in sorted:
  print (p)

print ()
print ("Steps:", steps)