Почему моя сортировка вставки не проходит этот тест? - PullRequest
Новая
       14

Почему моя сортировка вставки не проходит этот тест?

0 голосов
/ 21 мая 2018

Я пытаюсь написать сортировку вставки, и я прошёл несколько тестовых случаев, но я провалил один.Мой код: 

static void insertionSort1(int n, int[] arr) {


    int copy = arr[n-1];

    int i = n - 1;
    while (copy < arr[i-1]){

        arr[i] = arr[i-1];

        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
            System.out.println();
        i--;
        }
     arr[i] = copy;
    for(int m = 0; m < arr.length; m++){
       System.out.print(arr[m] + " ");
     }
    }

, где n это размер массива, а arr это массив.Мой алгоритм не проходит этот тест, в частности: 

10

2 3 4 5 6 7 8 9 10 1

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

5

2 4 6 8 3

или других.что происходит?

Ответы [ 2 ]

0 голосов
/ 21 мая 2018

Это индекс из привязанного исключения массива из-за минус значения arr.Это не проблема алгоритма, а язык. 

while (i > 0 && copy < arr[i - 1])

Источник: 

public class InsertionSort {
    static void insertionSort1(int n, int[] arr) {

        int copy = arr[n - 1];

        int i = n - 1;
        while (i > 0 && copy < arr[i - 1]) {

            arr[i] = arr[i - 1];

            for (int k = 0; k < arr.length; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
            i--;
        }
        arr[i] = copy;
        System.out.println("#### RESULT ####");
        for (int m = 0; m < arr.length; m++) {
            System.out.print(arr[m] + " ");
        }
        System.out.println("\n#### END ####\n");
    }

    public static void main(String[] args)
    {
        //10
        //2 3 4 5 6 7 8 9 10 1
        int[] arr ={2, 3, 4, 5, 6, 7, 8, 9, 10, 1};
        int n = arr.length;
        insertionSort1(n, arr);


        //5
        //2 4 6 8 3
        arr= new int[5];
        n = arr.length;

        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 8;
        arr[4] = 3;

        insertionSort1(n, arr);
    }
}

Результат: 

2 3 4 5 6 7 8 9 10 10 
2 3 4 5 6 7 8 9 9 10 
2 3 4 5 6 7 8 8 9 10 
2 3 4 5 6 7 7 8 9 10 
2 3 4 5 6 6 7 8 9 10 
2 3 4 5 5 6 7 8 9 10 
2 3 4 4 5 6 7 8 9 10 
2 3 3 4 5 6 7 8 9 10 
2 2 3 4 5 6 7 8 9 10 
#### RESULT ####
1 2 3 4 5 6 7 8 9 10 
#### END ####

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
#### RESULT ####
2 3 4 6 8 
#### END ####

Хорошего дня.

0 голосов
/ 21 мая 2018

Сначала вы должны рассмотреть, что такое сортировка вставок.Вы должны создать отсортированный список на одном конце массива, расширяя его по одному элементу за раз, «вставляя» следующее значение в правильное место.Это очень похоже на сортировку карт, если вам дают по одной.Вам понадобится вложенный цикл, чтобы сделать это правильно.

Тщательно продумайте, что на самом деле делает ваша программа, и посмотрите, почему она не работает - более короткий тестовый случай, который не может быть выполнен таким же образом, будет [3, 2, 1].Или [2, 1], в этом отношении.

...