For this assignment you are to write program that sorts the cars on a train. Consider the

Fantastic news! We've Found the answer you've been seeking!

Question:

For this assignment you are to write program that sorts the cars on a train. Consider the following diagram of a train track.

Cars come in from the left and exit on the right hand side. They can also move onto the "siding" track to the bottom. At the intersection, each car on the input train can either move to the exit track or onto the siding. From the siding, each car can either move to the exit track or back onto the input track. And finally, from the exit track, a car can move back to the input or siding tracks. The input, output, and siding tracks are stacks, since you can only access the car at the head of the track (as viewed from the intersection point). All tracks are at least as long as the input train.

Given an input sequence of cars, your program should sort the cars of the train so that the exit track is in order. To do, the following classes already exist:

public class Car implements Comparable { String toString(); // String representation int compareTo(Car other); // compares two cars }

public enum Track { INPUT, OUTPUT, SIDING; }

public class TrainYard { public TrainYard(int [] cars); // build a train from the int array of cars public Car frontOf(Track track); // peek at the front of a track, returns null if empty public void move(Track from, Track to); // move the front car from one track to another public String toString(); // String representation of the current train yard }

The following code demonstrates how you might use the TrainYard to move all the input cars directly to the output track:

public class RunMe { public static void main(String [] args) { int [] cars = {1, 2, 3, 4, 5}; TrainYard yard = new TrainYard(cars); System.out.println(yard); while (yard.frontOf(Track.INPUT) != null) { yard.move(Track.INPUT, Track.OUTPUT); } System.out.println(yard); } }

This would yield the following output

INPUT: [Car #1, Car #2, Car #3, Car #4, Car #5] OUTPUT: [] SIDING: [] INPUT: [] OUTPUT: [Car #5, Car #4, Car #3, Car #2, Car #1] SIDING: [] Moves so far: 1. Move Car #5 from Input to Output 2. Move Car #4 from Input to Output 3. Move Car #3 from Input to Output 4. Move Car #2 from Input to Output 5. Move Car #1 from Input to Output

Printing out the yard will show both the current state of the tracks and the moves that got you there.

Hint: There are a couple of approaches you can take from an algorithmic perspective. Here is just one approach that is analogous to insertion sort.

Look at the front car on the input track

Slide cars less than the input car from the output onto the siding (or cars greater than it from the siding to the output).

Move the car from input to output.

Repeat until the input and siding tracks are empty.

Here's another approach analogous to an selection sort:

Find the largest car on the input track by moving them all to the siding and tracking the maximum one.

Slide all the cars back from the siding to the input and when the maximum one is encountered, move it instead to the output track.

Repeat until the input and siding tracks are empty

public class TrainSorter { public void sort(TrainYard yard) { // Note that you can System.out.println(yard) for debugging. // insert your code here. } }