Add a method insertionSort to the class ArraySorter, that performs an insertion

Question

Add a method insertionSort to the class ArraySorter, that performs an
insertion sort of an array. The algorithm is described in detail on wikipedia.
for (index = 1; index < a.length; index++)
      insert value at index into the the appropriate place
      in the sorted subsection of the array,
      increasing the length of the sorted subsection by 1

Please add a method insertionSort to the class ArraySort and follow the algorium above carefully. I will give the code for ArraySort class below. Also please use IDE to finish this question and make sure it is working. In the result, it should show multiple arrays that show how the inertionSort process going from beginng to final result .  Also do not erase or build a whole new class, the question need to add an method inside the given class ArraySort.

here is the ArraySorter class

public class ArraySorter
{
/**
    Precondition: Every element in anArray has a value.
    Action: Sorts the array into ascending order.
*/
public static void selectionSort(int[] anArray)
{
  for (int index = 0; index < anArray.length - 1; index++)
  {   // Place the correct value in anArray[index]
   int indexOfNextSmallest = getIndexOfSmallest(index, anArray);
   interchange(index, indexOfNextSmallest, anArray);
   //Assertion:anArray[0] <= anArray[1]< =...<= anArray[index]
   //and these are the smallest of the original array elements.
   //The remaining positions contain the rest of the original
   //array elements.
  }
}
/**
    Returns the index of the smallest value in the portion of the
    array that begins at the element whose index is startIndex and
    ends at the last element.
*/
private static int getIndexOfSmallest(int startIndex, int[] a)
{
  int min = a[startIndex];  
  int indexOfMin = startIndex;
  for (int index = startIndex + 1; index < a.length; index++)
  {
   if (a[index] < min)
   {
    min = a[index];
    indexOfMin = index;
    //min is smallest of a[startIndex] through a[index]
   }
  }
  return indexOfMin;
}
/**
    Precondition: i and j are valid indices for the array a.
    Postcondition: Values of a[i] and a[j] have been interchanged.
*/
private static void interchange(int i, int j, int[] a)
{
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp; //original value of a[i]
}
}

Explanation / Answer

A method named insertionSort is added to the ArraySorter class. It sorts the array and prints the array at every step.

  public class ArraySorter  {      public static void main(String[] args) {          int array[] = {3, 1, 5, 8, 2, 9, 4};          insertionSort(array);      }        public static void insertionSort(int[] anArray)      {          System.out.println("Before insertion sort: ");          printArray(anArray);       //Move through the array from index = 1. The elements are assigned to 'value'. Starting at value = array[1].          for (int index = 1; index < anArray.length; index++) {              int value = anArray[index];              int j = index - 1;                              //'j' is the index of the sorted array. Starts at 0.              while (j >= 0 && anArray[j] > value) {          //If 'j'>=0 & (element at j > value)                  anArray[j+1] = anArray[j];                  //Push the element 1 index further. This repeats                  j = j - 1;                                  //till all elements larger than 'value' are placed              }                                               //after it.              //At end of while loop, 'j' is reduced to the index: index[last pushed larger number] - 2.              anArray[j+1] = value;                           //Value is assigned to the index before all numbers              System.out.println("Step " + index + ": ");     //larger than it.              printArray(anArray);          }      }        public static void printArray(int array[]) {          for (int i =0 ;i < array.length; i++) {              System.out.print(array[i]+ " ");          }          System.out.println();      }      /**       Precondition: Every element in anArray has a value.       Action: Sorts the array into ascending order.       */      public static void selectionSort(int[] anArray)      {          for (int index = 0; index < anArray.length - 1; index++)          {   // Place the correct value in anArray[index]              int indexOfNextSmallest = getIndexOfSmallest(index, anArray);              interchange(index, indexOfNextSmallest, anArray);              //Assertion:anArray[0] <= anArray[1]< =...<= anArray[index]              //and these are the smallest of the original array elements.              //The remaining positions contain the rest of the original              //array elements.          }      }      /**       Returns the index of the smallest value in the portion of the       array that begins at the element whose index is startIndex and       ends at the last element.       */      private static int getIndexOfSmallest(int startIndex, int[] a)      {          int min = a[startIndex];          int indexOfMin = startIndex;          for (int index = startIndex + 1; index < a.length; index++)          {              if (a[index] < min)              {                  min = a[index];                  indexOfMin = index;                  //min is smallest of a[startIndex] through a[index]              }          }          return indexOfMin;      }      /**       Precondition: i and j are valid indices for the array a.       Postcondition: Values of a[i] and a[j] have been interchanged.       */      private static void interchange(int i, int j, int[] a)      {          int temp = a[i];          a[i] = a[j];          a[j] = temp; //original value of a[i]      }  }  

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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