package algs13; import stdlib.*; // PROBLEM 2.2.17 //Linked-list sort. Implement a natural mergesort for linked lists.(This is the method of choice for sorting linked lists because it uses no extra space and is guaranteed to be linearithmic.) public class MyLinkedSort { static class Node { public Node() { } public double item; public Node next; } int N; Node first; public MyLinkedSort () { first = null; N = 0; checkInvariants (); } private void myassert (String s, boolean b) { if (!b) throw new Error (Assertion failed: + s); } private void checkInvariants() { myassert(Empty <==> first==null, (N == 0) == (first == null)); Node x = first; for (int i = 0; i < N; i++) { if (x==null) { throw new Error ("List too short!"); } x = x.next; } myassert("EndOfList == null", x == null); } public boolean isEmpty () { return first == null; } public int size () { return N; } public void add (double item) { Node newfirst = new Node (); newfirst.item = item; newfirst.next = first; first = newfirst; N++; } private static void print (String s, MyLinkedSort b) { StdOut.print (s + ": "); for (Node x = b.first; x != null; x = x.next) StdOut.print (x.item + " "); StdOut.println (); } private static void print (String s, MyLinkedSort b, double i) { StdOut.print (s + ": "); for (Node x = b.first; x != null; x = x.next) StdOut.print (x.item + " "); StdOut.println (": " + i); } private static MyLinkedSort merge(MyLinkedSort left, MyLinkedSort right){ } private void sort(){ // } public static void main (String args[]) { int[] a1 = new int[20]; for (int i = 0; i < a1.length; i++) a1[i] = i; StdRandom.shuffle (a1); MyLinkedSort b1 = new MyLinkedSort (); for (int i:a1) b1.add(i); MyLinkedSort.print("before sort",b1); b1.sort(); MyLinkedSort.print("after sort",b1); int[] a2 = new int[200]; for (int i = 0; i < a2.length; i++) a2[i] = i; StdRandom.shuffle (a2); MyLinkedSort b2 = new MyLinkedSort (); for (int i:a2) b2.add(i); MyLinkedSort.print("before sort",b2); b2.sort(); MyLinkedSort.print("after sort",b2); } }
