Out of curiosity, I decided to try devising aggregating variants on two of the simpler sorts: the short-circuiting version of BubbleSort, and Gnome Sort, in both the basic and 'teleporting' variants. They aren't really all that interesting in and of themselves, but I wanted to see how it altered best-case performance. I figure that if nothing else, they would serve as a sort of baseline for the effect that this sort of modification would have.
I thought I would share the ones I have done already before going any further. If anyone is curious, I can post both the instrumented test versions of these (and the base algorithms for comparison) and a log of some trials as an attachment.
Code: Select all
def musterSort(data):
"""muster sort - an accretive (or aggregating) variant of the
optimized bubblesort.
I chose the name because repeated elements aggregate into a
'troop' or 'squadron' which moves together from then on."""
endpoint = len(data)
for iter in range(endpoint):
sorted = True
tagged = 0
for pos in range(1, endpoint - iter):
diff = data[tagged] - data[pos]
if diff != 0:
if diff > 0:
data[pos], data[tagged] = data[tagged], data[pos]
sorted = False
tagged = pos
pos += 1
if sorted:
break
return dataCode: Select all
def smurfSort(data):
""" an aggregating variant of a Gnome Sort
Basically, gnomes that congregate in a village..."""
tagged, pos = 0, 1
endpoint = len(data)
direction = 1
while pos < endpoint:
if pos == 0:
direction = 1
tagged, pos = 0, 1
diff = (data[tagged] - data[pos]) * direction
if diff < 0:
tagged = pos
elif diff > 0:
data[tagged], data[pos] = data[pos], data[tagged]
tagged, pos = pos, tagged
direction = -direction
else:
pass
pos += direction
return dataCode: Select all
def bamfSort(data):
""" an aggregating version of the 'optimized' Gnome Sort
Probably only X-Men fans of old will get the name."""
def innerBamfSort(top):
pos, tagged = top-1 , top
while pos >= 0 and data[pos] >= data[tagged]:
if data[tagged] != data[pos]:
data[tagged], data[pos] = data[pos], data[tagged]
tagged = pos
pos -= 1
for pos in range(len(data)):
innerBamfSort(pos)
return data
