2.2.17 Linked-list sort. Implement a natural mergesort for linked lists. (This i

Question

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.)

-----------------------------------------------------------------------------

package algs13;

import stdlib.*;

// PROBLEM 2.2.17

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 void sort(){ //TODO

       }

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:a1) b2.add(i);

MyLinkedSort.print("before sort",b2);

b2.sort();

MyLinkedSort.print("after sort",b2);

}

}

Explanation / Answer

/*
* Node Declaration
*/
public class node
{
   public int data;
   public node next;
}

public class GlobalMembers
{
node SortedMerge(node a, node b);

/* Split the nodes of the given list into front and back halves*/
   public static void FrontBackSplit(node source, node[] frontRef, node[] backRef)
   {
       node fast;
       node slow;
       if (source == null || source.next == null)
       {
           frontRef = source;
           backRef = null;
       }
       else
       {
           slow = source;
           fast = source.next;
           while (fast != null)
           {
               fast = fast.next;
               if (fast != null)
               {
                   slow = slow.next;
                   fast = fast.next;
               }
           }
           frontRef = source;
           backRef = slow.next;
           slow.next = null;
       }
   }

   /* sorts the linked list by changing next pointers (not data) */
   public static void MergeSort(node[] headRef)
   {
       node head = headRef;
       node a;
       node b;
       if ((head == null) || (head.next == null))
       {
           return;
       }
       FrontBackSplit(head, a, b);
       MergeSort(a);
       MergeSort(b);
       headRef = SortedMerge(a, b);
   }
   /* merge the sorted linked lists */
   public static node SortedMerge(node a, node b)
   {
       node result = null;
       if (a == null)
       {
           return b;
       }
       else if (b == null)
       {
           return a;
       }
       if (a.data <= b.data)
       {
           result = a;
           result.next = SortedMerge(a.next, b);
       }
       else
       {
           result = b;
           result.next = SortedMerge(a, b.next);
       }
       return result;
   }

   /* print nodes in a given linked list */
   public static void printList(node node)
   {
       while (node != null)
       {
           System.out.print(node.data);
           System.out.print(" ");
           node = node.next;
       }
   }

   /* insert a node at the beginging of the linked list */
   public static void push(node[] head_ref, int new_data)
   {
       node new_node = new node();
       new_node.data = new_data;
       new_node.next = head_ref;
       head_ref = new_node;
   }
   /* Main */
   public static int Main()
   {
       node res = null;
       node a = null;
       push(a, 15);
       push(a, 10);
       push(a, 5);
       push(a, 20);
       push(a, 3);
       push(a, 2);
       MergeSort(a);
       System.out.print(" Sorted Linked List is: ");
       printList(a);
       return 0;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.