Ошибка алгоритма сортировки вставки в коде Java

Question

Итак, я рассматриваю некоторые распространенные алгоритмы сортировки и написал следующее:

Код :

public void insertionSort() {
    int key; 
    int i;   
    for ( int j = 1; j < this.a.length; j++ ) {
        key = a[j];
        i = j;

        while ( i > 0 && a[i-1] > key ) {
            a[i] = a[i-1];
            i = i - 1;
        }
        a[i] = key;
    }
}

Результат :

jan@janspc:~/Dropbox/programming/java/algorithms$ javac sort.java
jan@janspc:~/Dropbox/programming/java/algorithms$ java Test 
49, 68, 60, 14, 70, 8, 83, 96, 29, 7, 92, 35, 17, 84, 31, 62, 48, 95, 16, 22, 31, 97, 72, 55, 88, 63, 1, 63, 96, 32, 74, 15, 92, 77, 50, 13, 12, 36, 90, 93, 20, 15, 67, 88, 23, 31, 95, 90, 86, 65, 35, 27, 60, 4, 90, 11, 22, 97, 65, 88, 23, 1, 25, 21, 9, 81, 87, 56, 2, 4, 63, 52, 55, 86, 62, 30, 55, 64, 19, 10, 45, 92, 87, 43, 39, 95, 20, 43, 3, 30, 74, 64, 4, 90, 91, 93, 94, 44, 87, 21, 

49, 1, 1, 2, 3, 4, 4, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 19, 20, 20, 21, 21, 22, 22, 23, 23, 25, 27, 29, 30, 30, 31, 31, 31, 32, 35, 35, 36, 39, 43, 43, 44, 45, 48, 50, 52, 55, 55, 55, 56, 60, 60, 62, 62, 63, 63, 63, 64, 64, 65, 65, 67, 68, 70, 72, 74, 74, 77, 81, 83, 84, 86, 86, 87, 87, 87, 88, 88, 88, 90, 90, 90, 90, 91, 92, 92, 92, 93, 93, 94, 95, 95, 95, 96, 96, 97, 97, 

Execution took: 110628 nano sek?

Как видно из тестирования, на первое значение сортировка не влияет.Что не так с моим алгоритмом?

Answer 1

В первой итерации цикл while не выполняется, потому что i < 0. В следующей итерации цикл while не запускается, потому что i == 0.

Вы, вероятно, должны использовать while (i >= 0 && a[i] > key) (не проверено, хотя)

Answer 2

Вам нужно >= здесь:

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

Без этого изменения он никогда не сравнивает следующие элементы с первым.

Answer 3

Ниже приведен псевдокод сортировки вставок (взят из книги CLR "Введение в алгоритмы").

Вставка сортировки (А)

для (от j = 2 до A.length)

key = A[j]> 
i = j-1
while i>0 && A[i]>key
    A[i+1] = A[i]
    i = i-1
A[i+1] = key

Ваш код почти аналогичен приведенному выше псевдокоду. Все, что вам нужно, это изменить инициализацию int j=0 на int j=1 в цикле for:

for ( int j = 1; j < this.a.length; j++ ) {
    key = a[j];
    i = j - 1;

    while ( i > 0 && a[i] > key ) {
        a[i + 1] = a[i];
        i = i - 1;
    }
    a[i+1] = key;
}

Answer 4

Это тот же код, но как метод, которому можно передать массив целых чисел для сортировки.

public static int[] insertionSort(int[] array) {
    int key; 
    int i;   


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

        while ( i > 0 && array[i-1] < key ) {
            array[i] = array[i-1];
            i = i - 1;
        }
        array[i] = key;
    }
    return array;
}

Answer 5

public static int[] insrtSort(int array[]){

    for(int i=0 ; i<array.length-1;i++){
        int value=array[i+1],k=i;

        while(value<array[k] ){

            array[k+1]=array[k];
            if(k!=0)
            k--;
            else
                array[0]=value;
        }
        if(k!=0)
        array[k+1]=value;
    }
    return array;
    }

Answer 6

вот очень простая реализация сортировки вставок

package insertion_sort;

public class insertion_sort {
    public static void main(String ar[]) {
        int[] a = {24, 13, 9, 64, 7, 23, 34, 47, 87, 9, 37, 1992};
        insertion(a,12);
    }

    public static void insertion(int[] a, int n) {
        for (int i = 1; i <= n - 1; i++) {
            int value = a[i];
            int hole = i;
            while (hole > 0 && a[hole - 1] > value) {
                a[hole] = a[hole - 1];
                hole = hole - 1;    
            }
            a[hole] = value;
        }
        print(a);    
    }

    public static void print(int[] A) {    
        for (int i = 0; i < A.length; i++) {    
            System.out.print(A[i] + " ");    
        }    
        System.out.println();
    }    
}

Answer 7

Вот еще одна реализация сортировки вставки в java

открытый класс InsertionSort {

static int intArray[] = { 1000, 1, 100, 101, 15 };

public static void doSort() {
    for (int outer = 1; outer < intArray.length; outer++) {
        for(int inner=outer;inner>0; inner--){
            if(intArray[inner]<intArray[inner-1]){
                int temp=intArray[inner];
                intArray[inner]=intArray[inner-1];
                intArray[inner-1]=temp;
                continue;
            }
        }
    }
}

public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
        System.out.print("  " + intArray[i]);
    }
}

public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
}

}

Подробное объяснение кода и / или алгоритма может бытьвидел на - http://www.javabrahman.com/algorithms-in-java/insertion-sort-in-java/

Answer 8

In Insertion Sort нам нужно проверить каждый элемент массива и сравнить с другим элементом, чтобы получить более точный результат.Проблема в вашем коде во время цикла нам нужна строка

while ( i >= 0 && a[i] > key )

Answer 9

Исправленный код :

public void insertionSort() {
    int key; 
    int i;   
    for ( int j = 1; j < this.a.length; j++ ) {
        key = a[j];
        i = j;

        while ( i > 0 && a[i-1] > key ) {
            a[i] = a[i-1];
            i = i - 1;
        }
        a[i] = key;
    }
}

Answer 10

while ( i > 0 && a[i] > key ){ должно быть while ( i >= 0 && a[i] > key ){

Удачи ...