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 thePREV INDEX NEXTS 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-