PREV INDEX NEXT

Author: Stan Eisenstat
Subject: Re: [Cs223] Stable sorting
Date: Monday, 30 Mar 2020, 15:40:50


    > Message Posted By: Unknown
    >
    > I'm completely stuck on implementing stable sorting and I have no idea
    > where to start. Do you have any advice for getting started on stable
    > sorting?

A stable sorting algorithm is one where items with equal
keys appear in the same relative order in the output as
they appeared in the input.  That is, when splitting, if
S is the splitter and L is the line being assigned to a
group, L must be assigned to the S group if it
appeared later.

You know the order in which the lines read appear on the
stack or queue where you placed them initially.  And you
know how that order changes when you move the lines from
a stack or queue to a stack or queue.  Thus you should be
able to figure out the order in the stack or queue you
are splitting from.

You may find it useful to simulate your algorithm using
a set of cards.

--Stan-
PREV INDEX NEXT