Вставка Сортировка и двоичный поиск Вставка сортировки

Question

У меня возникли проблемы с внедрением метода insertionSort().

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; 
     } 
    } 

Я также не уверен, что этот метод «insertElementBinary (интермедиат ENDINDEX)» правильно реализован;

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; 
     } 
    } 

Это где мои основные проблемы:

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

Остальное это хорошо:

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

Вы очень близки к тому, что правильно.

В вашем методе insertElement (int endIndex) вам необходимо убедиться, что ваш current > 0, показанный ниже, иначе вы будете иметь ошибку за пределами границ.

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; 
     } 
    } 

То же самое исправление применяется к вашему методу insertElementBinary(int endIndex). Вы можете протестировать оба путем комментирования insertElement(i) или insertElementBinary(i) в методе insertionSort(). Оба будут работать отлично.