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
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) 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.