Run with 10000 8 -------------------------------------------------------------------------------- -- Auto-annotated source: /home/cstaley/PolyWork/CountInversions3.c -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -- line 7 ---------------------------------------- . . . . . . . . . . . . . . . . . . typedef struct { . . . . . . . . . long tag1; . . . . . . . . . long tag2; . . . . . . . . . char name1[NAME_LEN]; . . . . . . . . . char name2[NAME_LEN]; . . . . . . . . . } CacheHog; . . . . . . . . . 4 0 0 0 0 0 1 0 0 int main(int argc) { 2 1 0 0 0 0 2 0 0 int i, j, numHogs, numInv1 = 0, numInv2 = 0; . . . . . . . . . int tileSize, iBase, iLim, jBase, jLim; . . . . . . . . . CacheHog *vals; . . . . . . . . . 7 1 1 0 0 0 4 0 0 scanf("%d %d", &numHogs, &tileSize); 5 1 0 1 0 0 4 1 0 vals = calloc(sizeof(CacheHog), numHogs); 40,005 2 1 30,002 0 0 1 0 0 for (i = 0; i < numHogs; i++) { 60,000 0 0 40,000 0 0 10,000 10,000 0 vals[i].tag1 = numHogs - i; 60,000 0 0 40,000 0 0 10,000 0 0 vals[i].tag2 = numHogs + i; . . . . . . . . . } . . . . . . . . . 6,255 1 1 3,752 0 0 1,251 0 0 for (iBase = 0; iBase < numHogs; iBase = iLim) { 8,750 1 1 3,750 0 0 1,250 0 0 iLim = iBase + tileSize < numHogs ? iBase + tileSize : numHogs; . . . . . . . . . . . . . . . . . . // Check within the tile 47,500 1 1 33,750 0 0 1,250 0 0 for (i = iBase; i < iLim; i++) 210,000 1 0 135,000 0 0 10,000 0 0 for (j = i+1; j < iLim; j++) { 350,000 0 0 210,000 9,995 0 0 0 0 if (vals[i].tag1 > vals[j].tag1) 35,000 1 0 35,000 0 0 0 0 0 numInv1++; 350,000 0 0 210,000 0 0 0 0 0 if (vals[i].tag2 > vals[j].tag2) . . . . . . . . . numInv2++; . . . . . . . . . } . . . . . . . . . . . . . . . . . . // Check all following tiles, exhausting each completely wrt tile i 3,910,625 1 1 2,345,625 0 0 781,875 0 0 for (jBase = iLim; jBase < numHogs; jBase = jLim) { 5,464,375 1 0 2,341,875 0 0 780,625 0 0 jLim = jBase + tileSize < numHogs ? jBase + tileSize : numHogs; 29,663,750 1 0 21,076,875 0 0 780,625 0 0 for (i = iBase; i < iLim; i++) 237,310,000 0 0 168,615,000 0 0 6,245,000 0 0 for (j = jBase; j < jLim; j++) { 499,600,000 1 1 299,760,000 53,861,876 0 0 0 0 if (vals[i].tag1 > vals[j].tag1) 49,960,000 1 0 49,960,000 0 0 0 0 0 numInv1++; 499,600,000 0 0 299,760,000 0 0 0 0 0 if (vals[i].tag2 > vals[j].tag2) . . . . . . . . . numInv2++; . . . . . . . . . } . . . . . . . . . } . . . . . . . . . } . . . . . . . . . 7 1 0 2 0 0 4 0 0 printf("Inversion counts: %d %d \n", numInv1, numInv2); 3 0 0 1 0 0 2 0 0 free(vals); . . . . . . . . . 1 0 0 0 0 0 0 0 0 return 0; 2 0 0 2 0 0 0 0 0 } --------------------------------------------------------------------------------