Code:
#include <stdio.h>
#include <stdlib.h>
void printarray(const int x, const int data[]);
void quicksort(int data[], int first, int last, int *count);
int main()
{
int num_elements = 1000, count = 0, data[1000] = {7, 12, 18, 28, 45, 12, 63, 56, 81, 90,
22, 108, 52, 70, 135, 64, 153, 72, 38, 20,
126, 88, 92, 192, 150, 78, 27, 168, 58, 270,
124, 288, 99, 238, 140, 72, 333, 38, 312, 240,
369, 294, 215, 132, 135, 184, 235, 432, 294, 300,
51, 468, 371, 216, 385, 224, 342, 290, 531, 300,
244, 124, 252, 384, 390, 330, 335, 340, 345, 70,
71, 216, 584, 222, 225, 608, 385, 546, 553, 640,
81, 410, 581, 672, 680, 172, 174, 176, 623, 720,
637, 92, 651, 752, 475, 384, 194, 882, 594, 400,
101, 714, 618, 832, 735, 954, 642, 972, 436, 110,
777, 336, 678, 456, 115, 464, 702, 1062, 476, 120,
605, 976, 123, 372, 500, 630, 762, 640, 387, 1170,
1179, 396, 532, 402, 1080, 272, 1233, 552, 139, 560,
564, 852, 858, 1296, 1305, 584, 294, 444, 447, 450,
453, 1064, 1224, 308, 1085, 312, 628, 158, 795, 960,
161, 648, 1304, 656, 990, 996, 501, 672, 1183, 340,
1197, 1548, 1211, 174, 1050, 704, 354, 890, 1253, 360,
1267, 1274, 1464, 552, 1110, 744, 935, 188, 756, 1710,
1146, 384, 193, 582, 1170, 784, 1182, 1188, 1393, 400,
1407, 404, 203, 408, 1845, 1236, 1242, 208, 1881, 210,
422, 1272, 1065, 1712, 1935, 432, 434, 436, 438, 660,
1768, 1110, 1115, 1792, 1125, 1808, 2043, 456, 916, 1150,
693, 2088, 1398, 234, 235, 944, 948, 952, 956, 720,
482, 968, 1701, 1708, 490, 1476, 1976, 248, 1245, 1750,
251, 756, 2277, 762, 2040, 1280, 257, 1290, 1036, 780,
2349, 1048, 2367, 1584, 1060, 1862, 1869, 1876, 538, 270,
2168, 816, 546, 1370, 2475, 276, 2216, 1390, 2232, 840,
2529, 2538, 849, 2556, 570, 2288, 574, 864, 867, 870,
873, 876, 1758, 588, 1770, 2072, 2376, 894, 598, 2700,
301, 2718, 303, 912, 1220, 2142, 307, 616, 927, 2790,
622, 2808, 2504, 628, 2520, 2844, 2853, 2226, 2871, 320,
2889, 2898, 969, 1620, 325, 1956, 2943, 2296, 1974, 660,
1324, 1328, 333, 1336, 2010, 1008, 3033, 1690, 678, 3060,
1364, 684, 2744, 688, 1035, 2422, 2776, 348, 1396, 2100,
351, 1408, 1765, 354, 2130, 1424, 2142, 2148, 359, 720,
2527, 724, 1815, 1820, 2190, 3294, 1835, 1104, 1476, 2590,
742, 1860, 2238, 3366, 2250, 3008, 2262, 756, 3032, 3040,
1905, 3056, 3447, 384, 2310, 1930, 774, 776, 3112, 3510,
391, 1176, 393, 1576, 2370, 1584, 397, 398, 2394, 800,
2005, 2814, 2418, 404, 2835, 3654, 2849, 408, 409, 1230,
2466, 1648, 3717, 2070, 830, 2080, 3336, 1254, 2933, 1680,
3789, 2110, 2961, 3816, 3400, 426, 854, 2568, 3432, 2150,
3017, 1728, 1299, 1302, 870, 3052, 874, 2628, 2195, 440,
3969, 884, 1772, 3552, 1780, 2230, 1341, 4032, 2245, 3150,
1804, 1808, 453, 3632, 455, 3648, 2742, 916, 2295, 1840,
3227, 4158, 2315, 3248, 1395, 3262, 934, 936, 469, 2820,
4239, 4248, 2365, 474, 2375, 3332, 1431, 2868, 2874, 3360,
1443, 3374, 3864, 1452, 1455, 4374, 4383, 3904, 3912, 980,
1473, 1476, 493, 2470, 4455, 496, 4473, 3984, 499, 500,
2505, 3514, 4527, 3528, 3030, 1518, 2028, 4064, 4072, 4080,
2044, 4096, 1539, 4626, 4635, 3096, 3102, 4144, 1038, 2600,
3647, 1044, 2615, 2620, 3675, 2630, 2108, 3168, 529, 1060,
3186, 2660, 3198, 2136, 535, 1072, 3222, 1076, 4312, 2160,
3787, 1084, 1086, 544, 4360, 4368, 2188, 2740, 3294, 1650,
3857, 552, 2765, 1108, 3330, 1112, 2228, 3906, 3913, 2800,
4488, 1124, 3941, 2256, 2825, 3962, 2268, 4544, 3983, 1140,
5139, 2288, 573, 4592, 2300, 4608, 4039, 2890, 1737, 580,
4648, 4074, 1166, 1752, 5265, 2930, 1174, 1764, 1178, 3540,
2955, 4144, 2965, 1782, 4760, 5364, 4179, 1196, 2995, 2400,
601, 2408, 4824, 604, 1815, 5454, 4249, 5472, 1827, 5490,
5499, 4896, 3065, 4912, 615, 2464, 1851, 5562, 2476, 1240,
1863, 5598, 3738, 4992, 1250, 3130, 4389, 3768, 2516, 630,
631, 1896, 2532, 3804, 1905, 2544, 1911, 5742, 639, 3200,
4487, 5136, 1929, 1288, 3870, 646, 1941, 4536, 4543, 3900,
3906, 652, 3265, 1962, 5240, 2624, 3285, 1974, 659, 3960,
1983, 5296, 5304, 3320, 2660, 1332, 5336, 2672, 5352, 4690,
4697, 2016, 3365, 4718, 1350, 5408, 4062, 2712, 3395, 2040,
681, 6138, 683, 2052, 1370, 5488, 3435, 2752, 6201, 3450,
6219, 1384, 693, 5552, 2780, 1392, 4879, 698, 3495, 2100,
4907, 6318, 4218, 6336, 4935, 4942, 4949, 2124, 6381, 710,
2133, 4984, 6417, 2856, 5005, 5728, 6453, 1436, 1438, 5760,
2884, 722, 723, 2896, 5800, 1452, 2181, 2184, 1458, 5840,
4386, 5856, 3665, 1468, 5145, 1472, 4422, 2214, 1478, 2220,
2223, 3710, 6687, 1488, 4470, 5222, 6723, 3740, 5992, 6000,
3004, 752, 6024, 1508, 3020, 3780, 2271, 5306, 5313, 2280,
2283, 762, 763, 5348, 6885, 4596, 5369, 4608, 6152, 6160,
4626, 772, 773, 4644, 6975, 4656, 2331, 4668, 1558, 6240,
3124, 2346, 6264, 7056, 3140, 786, 3148, 3152, 3945, 7110,
4746, 3960, 5551, 3970, 1590, 5572, 797, 4788, 799, 4800,
4005, 4812, 4818, 4020, 1610, 2418, 7263, 1616, 6472, 810,
6488, 7308, 813, 3256, 6520, 1632, 3268, 818, 4095, 4920,
5747, 7398, 823, 3296, 3300, 826, 827, 3312, 4974, 6640,
5817, 6656, 4165, 2502, 1670, 3344, 2511, 838, 3356, 840,
6728, 1684, 5901, 6752, 4225, 4230, 7623, 5936, 2547, 1700,
851, 7668, 853, 1708, 3420, 3424, 7713, 1716, 4295, 4300,
861, 1724, 1726, 2592, 1730, 2598, 5202, 3472, 2607, 7830,
1742, 872, 873, 6992, 5250, 3504, 1754, 2634, 7032, 1760,
3524, 7056, 1766, 4420, 6195, 2658, 5322, 5328, 1778, 1780,
8019, 8028, 893, 894, 1790, 896, 2691, 7184, 3596, 2700,
6307, 3608, 903, 5424, 8145, 5436, 6349, 7264, 7272, 2730,
911, 1824, 913, 8226, 3660, 5496, 8253, 918, 1838, 920,
8289, 7376, 923, 6468, 7400, 8334, 6489, 7424, 6503, 8370,
931, 2796, 2799, 934, 5610, 1872, 5622, 938, 939, 1880,
2823, 7536, 1886, 944, 6615, 4730, 5682, 5688, 2847, 5700,
3804, 1904, 3812, 1908, 6685, 956, 1914, 3832, 7672, 5760,
2883, 8658, 5778, 2892, 8685, 8694, 2901, 3872, 8721, 970,
4855, 1944, 7784, 5844, 2925, 2928, 8793, 5868, 5874, 1960,
1962, 8838, 1966, 3936, 8865, 5916, 3948, 988, 8901, 1980,
3964, 992, 993, 7952, 995, 7968, 6979, 2994, 1998, 7000};
printarray(num_elements, data);
quicksort(data, 0, num_elements - 1, &count);
printarray(num_elements, data);
printf("it took %d goes", count);
return 0;
}
void printarray(const int x, const int data[])
{
int i, j = 0;
for (i = 0; i < x; i++)
{
if (j == 10)
{
printf("\n");
j = 0;
}
printf("%5d ", data[i]);
j++;
}
printf("\n");
}
void quicksort(int data[], int first, int last, int *count)
{
int i, j, pivot, temp;
*count += 1;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(data[i]<=data[pivot]&&i<last)
i++;
while(data[j]>data[pivot])
j--;
if(i<j)
{
temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
temp=data[pivot];
data[pivot]=data[j];
data[j]=temp;
quicksort(data,first,j-1, count);
quicksort(data,j+1,last, count);
}
}