// Insertion sorts for a table of integers #include #include 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=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;iarr[i].satPart) printf("Unstable at %d\n",i); printf("Sorted output-unstable\n"); for (i=0;i