Помогите доработать и найти ошибку

Question

Всем привет, в общем такое дело. Нужно написать код, который сортирует массив по алгоритму Shell и сохраняет изначальную позицию слова в несортированном массиве чтобы по надобности указать позицию, которую занимало слово до сортировки.

Код с введением одномерного массива и созданием двумерного массива с позицией слова в нем -

 public static String [][] sortInZweid(String[] array){
        String[][] arrN = new String [array.length][2];
        int counterForIndex = 1;
        int counterForString = 0;
        for(int i = 0; i < array.length; i++){
                arrN[i][counterForString] = array[i];
                arrN[i][counterForIndex] = Integer.toString(i);
        }
        return arrN;
     }
Код, который нужно переписать чтобы метод принимал двумерный массив и сохранял после сортировки позицию слова в несортированном массиве. Например - 
                                           "Borija" , "1";
                                           "Dima" , "2";
                                           "Anna" , "3";
После сортировки должно выглядеть так -    "Anna" ,"3";
                                           "Borija" , "1";
                                           "Dima" , "2";

Код который нужно переписать -

int sort(String [] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i += 1) {
                final String temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
        return 0;
    }

Код который переписал я, но он работает неправильно, разбираю целый день, но не могу понять почему -

int sort(String [][] arr) {
        for (int gap = arr[0].length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr[0].length; i += 1) {
                final String temp = arr[i][0];
                final String index = arr[i][1];
                int j;
                for (j = i; j >= gap && arr[j - gap][0].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j][0] = temp;
                arr[j][1] = index;
            }
        }
        return 0;
    }

Answer 1

Если тебе нужны исходные индексы слов, просто перед сортировкой создай словарь:

слово -> индексы в неотсортированном массиве.

Map<String, List<Integer>> indices = new HashMap<>();

Нет смысла городить тут двумерные массивы. Сам алгоритм сортировки можно оставить без изменений.

Или же сортировать не строки а пары

Pair<String, Integer> = ImmutablePair.of(arr[i], i);

Можно создать и свой класс StringAndIndex, учитывая при сравнении внутри алгоритма сортировки только сами строки.

class StringAndIndex {
    int index;
    String str;
    public StringAndIndex(String str, int idx) {
         this.index = idx;
         this.str = str;
    }
}

Answer 2

Вы совсем не читаете, что вам пишут в комментариях.

Заменить в циклах arr[0].length => arr.length
String[] temp = arr[i]; ... arr[j] = temp;

Получится в итоге

static int sort(String [][] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i += 1) {
            String[] temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap][0].compareTo(temp[0]) > 0; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    return 0;
}

И все нормально сортируется

[Anna, 2]
[Borija, 0]
[Dima, 1]

Answer 3

Как по мне, то идея с созданием класса лучше, чем двухмерный массив. Последнее - совсем костыль.

import java.util.Arrays;

class ShellSort {

    int sort(Pair arr[]) {        
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i += 1) {
                final Pair temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap].compareTo(temp) > 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
        return 0;
    }

    public static void main(String args[]) {
        String arr[] = {"xxx", "aaa", "ccc", "bbb", "zzz"};
        System.out.println("Array before sorting");
        System.out.println(Arrays.toString(arr));

        ShellSort ob = new ShellSort();
        Pair[] array = Pair.of(arr);
        ob.sort(array);

        System.out.println("Array after sorting");
        System.out.println(Arrays.toString(array));
    }
}


class Pair implements Comparable<Pair>{

    private final int index;
    private final String name;

    public Pair(Integer index, String name) {
        this.index = index;
        this.name = name;
    }

    public int getIndex() {
        return index;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name + "->" + index;
    }

    @Override
    public int compareTo(Pair pair) {
        return this.name.compareTo(pair.getName());
    }

    public static Pair[] of(final String[]arr){
        final Pair[] pairs = new Pair[arr.length];
        for (int i = 0; i < arr.length; i++) pairs[i] = new Pair(i, arr[i]);
        return pairs;
    }

}

БЛОГ НА HUSL

Помогите доработать и найти ошибку

Ответы (3 шт):