Question

This Individual Assignment is a set of three problems. The first is a recursion "warm up" exercise, and the second two are QuickSort variations. The "warm up" should be implemented as a static method in your main App class and the second two will use additional classes (as instructed below). All three problems should be included in the same NetBeans project (exported to ZIP as usual).

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

All of your classes should be properly encapsulated, follow all proper coding conventions discussed in class, and be logically constructed following good Object Oriented design. Your submitted code should compile and run without errors.

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

Problem #1: The Recursion Warm Up (10 points):

Write a recursive method to reverse and capitalize a String. For example:

reverseAndCap("abcdefg3!")

should return:

!3GFEDCBA

Note that non-alphabetic characters are included (but obviously cannot be capitalized).

Also, no points will be given for a non-recursive solution.

Problem #2: The Array CatSort (45 points):

1. Create a "Cat" class with the following attributes:

• Name
• Weight
• Age

Include a constructor and getter methods, and override toString() to display all info (you may let NetBeans do this for you).

2. In your main method, create an array of 5 Cats and initialize their attributes.
3. Implement the QuickSort algorithm (as shown in class) to sort Cats by weight. You may create this as a static recursive method.
4. Display the sorted array contents in main.

Problem #3: The Linked List CatSort (45 points):

1. Modify the Linked List example that you will be given in class into a LinkedCatList class that implements a Linked List of the Cat objects that you created in Problem #2.
2. In your main method, create a LinkedCatList of 5 Cats and initialize their attributes.
3. Create a sort method in your LinkedCatList class that uses QuickSort (implemented by you) to sort the list of Cats alphabetically (lexicographicaly) by Name.
4. Display the sorted list contents in main.

This is the LinkedList Starter code that I am supposed to use for #3

import java.util.NoSuchElementException;

public class LinkedStringList {

private Node first;
private Node currentNode;
private int length;

class Node
{
private String data;
private Node next;

public void printNodeData()
{
System.out.println("Node data: " + data);
}
public Node getNext()
{
return next;
}
}
public LinkedStringList()
{
first = null;
currentNode = null;
length = 0;
}
public void setFirst(String value)
{
first.data = value;
}
public void setCurrent(String value)
{
currentNode.data = value;
}
public void addFirst(String value)
{

//create the Node and set its value
Node newNode = new Node();
newNode.data = value;

// if newNode is the first node, this will be null
// otherwise it will point to the former "first" now
newNode.next = first;

//set our "first" Node to the Node we just created
first = newNode;

currentNode = newNode;

length++;

}

public void removeFirst()
{
if (first == null)
{
throw new NoSuchElementException();
}
else
{
first = first.next;
length--;
}
}

public void remove()
{
if (currentNode == first)
{
removeFirst();
}
else
{
Node tempCurrent = currentNode;
moveFirst();
boolean found = false;
while (!found)
{
if(currentNode.next == tempCurrent)
{
found = true;
}
else
{
moveNext();
}
}

currentNode.next = tempCurrent.next;
}
}

public int indexOf(String value)
{
Node tempNode = first;
int position = 0;

while (tempNode != null)
{
if (tempNode.data == value)
{
return position;
}
else
{
tempNode = tempNode.next;
position++;
}
}

return -1;

}


//adds after currentNode
public void add(String value)
{
if (first == null)
{
addFirst(value);
}
else
{

//create node having "next" pointing to tempSwap
Node newNode = new Node();
newNode.data = value;
newNode.next = currentNode.next;

//make the old current node point to our newNode
currentNode.next = newNode;

//move current refer to node we just added
moveNext();

//increment length of list
length++;
}

}
public boolean isEmpty()
{
return (first == null);
}

public int getLength()
{
return length;
}

public String getFirstValue()
{
if (first == null)
{
throw new NoSuchElementException();
}
else
{
return first.data;
}
}

public String getCurrentValue()
{
if (currentNode == null)
{
throw new NoSuchElementException();
}
else
{
return currentNode.data;
}
}
public void moveNext()
{
currentNode = currentNode.next;
}
public void moveFirst()
{
currentNode = first;
}
public void displayList()
{
Node currentNode = first;
System.out.println("List contents:");
while (currentNode != null)
{
currentNode.printNodeData();
currentNode = currentNode.getNext();
}
}

}

Answer 1

Answer:

programe:

