// Insertion sorts for a table of integers

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

typedef struct {int keyPart, satPart;  } Item;
#define key(A) (A.keyPart)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

void insertionSort(Item *a,int N) // Guaranteed stable
{
int i,j;
Item v;

for (i=1; i<N; i++) 
{
  v=a[i];
  j=i;
  while (j>=1 && less(v,a[j-1]))
  {    
    a[j]=a[j-1];
    j--;
  }
  a[j]=v;
}
}

void insertion(Item a[], int ell, int r)
// Sentinel processing loses stability
{
  int i;
  for (i = ell+1; i <= r; i++) // Ensures a[ell] is instance of
    compexch(a[ell], a[i]);    // smallest value using swaps
  for (i = ell+2; i <= r; i++)
  { // a[ell] ... a[i-1] are in ascending order
    int j = i;
    Item v = a[i];
    while (less(v, a[j-1])) // Rippling to fix prefix
    {
      a[j] = a[j-1];
      j--;
    }
    a[j] = v; // After this assignment a[ell] ... a[i] are ordered
  }
}

int main()
{
// Use 20 123 as input to cause stability issue with insertion()
Item *arr;
int i,arrSize;
int seed;

printf("enter number of keys\n");
scanf("%d",&arrSize);
arr=(Item*) malloc(sizeof(Item)*arrSize);
if (!arr)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
printf("enter seed\n");
scanf("%d",&seed);
srandom(seed);
for (i=0;i<arrSize;i++) {
  arr[i].keyPart=abs((int) random()%10);
  arr[i].satPart=i;
}
printf("Unsorted input-stable\n");
for (i=0;i<arrSize;i++)
  printf("%3d %3d %3d\n",i,arr[i].keyPart,arr[i].satPart);
insertionSort(arr,arrSize);
printf("Sorted output-stable\n");
for (i=0;i<arrSize;i++)
  printf("%3d %3d %3d\n",i,arr[i].keyPart,arr[i].satPart);

srandom(seed);
for (i=0;i<arrSize;i++) {
  arr[i].keyPart=abs((int) random()%10);
  arr[i].satPart=i;
}
printf("Unsorted input-unstable\n");
for (i=0;i<arrSize;i++)
  printf("%3d %3d %3d\n",i,arr[i].keyPart,arr[i].satPart);
insertion(arr,0,arrSize-1);
for (i=1;i<arrSize;i++)
  if (arr[i-1].keyPart==arr[i].keyPart && arr[i-1].satPart>arr[i].satPart)
    printf("Unstable at %d\n",i);
printf("Sorted output-unstable\n");
for (i=0;i<arrSize;i++)
  printf("%3d %3d %3d\n",i,arr[i].keyPart,arr[i].satPart);
}