5
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.