• ############### ReverseString.java ##############

  /**
  * The Class ReverseString.
  */
  public class ReverseString {

     /**
     * The main method.
     *
     * @param args the arguments
     */
     public static void main(String[] args) {
         String str = "abcdefg3!";
         System.out.println("String: " + str);
         System.out.println("Reverse: " + reverseAndCap(str));
     }

     /**
     * Reverse and cap.
     *
     * @param str the str
     * @return the string
     */
     private static String reverseAndCap(String str) {
         if (str.isEmpty())
             return str;
         // Calling Function Recursively
         return (reverseAndCap(str.substring(1)) + str.charAt(0)).toUpperCase();
     }
  }

  ########### output #################

  
  ############### Cat.java ###############

  /**
  * The Class Cat.
  */
  public class Cat implements Comparable<Cat> {

     /** The name. */
     private String name;

     /** The weight. */
     private double weight;

     /** The age. */
     private int age;

     /**
     * Instantiates a new cat.
     *
     * @param name the name
     * @param weight the weight
     * @param age the age
     */
     public Cat(String name, double weight, int age) {
         this.name = name;
         this.weight = weight;
         this.age = age;
     }

     /**
     * Gets the name.
     *
     * @return the name
     */
     public String getName() {
         return name;
     }

     /**
     * Gets the weight.
     *
     * @return the weight
     */
     public double getWeight() {
         return weight;
     }

     /**
     * Gets the age.
     *
     * @return the age
     */
     public int getAge() {
         return age;
     }

     @Override
     public String toString() {
         return String.format("Cat [name=%s, weight=%s, age=%s]", name, weight, age);
     }

     @Override
     public int compareTo(Cat o) {
         return name.compareToIgnoreCase(o.name);
     }

  }

  ########## CatSort.java #############

  /**
  * The Class CatSort.
  */
  public class CatSort {

     /**
     * The main method.
     *
     * @param args the arguments
     */
     public static void main(String[] args) {
         Cat[] cats = { new Cat("Lara", 16.55, 3), //
                 new Cat("Puss", 10.15, 1), //
                 new Cat("Tom", 8.30, 5), //
                 new Cat("Sammy", 19.00, 9), //
                 new Cat("Jess", 26.55, 10) };
         quickSort(cats, 0, cats.length - 1);
         for (Cat cat : cats) {
             System.out.println(cat.toString());
         }
     }

     /**
     * Quick sort.
     *
     * @param cats the cats
     * @param low the low
     * @param high the high
     */
     private static void quickSort(Cat[] cats, int low, int high) {
         if (cats == null || cats.length == 0) {
             return;
         }
         if (low >= high) {
             return;
         }
         int middle = low + (high - low) / 2;
         Cat pivot = cats[middle];
         // make left < pivot and right > pivot
         int i = low, j = high;
         while (i <= j) {
             // Check until all values on left side array are lower than pivot
             while (cats[i].getWeight() < pivot.getWeight()) {
                 i++;
             }
             // Check until all values on left side array are greater than pivot
             while (cats[j].getWeight() > pivot.getWeight()) {
                 j--;
             }
             // Now compare values from both side of lists to see if they need
             // swapping
             // After swapping move the iterator on both lists
             if (i <= j) {
                 swap(cats, i, j);
                 i++;
                 j--;
             }
         }
         // Do same operation as above recursively to sort two sub arrays
         if (low < j) {
             quickSort(cats, low, j);
         }
         if (high > i) {
             quickSort(cats, i, high);
         }

     }

     /**
     * Swap.
     *
     * @param cats the cats
     * @param x the x
     * @param y the y
     */
     public static void swap(Cat[] cats, int x, int y) {
         Cat temp = cats[x];
         cats[x] = cats[y];
         cats[y] = temp;
     }

  }

  
  ############### output #############

  

  ########## LinkedCatList.java ##########

  import java.util.LinkedList;

  /**
  * The Class LinkedCatList.
  */
  public class LinkedCatList {

     /** The cats. */
     private LinkedList<Cat> cats;

     /**
     * Instantiates a new linked cat list.
     */
     public LinkedCatList() {
         this.cats = new LinkedList<>();
     }

     /**
     * Push.
     *
     * @param cat the cat
     */
     public void push(Cat cat) {
         cats.push(cat);
     }

     /**
     * Pop.
     *
     * @return the cat
     */
     public Cat pop() {
         return cats.pop();
     }

     /**
     * Peek.
     *
     * @return the cat
     */
     public Cat peek() {
         return cats.peek();
     }

     /**
     * Size.
     *
     * @return the int
     */
     public int size() {
         return cats.size();
     }

     /**
     * Gets the.
     *
     * @param i the i
     * @return the cat
     */
     public Cat get(int i) {
         return cats.get(i);
     }

     /**
     * Replace.
     *
     * @param i the i
     * @param cat the cat
     */
     public void replace(int i, Cat cat) {
         cats.set(i, cat);
     }
  }
  ################# LinkedCatListSort.java ###########

  /**
  * The Class LinkedCatListSort.
  */
  public class LinkedCatListSort {

     /**
     * The main method.
     *
     * @param args the arguments
     */
     public static void main(String[] args) {
         LinkedCatList catList = new LinkedCatList();
         catList.push(new Cat("Lara", 16.55, 3));
         catList.push(new Cat("Puss", 10.15, 1));
         catList.push(new Cat("Tom", 8.30, 5));
         catList.push(new Cat("Sammy", 19.00, 9));
         catList.push(new Cat("Jess", 26.55, 10));
         quickSort(catList, 0, catList.size() - 1);
         while (catList.size() > 0) {
             System.out.println(catList.pop().toString());
         }
     }

     /**
     * Quick sort.
     *
     * @param list the list
     * @param from the from
     * @param to the to
     */
     public static void quickSort(LinkedCatList list, int from, int to) {
         if (from < to) {
             int pivot = from;
             int left = from + 1;
             int right = to;
             Cat pivotValue = list.get(pivot);
             while (left <= right) {
                 // left <= to -> limit protection
                 while (left <= to && pivotValue.getName().compareToIgnoreCase(list.get(left).getName()) >= 0) {
                     left++;
                 }
                 // right > from -> limit protection
                 while (right > from && pivotValue.getName().compareToIgnoreCase(list.get(right).getName()) < 0) {
                     right--;
                 }
                 if (left < right) {
                     swap(list, left, right);
                 }
             }
             swap(list, pivot, left - 1);
             quickSort(list, from, right - 1); // <-- pivot was wrong!
             quickSort(list, right + 1, to); // <-- pivot was wrong!
         }
     }

     /**
     * Swap.
     *
     * @param list the list
     * @param x the x
     * @param y the y
     */
     public static void swap(LinkedCatList list, int x, int y) {
         Cat temp = list.get(x);
         list.replace(x, list.get(y));
         list.replace(y, temp);
     }
  }

  
  ############# output ############