Функция сортировки вставкой не работает.Зачем?

Question

void insertionsort(int a[], int n){
    int next, i, j;
    for(i=1; i<n; i++){
        if(a[i]<a[i-1]){
            for(j=i-2; j>=0; j--){
                if(a[j]<a[i]){
                    next = a[i];
                    a[i] = a[j];
                    a[j] = next;
                }
            }
        }
    }
}

Это функция, которая должна упорядочивать элементы массива в порядке возрастания.Почему это не работает?

Answer 1

Ваше решение не совсем то, что утверждает алгоритм.Вы можете не использовать два вложенных цикла for:

void insertionsort(int a[], int n){
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = a[i]; 
       j = i-1; 

       /* 
          Move all elements in the array at index 0 to i-1, that are 
          greater than the key element, one position to the right 
          of their current position 
       */
       while (j >= 0 && a[j] > key) 
       { 
           a[j+1] = a[j]; 
           j = j-1; 
       } 
       a[j+1] = key; 
   } 
}

Answer 2

Вам также нужно поменять значение индекса i-1, а второе условие цикла должно быть >.

void insertionsort(int a[], int n){
    int next, i, j;
    for(i=1; i<n; i++){
        if(a[i]<a[i-1]){
            for(j=i; j>0; j--){
                if(a[j - 1]>a[ j ]){
                    next = a[ j - 1];
                    a[j - 1] = a[j];
                    a[j] = next;
                }
            }
        }
    }
}