Вставка сортируется в противоположном направлении. Сортированная часть справа и несортированная слева

Question

Я пытаюсь инвертировать отсортированную часть и несортированную часть в логике сортировки вставки, описанной в CLR. Выход полностью ошибочен. Может кто-нибудь указать ошибку или логическую ошибку в моем коде.

#include<stdio.h> 
#include<stdlib.h> 

int main() 
{ int a[] = {67,7,3,2,1,9,45,5}; 
    int k; 
    int n = sizeof(a)/sizeof(a[0]); 
    insert(a,n); 
    for(k = 0;k < n; k++) 
     printf("%d %d\n",k,a[k]); 
    return 0; 
} 

void insert(int *a,int n) 
{ 
    int i,j,val; 
    for(i=n-2;i>=0;i--){ 
     val=a[i]; 
     for(j=i+1;j<n && a[j]<val;j++){ 
      a[j-1]=a[j]; 
     } 
     a[j--]=val; 
} 

Answer 1

Вы должны вставить последний элемент в a[j - 1]. Вы можете добиться этого с уменьшением, но в этом случае вы должны использовать префикс декремента, который изменяет значение перед его ссылкой: a[--j] = val;.

Вот исправленный вариант:

void insertion_sort_backwards(int *a, int n) 
{ 
    int i = n - 1; 

    while (i--) { 
     int val = a[i]; 
     int j; 

     for (j = i + 1; j < n && a[j] < val; j++) { 
      a[j - 1] = a[j]; 
     } 

     a[j - 1] = val; 
    } 
} 

Это будет сортировать массив с правой стороны:

67, 7, 3, 2, 1, 9, 5, 45 
67, 7, 3, 2, 1, 5, 9, 45 
67, 7, 3, 2, 1, 5, 9, 45 
67, 7, 3, 1, 2, 5, 9, 45 
67, 7, 1, 2, 3, 5, 9, 45 
67, 1, 2, 3, 5, 7, 9, 45 
1, 2, 3, 5, 7, 9, 45, 67