Insertion Sort & Binary Search insertion sort

Question

I am having trouble implementing the insertionSort() method.

import java.util.Random;
import java.util.Arrays;

public class Lab6 {

   static final int SIZE = 100;
   static int[] values = new int[SIZE];
   static void initValues() {
      Random rand = new Random();
      for(int i =0; i< SIZE;i++) {
         values[i] = rand.nextInt(100);// limit to 100
      }
   }

   static boolean isSorted() {
      boolean sorted = true;
      for(int i=0;i<SIZE-1;i++) {
         if(values[i] > values[i+1]){
            sorted = false;
         }
      }
      return sorted;
   }

   static void swap(int index1, int index2) {
      int temp = values[index1];
      values[index1] = values[index2];
      values[index2] = temp;
   }

   static void insertElement(int endIndex) {
   // FILL IN CODE HERE
      boolean finished = false;
      int current = endIndex;
      boolean moretoSearch = true;
      while (moretoSearch && !finished){
         if (values[current] < values[current-1]){
            swap(current, current-1);
            current--;
         }
         else
            finished = true;
      }
   }

I am also not sure if this method "insertElementBinary(int endIndex)" is correctly implemented;

   static void insertElementBinary(int endIndex) {
   //FILL IN CODE HERE FOR BINARY SEARCH INSERTIONSORT
    boolean finished = false;
      int current = endIndex;
      boolean moretoSearch = true;
      while (moretoSearch && !finished){
         if (values[current] < values[current-1]){
            swap(current, current-1);
            current--;
            moretoSearch = (current != endIndex);
         }
         else
            finished = true;
      }
   }

This is where my major problems are:

   static void insertionSort() {
   //FILL IN CODE HERE
      for (int i =0; i < SIZE; i++){
         insertElement(i);
         insertElementBinary(i);
      }
   }

The rest of this is good:

   public static void main(String[] args) {
      Lab6.initValues(); // generate the random array
      System.out.println(Arrays.toString(values));
      System.out.println(isSorted());
      insertionSort();
      System.out.println(Arrays.toString(values));
      System.out.println(isSorted());
   }
}

Answer 1

You're very close to having it correct.

In your insertElement(int endIndex) method, you need to make sure your current > 0, shown below, or else you're going to have an array out of bounds error.

static void insertElement(int endIndex) {
        boolean finished = false;
        int current = endIndex;
        boolean moretoSearch = true;
        while (moretoSearch && !finished && current > 0){
            if (values[current] < values[current-1]){
                swap(current, current-1);
                current--;
            }
            else
                finished = true;
        }
    }

The same fix applies to your insertElementBinary(int endIndex) method. You can test both by commenting out insertElement(i) or insertElementBinary(i) in the insertionSort() method. Both will work fine now.