001package algs22; 002import stdlib.*; 003 004// PROBLEM 2.2.17 005public class MyLinkedSort { 006 static class Node { 007 public Node() { } 008 public double item; 009 public Node next; 010 } 011 012 int N; 013 Node first; 014 015 private void sort() { 016 // TODO 017 } 018 019 public MyLinkedSort () { 020 first = null; 021 N = 0; 022 checkInvariants (); 023 } 024 025 private void myassert (String s, boolean b) { if (!b) throw new Error ("Assertion failed: " + s); } 026 private void checkInvariants() { 027 myassert("Empty <==> first==null", (N == 0) == (first == null)); 028 Node x = first; 029 for (int i = 0; i < N; i++) { 030 if (x==null) { 031 throw new Error ("List too short!"); 032 } 033 x = x.next; 034 } 035 myassert("EndOfList == null", x == null); 036 } 037 038 public boolean isEmpty () { return first == null; } 039 public int size () { return N; } 040 public void add (double item) { 041 Node newfirst = new Node (); 042 newfirst.item = item; 043 newfirst.next = first; 044 first = newfirst; 045 N++; 046 } 047 048 private static void print (String s, MyLinkedSort b) { 049 StdOut.print (s + ": "); 050 for (Node x = b.first; x != null; x = x.next) 051 StdOut.print (x.item + " "); 052 StdOut.println (); 053 } 054 private static void print (String s, MyLinkedSort b, double i) { 055 StdOut.print (s + ": "); 056 for (Node x = b.first; x != null; x = x.next) 057 StdOut.print (x.item + " "); 058 StdOut.println (": " + i); 059 } 060 061 public static void main (String args[]) { 062 int[] a1 = new int[20]; 063 for (int i = 0; i < a1.length; i++) 064 a1[i] = i; 065 StdRandom.shuffle (a1); 066 MyLinkedSort b1 = new MyLinkedSort (); 067 for (int i:a1) b1.add(i); 068 MyLinkedSort.print("before sort",b1); 069 b1.sort(); 070 MyLinkedSort.print("after sort",b1); 071 072 int[] a2 = new int[200]; 073 for (int i = 0; i < a2.length; i++) 074 a2[i] = i; 075 StdRandom.shuffle (a2); 076 MyLinkedSort b2 = new MyLinkedSort (); 077 for (int i:a1) b2.add(i); 078 MyLinkedSort.print("before sort",b2); 079 b2.sort(); 080 MyLinkedSort.print("after sort",b2); 081 082 } 083} 084 085