Сортировка целочисленного массива в java с использованием сортировки выбором. Не могу найти свою ошибку

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

int currentMin;
    int currentMinIndex = 0;
    int temp;
    for(int i=0;i<array.length-1;i++){
        currentMin = array[i]; 
        for(int j=i+1;j<array.length-1;j++){
            if(array[j]<currentMin){
                currentMinIndex = j; 
                currentMin = array[j];
            }
        }
        temp = array[currentMinIndex]; //I am aware this could be currentMin 
        array[currentMinIndex] = array[i];
        array[i] = temp;
    }

Надеюсь, кто-нибудь заметит мою ошибку и скажет мне. (Если у вас есть другие «простые» упражнения, которые я мог бы сделать, творческий подход приветствуется, однако этот пост должен оставаться по теме)

Изменить: я только что заметил, что каким-то странным образом, когда массив большой длины, он сортируется, но последний. (длина массива варьируется, потому что они случайны)


java arrays sorting selection-sort
person Marekkk    schedule 15.12.2016    source источник
comment
У меня есть новости для вас! Вам больше не нужно следовать коду в голове.   -  person shmosel    schedule 16.12.2016
comment
Внутренний цикл должен перейти к array.length (удалите -1)   -  person 4castle    schedule 16.12.2016
comment
Я уже записал его, затем записал каждую переменную. Все предупреждения включены. Я думаю, что уже сломал код, не знаю, как дальше. Я сделал тестовую часть. Я извиняюсь за то, что был глуп.   -  person Marekkk    schedule 16.12.2016
comment
Кроме того, у вас есть две переменные currentMin и currentMinIndex, где currentMinIndex будет достаточно. И если вы установите для currentMin значение array[i], то вы также должны установить для currentMinIndex значение i. Все это было бы очень заметно, если бы вы прошлись по коду с помощью отладчика.   -  person JB Nizet    schedule 16.12.2016
comment
@4castle Хорошо, это немного сработало, но я все еще получаю несортированные массивы. Я только что изменил длину на 5, чтобы было лучше видно. но иногда он сортируется, а иногда нет. И я использую совершенно случайные числа...   -  person Marekkk    schedule 16.12.2016
comment
Спасибо, ребята, это было решено, currentMinIndex должен был быть установлен равным i во внешнем цикле   -  person Marekkk    schedule 16.12.2016

Ответы (3)


arrow_upward
2
arrow_downward

Вам нужно обновить currentMinIndex до i, когда вы устанавливаете currentMin, и ваш внутренний цикл должен быть до array.length.

currentMin = array[i]; 
currentMinIndex = i;
for(int j=i+1;j<array.length;j++){

Вы можете еще больше упростить это, переместив свои объявления в цикл и удалив temp (как у вас есть currentMin), например

for (int i = 0; i < array.length - 1; i++) {
    int currentMin = array[i];
    int currentMinIndex = i;
    for (int j = i + 1; j < array.length; j++) {
        if (array[j] < currentMin) {
            currentMinIndex = j;
            currentMin = array[j];
        }
    }
    array[currentMinIndex] = array[i];
    array[i] = currentMin;
}
person Elliott Frisch    schedule 15.12.2016

arrow_upward
1
arrow_downward

Было две проблемы

  1. Вы забыли сбросить currentMinIndex
  2. Граничное условие во внутреннем цикле for было неправильным

Вот модифицированная версия вашего кода:

public class SelectionSort {

    public static void main(String[] args) {
        int currentMin;
        int currentMinIndex = 0;
        int temp;
        int[] array = {9, 1, 3, 2, 4, 7};
        for(int i=0;i<array.length-1;i++){  
            currentMin = array[i]; 
            currentMinIndex = i;                    // Problem #1
            for(int j=i+1;j<=array.length-1;j++){   // Problem #2
                if(array[j]<currentMin){
                    currentMinIndex = j; 
                    currentMin = array[j];
                }
            }
            temp = array[currentMinIndex]; //I am aware this could be currentMin 
            array[currentMinIndex] = array[i];
            array[i] = temp;
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        String comma = "";      // first time special
        for (int i=0; i<array.length; i++) {
            sb.append(comma + array[i]);
            comma = ", ";       // second time and onwards
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

Вывод этой программы

[1, 2, 3, 4, 7, 9]
person leeyuiwah    schedule 15.12.2016

arrow_upward
0
arrow_downward

Обе ваши петли пропускают последний элемент. Рассмотрите возможность использования <= вместо < в условиях циклов, чтобы учитывать и последний элемент.

person Abhishek Patel    schedule 15.12.2016