Gnomesort работает только для первых двух строк

Question

Мне нужно реализовать gnomesort для сортировки строк по их близости к строковому вводу.Я измеряю эту разницу с помощью алгоритма Левенштейна.

Алгоритм работает нормально, но только если у меня есть две строки в базе данных.Затем он сортируется, но если строк больше двух, он просто печатает их в том порядке, в котором они находятся в базе данных.Я действительно не могу найти проблему

public static void retrieveFromDatabase(String string) 
{        
    String[] sq = new String[database.size()];
    database.toArray(sq);        
    int r = 0, index = 1, y = 2, tmp1 = 0;
    String tmp2;

    int[] ds = new int[sq.length];

    for (int i = 0; i < database.size(); i++) {
        ds[i] = sortLevenshtein(string, database.get(i), false);
    }

    for(index = 1; index < ds.length; index++) // gnomsort
    {
        if(ds[index - 1] <= ds[index] )
        {
            ++index;
        }
        else
        {
            tmp1 = ds[index];
            tmp2 = sq[index];
            ds[index] = ds[index - 1];
            sq[index] = sq[index - 1];
            ds[index-1] = tmp1;
            sq[index-1] = tmp2;
            index--;
            if (index == 0) 
                index++;
        }
    }
    System.out.println("Best matches: ");
        for(r=0; r<Math.min(3,sq.length); r++)
        {
            System.out.println(ds[r] + "\t" + sq[r]);
        } 
}

Проблема

Answer 1

Ваша сортировка гномов сортируется некорректно, если сортировать более двух элементов.

В вашем проблемном случае ваш ds содержит 1, 1, 0 с самого начала.В вашем for цикле index равно 1. Вы видите, что элементы с индексами 0 и 1 расположены в правильном порядке (оба элемента равны 1), поэтому вы увеличиваете index до 2 в операторе if.Затем ваш цикл for также увеличивает index, поэтому теперь он равен 3. 3 не меньше, чем ds.length (также 3), поэтому цикл завершается.

Я не знаю сортировку гномов,так что я не могу сказать вам исправление.Что я могу вам сказать, так это то, что манипулирование вашей управляющей переменной цикла for - index в вашем коде - внутри цикла for - это верный путь к коду, который трудно понять и в котором очень трудно найти ошибки. Я никогдакогда-либо делаю это.

    for(index = 1; index < ds.length; index++) // OK: loop control variable is incremented here
    {
        if(ds[index - 1] <= ds[index] )
        {
            ++index; // No-no: incrementing loop control variable, dangerous
        }
        else
        {
            tmp1 = ds[index];
            tmp2 = sq[index];
            ds[index] = ds[index - 1];
            sq[index] = sq[index - 1];
            ds[index-1] = tmp1;
            sq[index-1] = tmp2;
            index--; // No-no: decrementing loop control variable, problematic
            if (index == 0) 
                index++; // No-no: incrementing loop control variable
        }
    }