реализация сортировки вставки в Java

Question

У меня есть два файла: один - драйвер, а второй - два метода, первый - сортировка вставкой, второй - метод печати. Сортировка вставки должна сортировать массив строк по лексикографическому признаку.

import java.util.Arrays;

общественный класс Utility {

public static void insertionSort(String[] array) {
    //TODO

    for ( int i=1  ; i<array.length; i++)
    {
        int j = i;
        String str1 = array[j-1];
        String str2 = array[j];
        while (j>0 && str1.compareTo(str2)>0)
        {
            String t = array[j];
            array[j] = array[j-1];
            array[j-1] =t;
            j = j-1;
        }
    }
}

public static void printArray(String[] array) {

    String t = Arrays.toString(array);
    System.out.println(t);
}

}

а вот и мой драйвер

public class Driver {

public static void main(String[] args) {

    String[] names = {"Tom", "Steve","Ann","Zoe","Bob","Moana","Naomi","Kevin","Ryan","Nina","Dora","Wanda","Eric"};

    System.out.println("Unsorted array:");
    Utility.printArray(names);
    System.out.println("Sorted array:");
    Utility.insertionSort(names);
    Utility.printArray(names);




}

}

Я пытался отсортировать массив, но я не знаю, почему не происходит сортировка, потому что это мой метод inserttionSort и это что-то в моем драйвере

вот псевдокод, которому я пытался следовать

for i=1 to length(A)
   j =i
  while j > 0 and A[j-1] > A[j]
    swap A[j] and A[j-1]
    j =j -1
  end while

конец для

Answer 1

Я обнаружил две ошибки в вашем исходном алгоритме:

• Первый: второй цикл никогда не заканчивается, потому что в его внутреннем блоке не происходит изменений условий управления.
• Second: Еще раз, второй цикл всегда выполняет то же сравнение, потому что в сравниваемых строках не производится никаких изменений.

Мой совет:

• Для выполнения индексированных циклов всегда используйте форму for. При объявлении поддерживающего условия включайте простое реляционное сравнение.
• Инициализация переменных должна выполняться на самом внутреннем уровне (и только один раз), на каждой итерации, от которой они зависят.
• Сложные условия должны быть реализованы через определенный if.