Unsorted didgit в алгоритме вставки сортировки - PullRequest
Новая
       10

Unsorted didgit в алгоритме вставки сортировки

0 голосов
/ 04 сентября 2018 
// this describes the insertion sort algorithm
public class InsertionSort {

    public static void main(String[] args) {
        //array of unsorted integers

        int [] array = { 10, 4, 1, 11, 5, 3, 8, 2, 0, 9};

        int n = array.length;

        for ( int j = 1; j<n; j++) {
            //assign a value to the second element in the array
            int key = array[j];

            //assign a value to the 1st element in the list
            int i = j-1;

            //loop executes as long as i>0 and that the element befor the key is greater than the key itself
            while( i>0 && array[i]>key) {

                //move the bigger element 1 block forward
                array[i+1] = array[i];

                // keep moving until the element is in the right position
                i =i-1;

            }
            array[i+1] = key;//assign the key to the appropritae location
        }

         for (int i=0; i<n; i++)
                System.out.print(array[i] + " ");

            System.out.println();
    }

}

это вывод, как видите, все отсортировано, кроме 10, который все еще неуместен в массиве

10 0 1 2 3 4 5 8 9 11

1 Ответ

0 голосов
/ 04 сентября 2018

В этой строке есть проблема: 

while( i>0 && array[i]>key) {

Первая итерация, j равна 1, и поэтому я равен 0. И ваш цикл не запускается, потому что 0 не больше , чем ноль. Но он должен работать, поэтому условие должно измениться на «больше чем или равно нулю»: 

while( i>=0 && array[i]>key) {

Это исправит ваш род.

...