Question

I need to implement incrementalInserstionSort im stuck on that part

import java.util.*;

/**
 * This class represents chains of linked nodes that
 * can be sorted by a Shell sort.
 *
 * @author Charles Hoot
 * @author Frank M. Carrano
 *         Modified by atb
 * @author YOUR NAME
 * @version 9/29/2020
 */
public class ChainSort>
{
    private Node firstNode; // reference to first node

    public ChainSort()
    {
        this.firstNode = null;
    }

    public void display()
    {
        Node currentNode = this.firstNode;
        while (currentNode != null)
        {
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.next;
        }
        System.out.println();
    } // end display

    public boolean isEmpty()
    {
       return this.firstNode == null;
    } // end isEmpty

    public void addToBeginning(T newEntry)
    {
        Node newNode = new Node<>(newEntry);
        newNode.next = this.firstNode;
        this.firstNode = newNode;
    } // end addToBeginning

    public void shellSort(int chainSize)
    {
        //TODO Project3

        for (int space = chainSize / 2; space > 0; space = space / 2)
        {
            //     create sub-chains:
            //          set previousNode to the first node in the chain
            //          set currentNode to the first node in the chain
            //          with a for loop traverse nodes space times using currentNode
            //            to find the second node of the first sub-chain
            //
            //          with a while loop set up backward links for all sub-chains:
            //              set currentNode's previous pointer to the previousNode
            //              set previousNode to its next node and do the same with the currentNode
            Node currentNode = this.firstNode;
            Node previousNode = this.firstNode;
            for (int index = 0; index < space; index++)
            {
                currentNode = currentNode.next;
            }


            while (currentNode != null)
            {
                previousNode = previousNode.next;
                currentNode = currentNode.next;
            }



            System.out.println("\n\u001B[35m\u001B[1m----->Before partial sort with space " + space + " :\u001B[0m");
            display();
            // sort all the sub-chains:
            incrementalInsertionSort(space);
            System.out.println("\u001B[35m\u001B[1m----->After partial sort done with space " + space + " :\u001B[0m");
            display();
        }
    } // end shellSort

    /**
     * Task: Sorts equally spaced elements of a linked chain into
     * ascending order. Sub-chains created with a use of previous.
     *
     * @param space the space between the nodes of the
     *              elements to sort
     */
    private void incrementalInsertionSort( int space)
    {
        //TODO Project3
        // when sorting do not change pointers - simply swap the data if needed


    } // end incrementalInsertionSort


    private class Node
    {
        private S data;
        private Node next;
        private Node previous; // ADDED for linking backwards for shell sort

        private Node(S dataPortion)
        {
            this.data = dataPortion;
            this.next = null;
            this.previous = null;
        }
    } // end Node

    // ************ TEST DRIVER *****************

    public static void main(String args[])
    {
        System.out.println("What size chain should be used?");
        int chainSize = getInt("   It should be an integer value greater than or equal to 1.");

        System.out.println("What seed value should be used?");
        int seed = getInt("   It should be an integer value greater than or equal to 1.");
        Random generator = new Random(seed);
        ChainSort myChain = new ChainSort<>();

        for (int i = 0; i < chainSize; i++)
            myChain.addToBeginning(generator.nextInt(100));

        System.out.print("\nOriginal Chain Content: ");
        myChain.display();
        myChain.shellSort(chainSize);
        System.out.print("\nSorted Chain Content: ");
        myChain.display();
    }


    /**
     * Get an integer value
     *
     * @param rangePrompt String representing a message used to ask the user for input
     * @return an integer
     */
    private static int getInt(String rangePrompt)
    {
        Scanner input;
        int result = 10;        //default value is 10
        try
        {
            input = new Scanner(System.in);
            System.out.println(rangePrompt);
            result = input.nextInt();

        } catch (NumberFormatException e)
        {
            System.out.println("Could not convert input to an integer");
            System.out.println(e.getMessage());
            System.out.println("Will use 10 as the default value");
        } catch (Exception e)
        {
            System.out.println("There was an error with System.in");
            System.out.println(e.getMessage());
            System.out.println("Will use 10 as the default value");
        }
        return result;
    }
} // end ChainSort

Answer 1

Insertion sort is a sorting algorithm in which one element is taken from the unsorted part and is placed in its correct position in the sorted part.

For example:

Let the array be

3 2 4 1 5

First element, 3, is taken and as there is only one element it is sorted and is in correct position. Therefore, the list remains the same.

3 2 4 1 5

Now, 3 is the sorted part and 2 4 1 5 is the unsorted part.

Now, second element, 2, is taken and it is placed in the correct position in the sorted part. Therefore, the list becomes:

2 3 4 1 5

Now, 2 3 is the sorted part and 4 1 5 is the unsorted part.

Now the third element, 4, is taken. The list becomes:

2 3 4 1 5

Now, 2 3 4 is the sorted part and 1 5 is the unsorted part.

Now the fourth element, 1, is taken. The list becomes:

1 2 3 4 5

Finally, the last element is placed.

The final sorted list is:

1 2 3 4 5

Therefore, in this way the list is sorted using the insertion sort algorithm.

Method to sort an array using Insertion sort is as follows:

void sort(int arr[])
{
int n=arr.length;
for (int i=1; i<n; ++i)
{
int key=arr[i];
int j=i-1;
while(j>=0 && arr[j]>key)
{
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=key;
}
}