Follow up to Selection sort with reduced comparison count - semi-final Iteration?
My goal (and excuse not to tag reinventing…) is to have presentable code to argue the viability of reducing the number of comparisons used by selection sort (for readers not necessarily versed in the implementation language chosen).
In this iteration, that is prominently MinMax.iteration() and from Keeper the methods iteration, prepare, put and put2, including intrusive comparison accounting for emphasis (and the possible addition of MinMax.get_comparisons() for computing the number of operations of interest).
Note to reviewers of previous iterations: finding suggestions not followed, be assured they were not ignored - feel free to chat (or flame) me, regardless.
'''
selection sort implementations to show how to reduce
the number of comparisons (and input traversals).
Ideas:
- exploit finding min and max of n items in 3n/2 comparisons
- avoid repeating "input pair comparisons"
If and when indulging in (micro-)benchmarking,
be sure to use an appropriate framework
- and compare lemons to lemons.
'''
import logging
# demonstration code - you won't see production code for such
# - nobody rolls her own sort
# - for input where reduced comparisons do outweigh increased setup cost,
# a sub-quadratic sort promises to do even better
# - the related heap sort is "worst-case efficient"
# @functools.total_ordering didn't help, in the end:
# "composed" operators are "tracked" more than once
class ComparisonTracker:
''' call track() for each use of a comparison operator '''
def track(self):
pass # logging.debug("useless tracker")
def __lt__(self, other):
self.track()
return super().__lt__(other)
def __le__(self, other):
self.track()
return super().__le__(other)
def __eq__(self, other):
self.track()
return super().__eq__(other)
def __ge__(self, other):
self.track()
return super().__ge__(other)
def __gt__(self, other):
self.track()
return super().__gt__(other)
def __ne__(self, other):
self.track()
return super().__ne__(other)
# "interface"
class Sorter:
''' In-place sorter. '''
def sort(self):
''' Sort items in place. '''
raise NotImplementedError("Sorters better know how to sort")
class LoCoSelectionSorter(Sorter):
''' In-place selection sorter striving for a low comparison count. '''
def get_assignments(self, items):
raise NotImplementedError("LoCoSelectionSorters better know how to "
"report the number of assignments")
def get_comparisons(self, items):
raise NotImplementedError("LoCoSelectionSorters better know how to "
"report the number of comparisons")
# This class used to be an abstraction of implementations
# - keeping an attribute "items"
# - "knowing" the number of "assignments" to items (#of __setitem__()-calls)
# open coding keeping track thereof interfered with the purpose
# "show how to reduce the number of comparisons"
# - provide for swap given two indices (ended up used up to once per sort)
# - define "sort" an operation of repeated "iteration"s from 0 to a "limit"
# returned by a "prepare" step
# (with a "trace" suitable after prepare() and each iteration())
# The name is preposterous with assignment accounting removed.
class TallyAssignments(LoCoSelectionSorter):
def get_assignments(self, items):
''' Get number of assignments to self.items. '''
return self.items.assignments
def __init__(self, items):
self.items = items
def value_at(self, i):
''' Return the (key value of the) item at i. '''
return self.items[i]
def trace(self, sor):
pass
def swap(self, i, j):
if i != j:
items = self.items
items[j], items[i] = items[i], items[j]
def prepare(self):
''' Prepare iterations of self.items
returning first index not to process "going upwards"
''' # ? and destination index for the first max (after) ?
raise NotImplementedError("TallyAssignments better know how to "
"prepare iteration of items")
def iteration(self, lo_dest): # , hi_dest):
''' Iterate (the unordered part of) self.items once. '''
raise NotImplementedError("TallyAssignments better know how to "
"iterate items")
def put(self, dest, value):
''' Put value in self.items replacing the one at dest,
keeping invariants as needed.
'''
self.items[dest] = value
def put2(self, dest1, value1, dest2, value2):
''' put two values in self.items
replacing the ones at the destinations specified,
keeping invariants as needed.
'''
self.put(dest1, value1)
self.put(dest2, value2)
def sort(self):
''' Override: In-place low comparison count selection sort. '''
if not self.items or len(self.items) < 2:
return
limit = self.prepare()
self.trace(self)
for forward in range(limit):
self.iteration(forward)
self.trace(self)
# def order(items):
# ''' In-place low comparison count selection sort. '''
# sorter = Keeper(items)
# sorter.sort()
# return sorter
class MinMax(TallyAssignments):
''' Find both min and max in one traversal.
Avoid about one quarter of the naive comparisons.
'''
def __init__(self, items):
super().__init__(items)
self.comparisons = 0
def get_comparisons(self, items):
'''Override.'''
logging.debug("%d computed: %d", len(items),
(((self.last - 3) * (self.last - 1)) * 3) / 8 + 2*self.last
+ (self.last if 1 & len(items) else -1))
# logging.debug("counted by naked code: %d", self.comparisons)
# logging.debug("overridden __setitem__: %d",
# ComparisonTrackingInt.comparisons)
return ComparisonTrackingInt.comparisons
def prepare(self):
'''Override.'''
n_items = len(self.items)
last = self.last = n_items - 1
if n_items & 1:
# for odd(length) arrays, find max and get it out of the way
# so only pairs need to be considered ever after
# max_index = max_index(self.items)[1]
max_index = max(range(n_items), key=self.value_at)
self.comparisons += last
self.swap(max_index, last)
self.last -= 1
return len(self.items) // 2
def min_max_indices(self, lo_dest, hi_dest):
''' Find indices of minimum and maximum. '''
items = self.items
start, beyond = (lo_dest, lo_dest+1) if (items[lo_dest]
< items[lo_dest+1]) else (lo_dest+1, lo_dest)
self.comparisons += 1
for forward in range(lo_dest+2, hi_dest, 2):
if items[forward] < items[forward+1]:
if items[forward] < items[start]:
start = forward
if items[beyond] < items[forward+1]:
beyond = forward+1
else:
if items[forward+1] < items[start]:
start = forward+1
if items[beyond] < items[forward]:
beyond = forward
# self.comparisons += 3;
self.comparisons += (3 * (hi_dest - lo_dest - 1)) // 2
return start, beyond
def iteration(self, lo_dest):
'''Override.'''
hi_dest = self.last - lo_dest
lo, hi = self.min_max_indices(lo_dest, hi_dest)
items = self.items
# the tricky part is three elements moving
if lo == lo_dest: # min does not move
if hi != hi_dest: # max moves
ex = items[hi]
self.put(hi, items[hi_dest])
items[hi_dest] = ex
# else nothing moves
else: # min moves
mini = items[lo]
if lo == hi_dest: # max stays in place
self.put(lo, items[lo_dest])
else: # both move
maxi = items[hi]
if lo == hi_dest: # min comes from hi_dest
if hi != lo_dest: # max from in between
self.put(hi, items[lo_dest])
# else min and max get exchanged (never with Keeper)
else: # min from in between
if hi == lo_dest: # max comes from lo_dest
self.put(lo, items[hi_dest]) # (never with Keeper)
else:
self.put2(lo, items[lo_dest], hi, items[hi_dest])
items[hi_dest] = maxi
items[lo_dest] = mini
pass
# exact number of comparisons is data dependant
class Keeper(MinMax):
''' Keep pairs ordered to avoid about half the naive comparisons. '''
def put(self, destination, value):
''' Override: order <code>value</code> conceptually at
<code>destination</code> and the value at its
"mirror-position" in self.items
(such that the lower value is at the lower index).
'''
mirror = self.last - destination
# destination == mirror only with an odd number of unordered items
if ((value < self.items[mirror]) == (destination < mirror)):
self.items[destination] = value
else:
self.items[destination] = self.items[mirror]
self.items[mirror] = value
self.comparisons += 1
def put2(self, dest1, val1, dest2, val2):
''' Override: order val1 conceptually at dest1, val2 conceptually at
dest2 and the values at their "mirror-positions" in self.items
(have the lower value of each pair at the lower index).
dest1 shall be smaller than dest2.
'''
mirror = self.last - dest1
if mirror != dest2:
self.put(dest1, val1)
self.put(dest2, val2)
return
items = self.items
items[dest1], items[dest2] = (val1, val2) if val1 <= val2\
else (val2, val1)
self.comparisons += 1
def prepare(self):
''' Override: prepare iterations of self.items.
Return first index not to process "going upwards".
Resets <code>comparisons</code>.
''' # and destination index for the first max (after)?
items = self.items
n_items = len(items)
middle = n_items // 2
last = self.last = middle * 2 - 1
# place lower(higher) "buddies" at the lower(higher) index,
# never to be compared again unless at least one gets replaced.
for forward in range(middle):
# put(forward, items[forward]) instead would at least
# spare everyone discussing names u, d and outlasting this loop
# (the catch being avoidable assignments)
u = items[forward]
d = items[last - forward]
if d < u:
items[forward] = d
items[last - forward] = u
# for odd(length) arrays, determine max and get it out of the way
# so only pairs need to be considered ever after
if n_items & 1:
max_index = max(range(middle, n_items), key=self.value_at)
self.comparisons = last
if max_index <= last:
maxVal = items[max_index]
self.put(max_index, items[last+1])
items[last+1] = maxVal
else:
self.comparisons = middle
# when there are just two elements left, they are already ordered
return middle - 1
def min_max_indices(self, lo_dest, hi_dest):
'''Override.'''
lo = lo_dest
middle = len(self.items) // 2
for forward in range(lo_dest+1, middle):
if self.items[forward] < self.items[lo]:
lo = forward
hi = hi_dest
for forward in range(middle, hi_dest):
if self.items[hi] < self.items[forward]:
hi = forward
self.comparisons += hi_dest - lo_dest - 1
return lo, hi
class PlainSelection(TallyAssignments):
''' Plain selection sort for reference. '''
def prepare(self):
return len(self.items)-2
def iteration(self, lo_dest):
self.swap(lo_dest, max(range(lo_dest, len(self.items)),
key=self.value_at))
# ToDo:
# comparison reduction along TAoCP 5.2.3 Ex. 8 (& combinations?)
# realistic heap sort for reference
# only miscellanea to follow
class ComparisonTrackingInt(ComparisonTracker, int):
def track(self):
ComparisonTrackingInt.comparisons += 1
comparisons = 0
class AssignmentTrackingList(list):
def __init__(self, iterable):
super().__init__(iterable)
self.assignments = 0
def __setitem__(self, key, value):
super().__setitem__(key, value)
self.assignments += 1
def main(): # to keep the global namespace clean
import random
nItems = 19 # 19
items = AssignmentTrackingList(ComparisonTrackingInt(
random.randint(10, 99)) for r in range(nItems))
check = items[:]
print(items # , max(items) # beware comparisons
)
sorter = Keeper(items)
if 0 == len(logging.root.handlers):
debug_level = getattr(logging, "DEBUG", None)
logging.basicConfig(level=debug_level)
# sorter.trace = lambda sor: logging.root.debug(sor.items)
sorter.sort()
print(sorter.get_comparisons(items),
" (", items == sorted(check), ')', sep='')
if __name__ == "__main__":
main()
- Ideas to organise the code to make the parts mentioned as "prominent" in the introduction "eye-catching"?
- Additional ideas for reducing the number of comparisons in selection sort (short of mutating into hybrids with "well-known" sub-quadratic algorithms) welcome.
