Question

Complete the java code as per the comments public class Sorting {    ///////////////////////////////////////////////    //...

Complete the java code as per the comments

public class Sorting
{
   ///////////////////////////////////////////////
   // STEP 1 -- Make sorting methods generic
   ///////////////////////////////////////////////
  
   /**
   * Re-orders the contents given array using the insertion sort algorithm.
   *
   * @param data The array to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void insertionSort(int[] data)
   {
       int insert; // temporary variable to hold element to insert
      
       // loop over data.length - 1 elements
       for (int next = 0; next < data.length; next++)
       {
           insert = data[ next ]; // store value in current element
           int moveItem = next; // initialize location to place element
         
           // shift items in the sorted part of the array to make room for next element
           // making sure we don't step off the front of the array
           while (moveItem > 0 && data[ moveItem - 1 ] > insert)
           {   
               data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
               moveItem--;
           }
         
           data[ moveItem ] = insert; // place inserted element
       }
   }
  
   /**
   * Sorts passed data using Merge Sort by modifying the input array.
   *
   * @param data The data to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void mergeSort(int[] data)
   {
       mergeSortHelper(data, 0, data.length - 1);
   }
  
   /**
   * Recursive helper method for mergeSort.
   * @param data The data in which the sub-array is located
   * @param left Lower index of the sub-array.
   * @param right Upper index of the sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void mergeSortHelper(int[] data, int left, int right)
   {
       //General Case: The sublist has at least one item in it.
       if ((right - left) >= 1)  
       {
           int middle1 = (left + right) / 2;
           int middle2 = middle1 + 1;
          
           mergeSortHelper(data, left, middle1);
           mergeSortHelper(data, middle2, right);

           merge(data, left, middle1, middle2, right);
       }
   }
  
   /**
   * Helper method for merge sort. Merges two sub-arrays into sorted order.
   *
   * @param data The data in which the sub-arrays are located
   * @param left Lower index of first sub-array.
   * @param middle1 Upper index of first sub-array.
   * @param middle2 Lower index of second sub-array.
   * @param right Upper index of second sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void merge(int[] data, int left, int middle1, int middle2, int right)
   {
       int leftIndex = left;                   // Local variables for tracking left and right
       int rightIndex = middle2;               // while merging.
      
       int[] combined = new int[data.length];   // A temporary place where we can store our merged results
      
       int combinedIndex = left;       //The position we are at filling up combined
      
       // As long as both subarray pieces have data still in them,
       // we need to keep picking the next smallest from the start
       // of each and putting it into combined
       while (leftIndex <= middle1 && rightIndex <= right)
       {
           // Is the first item of the left subarray smaller?
           if (data[leftIndex] <= data[rightIndex])
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
           // Or is the first item in the right one smaller?
           else
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }

       // If the left sub-array has run out of values, we need
       // to go through emptying the remainder from the right
       if (leftIndex == middle2)
       {
           while (rightIndex <= right)
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }
       // Otherwise, check whether the right one is empty and
       // grab any remaining values from the left sub-array
       else
       {
           while (leftIndex <= middle1)
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
       }
          
       // Lastly, copy the merged array values back into the
       // original input array so it will be sorted after
       // returning from merge.
       for (int i = left; i <= right; i++)
       {
           data[i] = combined[i];
       }      
   }
  
   ///////////////////////////////////////////////////////
   // STEP 2 - Refactor Insertion Sort
   //
   //TODO: Write the helper method described below and then
   // simplify insertionSort to eliminate duplicate code
   ///////////////////////////////////////////////////////
  
   /**
   * insertionSortRange is a generic method that allows for
   * sorting a sub-range of Comparable array values using the
   * insertion sort algorithm.
   *
   * Ranges are specified with the parameters left and right,
   * which are inclusive.
   *
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Write the method header and body for insertionSortRange here

  
   //////////////////////////////////////////////////////
   // STEP 3 - Complete TimSort
   //////////////////////////////////////////////////////
  
   /**
   * timSort is a generic sorting method that sorts an array of Comparable
   * data using the TimSort algorithm. Make sure this method is public so
   * that we can test it.
   *
   * @param data The array of data to be sorted
   */
   //TODO: Write the method header for timSort here. Just uncomment the body, do not edit it.
   /*
   {
       timSortHelper(data, 0, data.length - 1);
   }
   */
  
  
   /**
   * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
   * data using the TimSort algorithm. This method should be public for testing purposes
   * but would normally be private.
   *
   * Ranges are specified with the parameters left and right,
   * which are inclusive.
   *
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Now write the header and body of the timSortHelper method as described
   // for the algorithm.
  
  
  
}

Homework Answers

Answer #1
import java.util.*;


public class T
{
   ///////////////////////////////////////////////
   // STEP 1 -- Make sorting methods generic
   ///////////////////////////////////////////////
   
   /**
   * Re-orders the contents given array using the insertion sort algorithm.
   * 
   * @param data The array to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void insertionSort(Comparable[] data) 
   {
       Comparable insert; // temporary variable to hold element to insert
       
       // loop over data.length - 1 elements
       for (int next = 0; next < data.length; next++) 
       { 
           insert = data[ next ]; // store value in current element
           int moveItem = next; // initialize location to place element
         
           // shift items in the sorted part of the array to make room for next element
           // making sure we don't step off the front of the array
           while (moveItem > 0 && greaterThan(data[moveItem-1], insert)) 
           {   
               data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
               moveItem--;
           } 
         
           data[ moveItem ] = insert; // place inserted element
       }
   }
   
   private static boolean greaterThan(Comparable left, Object right)
        { return left.compareTo(right) == 1; }
        
    private static boolean lessThan(Comparable left, Object right)
        { return left.compareTo(right) == -1; }
        
    private static boolean greaterThanEqual(Comparable left, Object right)
        { return left.compareTo(right) >= 0; }
    
    private static boolean lessThanEqual(Comparable left, Object right)
        { return left.compareTo(right) <= 0; }
   
   /**
   * Sorts passed data using Merge Sort by modifying the input array. 
   * 
   * @param data The data to be sorted.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   public static void mergeSort(Comparable[] data)
   {
       mergeSortHelper(data, 0, data.length - 1);
   }
   
   /**
   * Recursive helper method for mergeSort.
   * @param data The data in which the sub-array is located
   * @param left Lower index of the sub-array.
   * @param right Upper index of the sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void mergeSortHelper(Comparable[] data, int left, int right)
   {
       //General Case: The sublist has at least one item in it.
       if ((right - left) >= 1)   
       {
           int middle1 = (left + right) / 2;
           int middle2 = middle1 + 1;
           
           mergeSortHelper(data, left, middle1);
           mergeSortHelper(data, middle2, right);

           merge(data, left, middle1, middle2, right);
       }
   }
   
   /**
   * Helper method for merge sort. Merges two sub-arrays into sorted order.
   * 
   * @param data The data in which the sub-arrays are located
   * @param left Lower index of first sub-array.
   * @param middle1 Upper index of first sub-array.
   * @param middle2 Lower index of second sub-array.
   * @param right Upper index of second sub-array.
   */
   //TODO: Make me generic to work on any kind of Comparable data!
   private static void merge(Comparable[] data, int left, int middle1, int middle2, int right)
   {
       int leftIndex = left;                   // Local variables for tracking left and right
       int rightIndex = middle2;               // while merging.
       
       Comparable[] combined = new Comparable[data.length];   // A temporary place where we can store our merged results 
       
       int combinedIndex = left;       //The position we are at filling up combined
       
       // As long as both subarray pieces have data still in them, 
       // we need to keep picking the next smallest from the start
       // of each and putting it into combined
       while (leftIndex <= middle1 && rightIndex <= right)
       {
           // Is the first item of the left subarray smaller?
           if (lessThanEqual(data[leftIndex], data[rightIndex]))
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
           // Or is the first item in the right one smaller?
           else 
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }

       // If the left sub-array has run out of values, we need
       // to go through emptying the remainder from the right
       if (leftIndex == middle2)
       {
           while (rightIndex <= right)
           {
               combined[combinedIndex++] = data[rightIndex++];
           }
       }
       // Otherwise, check whether the right one is empty and 
       // grab any remaining values from the left sub-array
       else
       {
           while (leftIndex <= middle1)
           {
               combined[combinedIndex++] = data[leftIndex++];
           }
       }
           
       // Lastly, copy the merged array values back into the 
       // original input array so it will be sorted after
       // returning from merge.
       for (int i = left; i <= right; i++)
       {
           data[i] = combined[i];
       }       
   }
   
   ///////////////////////////////////////////////////////
   // STEP 2 - Refactor Insertion Sort
   //
   //TODO: Write the helper method described below and then 
   // simplify insertionSort to eliminate duplicate code
   ///////////////////////////////////////////////////////
   
   /**
   * insertionSortRange is a generic method that allows for
   * sorting a sub-range of Comparable array values using the 
   * insertion sort algorithm. 
   * 
   * Ranges are specified with the parameters left and right, 
   * which are inclusive.
   * 
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Write the method header and body for insertionSortRange here
    public static void insertionSortRange(Comparable[] data, int left, int right) 
    { 
        for (int i = left; i <= right; i++)  
        { 
            Comparable temp = data[i]; 
            int j = i - 1; 
            while (j >= left && lessThan(data[j] , temp))  
            { 
                data[j + 1] = data[j]; 
                j--; 
            } 
            data[j + 1] = temp; 
        } 
    } 

   
   //////////////////////////////////////////////////////
   // STEP 3 - Complete TimSort
   //////////////////////////////////////////////////////
   
   /**
   * timSort is a generic sorting method that sorts an array of Comparable
   * data using the TimSort algorithm. Make sure this method is public so
   * that we can test it.
   * 
   * @param data The array of data to be sorted
   */
   //TODO: Write the method header for timSort here. Just uncomment the body, do not edit it.
   
   
      // public static void timSortHelper(T[] data, 0, data.length - 1);
   
  
   
   
   /**
   * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
   * data using the TimSort algorithm. This method should be public for testing purposes
   * but would normally be private.
   * 
   * Ranges are specified with the parameters left and right, 
   * which are inclusive.
   * 
   * @param data The array of data to sort
   * @param left The index of the left-most position to sort
   * @param right The index of the right most position to sort
   */
   //TODO: Now write the header and body of the timSortHelper method as described
   // for the algorithm.
   
        static int MIN_MERGE = 32; 
  
    public static int minRunLength(int n) 
    { 
        assert n >= 0; 
        
        // Becomes 1 if any 1 bits are shifted off 
        int r = 0; 
        while (n >= MIN_MERGE)  
        { 
            r |= (n & 1); 
            n >>= 1; 
        } 
        return n + r; 
    } 
    public static void timSortHelper(Comparable[] data, int left, int right) 
    { 
         int minRun = minRunLength(MIN_MERGE); 
         int z = right-left+1;
        
        // Sort individual subarrays of size RUN 
        for (int i = 0; i < z; i += minRun) 
        { 
            insertionSortRange(data, i, 
                          Math.min((i + 31), (z - 1))); 
        } 
  
        // Start merging from size  
        // RUN (or 32). It will 
        // merge to form size 64,  
        // then 128, 256 and so on 
        // .... 
        for (int size = minRun; size < z; size = 2 * size)  
        { 
  
            // Pick starting point  
            // of left sub array. We 
            // are going to merge  
            // arr[l..l+size-1] 
            // and arr[l+size, l+2*size-1] 
            // After every merge, we  
            // increase l by 2*size 
            for (int l = 0; l < z;  
                                 l += 2 * size)  
            { 
  
                // Find ending point of left sub array 
                // mid+1 is starting point of right sub 
                // array 
                int mid = l + size - 1; 
                int r = Math.min((l + 2 * size - 1), 
                                     (z - 1)); 
  
                // Merge sub array arr[l.....mid] & 
                // arr[mid+1....r] 
                merge(data, l, mid,mid+1, r); 
            } 
        } 
    } 
    
   
}
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Finish the code wherever it says TODO /**    * Node type for this list. Each...
Finish the code wherever it says TODO /**    * Node type for this list. Each node holds a maximum of nodeSize elements in an    * array. Empty slots are null.    */    private class Node {        /**        * Array of actual data elements.        */        // Unchecked warning unavoidable.        public E[] data = (E[]) new Comparable[nodeSize];        /**        * Link to next node.       ...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Java Program: You will be inserting values into a generic tree, then printing the values inorder,...
Java Program: You will be inserting values into a generic tree, then printing the values inorder, as well as printing the minimum and maximum values in the tree. Given main(), write the methods in the 'BSTree' class specified by the // TODO: sections. There are 5 TODOs in all to complete. Ex: If the input is like ferment bought tasty can making apples super improving juice wine -1 the output should be: Enter the words on separate lines to insert...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial capacity of the ArrayDeque. * * DO NOT MODIFY THIS VARIABLE. */ public static final int INITIAL_CAPACITY = 11; // Do not add new instance variables or modify existing ones. private T[] backingArray; private int front; private int size; Q1: write a method that constructs a new arrayDeque called "public ArrayDeque()" Q2: write a method called "public void addFirst(T data)" that adds an element...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort...
IN JAVA PLEASE This problem requires you to code the Merge part of the Merge Sort algorithm. The Merge step merges n elements which takes O(n) time. Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Any code that is found to exceed linear time will fail the tests. Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] import java.util.Scanner; import java.util.ArrayList; public class Solution...
Java Program: You will be traversing through an integer tree to print the data. Given main(),...
Java Program: You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is: 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 -...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial capacity of the ArrayDeque. * * DO NOT MODIFY THIS VARIABLE. */ public static final int INITIAL_CAPACITY = 11; // Do not add new instance variables or modify existing ones. private T[] backingArray; private int front; private int size; Q1: write a method called "public void addLast(T data)" which adds an element to the back of a Deque. If sufficient space is not available...
DIRECTIONS: IMPLEMENT QuickSort and MergeSort. You have been provided: 1. Functions to perform Merge (for MergeSort)...
DIRECTIONS: IMPLEMENT QuickSort and MergeSort. You have been provided: 1. Functions to perform Merge (for MergeSort) and Partition (for QuickSort). 2. In class we discussed the body of the recursive functions, the "brakes" needed to stop the recursion. You are expected to develop 2 RECURSIVE programs: 1. Complete the bodies of the sort functions, MergeSort and QuickSort. 2. Complate the main that tests each function. - program should not read inputs - stock the program with multiple arrays (test cases)...
Write code in java Implement a method to build an AVL tree out of a sorted...
Write code in java Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT