Сортировка 2D String Array с BUBBLESORT в Java

Question

Подобные вопросы задавались, но никогда не касались 2D String Arrays, поэтому после долгой попытки я не смог найти то, что хотел. Я пытаюсь отсортировать 2D String Array в Java с помощью BubbleSort.

В качестве ввода я получаю двумерный массив (таблицу) строк и индекс «столбца», который вы должны отсортировать. Я должен отсортировать строки по значениям в указанном столбце.

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

String[][] table = {
  {"a", "b"},
  {"c", "d"}
};

-

0   1
  +---+---+
0 | a | b |
  +---+---+
1 | c | d |
  +---+---+

Чтобы продолжить в этом примере, таблица [0] [1] выдаст значение "b", поскольку это элемент в строке 0 и столбце 1.

ВАЖНО: мне не разрешено использовать какой-либо алгоритм сортировки из библиотеки Java, например Arrays.sort.

Это то, что я пробовал до сих пор:

class Solution {
        public static void stableSort(String[][] table, int column) {
            int i;
            int j;
            String temp = null;
            for (i = 0; i < table.length - 1; i++) {
                for (j = 0; j < table.length - 1 - i; j++) {
                    if (table[i][j].compareTo(table[i][j + 1]) > 0) {
                        temp = table[i][j];
                        table[i][j] = table[i][j + 1];
                        table[i][j + 1] = temp;
                    }
                }
            }
        }
    }

Я получаю ошибку Index of Bounds, которая также не работает, так как тест ожидает другой результат в таблице [0] [0] Спасибо за вашу помощь.

Answer 1

public static String[][] stableSort(String[][] table, int column) {
    int i=0,j=0;
    String[] temp = null;
    boolean swap=true;
    while(swap)
    for (i = 0; i < table.length - 1; i++) {
        swap=false;
        if(table[i][column].compareTo(table[i+1][column]) > 0){
            temp = table[i];
            table[i] = table[i+1];
            table[i+1]=temp;
            swap=true;
        }
    }
    return table;
}

Он продолжает применять пузырьковую сортировку до тех пор, пока больше не будет произведен обмен. В этот момент условие while (swap) больше не выполняется, и метод возвращается. Пробовал в основном и все работает (если я понимаю, что вы имели в виду):

public static void main(String[] args) {
    String[][] table = {
            {"z", "b", "v"},
            {"s", "w", "a"},
            {"r", "c", "h"}
    };

    table = stableSort(table,1);
    for(int i = 0; i < table.length; i++){
        for(int j = 0; j < table[0].length; j++){
            System.out.printf("%5s ", table[i][j]);
        }
        System.out.println();
    }
}

это выводит:

z     b     v 
r     c     h 
s     w     a 

Answer 2

для начала, сделайте это 1d массивом или хотя бы 1d индексируемый намного легче формула:

x = (int)index/(int)rows
y = index % rows

с этим вы можете использовать 1 индекс переменной и индексировать 2d массив и это пузырьковая сортировка

def sort(self):
    for passnum in range(len(self.array)-1,0,-1):
        for i in range(passnum):
            if self.array[i]>self.array[i+1]:
                temp = self.array[i]
                self.array[i] =  self.array[i+1]
                self.array[i+1] = temp

Answer 3

Мой рабочий раствор:

import java.util.Arrays;

public class MySolution {
    public static void stableSort(String[][] table, int column) {
        String[] temp = null;
        int rows = table.length;
        for (int i = 0; i < rows; i++) {
            for (int j = 1; j < (rows - i); j++) {
                if (table[j - 1][column].compareTo(table[j][column]) > 0) {
                    temp = table[j - 1];
                    table[j - 1] = table[j];
                    table[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        String[][] table = { { "c", "d" }, { "a", "b" } };
        printTable(table);
        stableSort(table, 1);
        printTable(table);
    }

    private static void printTable(String[][] table) {
        System.out.println("table:");
        for (int i = 0; i < table.length; i++) {
            System.out.println(Arrays.toString(table[i]));
        }
    }
}

некоторые заметки для вас:

1. использовать значимые имена (строки легче понять, чем table.length)
2. петли пузырьковой сортировки были немного отключены, есть множество примеров, как это сделать онлайн
3. как уже упоминалось, вы должны начать делать это для 1d массива, а затем "обобщить" его
4. одна большая проблема, с которой вы столкнулись: использование j (который должен быть индексом строки для сравнения) в качестве столбца (и игнорирование столбца)
5. еще одна большая проблема - замена только элемента (вместо строк)

Надеюсь, это поможет вам!

РЕДАКТИРОВАТЬ: я только что заметил, что вы также переключились между строкой и столбцом в вашем коде (в вашем объяснении первый индекс обозначает строку, в вашем коде кажется, что все наоборот)

Answer 4

РЕДАКТИРОВАТЬ: работает и без ошибок

Если я возьму точную сортировку, но добавлю оператор if для переключения строк, добавим внешний цикл, чтобы пройти через 2D-массив, длина умноженная на ширину, и изменитьдля контроля цикла в '<=', тогда я получаю следующее </p>

   for(int z = 0; z < table.length * table.length; z++) // exterior for loop to run through the loop multiple times
   {
       for (i = 0; i <= table.length - 1; i++) {
           for (j = 0; j <= table.length - 1; j++) {
              if(j == table.length -1 && i == table.length-1) // If we are at the end then we can continue either to the next iteration or to the end of program
                  continue;
              if(j == table.length -1) // If you are ate the end of the row compare to the next row
              {
                   if (table[i][j].compareTo(table[i+1][0]) > 0) {
                       temp = table[i][j];
                       table[i][j] = table[i+1][0];
                       table[i+1][0] = temp;
                   } 
              }
              else if (table[i][j].compareTo(table[i][j + 1]) > 0) {
                   temp = table[i][j];
                   table[i][j] = table[i][j + 1];
                   table[i][j + 1] = temp;
              }
           }
       }
   }

Я видел, что вы пытались сделать, минимизируя количество проверок, когда вы ставите

table.length - 1 - i

То естьхорошо для эффективности, но сначала попытайтесь заставить сортировку работать.затем обрежьте его, чтобы лучше преформировать.

Кроме того, передо мной нет компилятора, поэтому в коде могут быть ошибки