1 Couting Sort You may have learned some sorting algorithms such as bubble sort and quicksort in CS 110 and CS 210. This homework is about counting sort. Let n be the number of elements to be sorted. Bubble sort and quicksort assume that we can compare any pair of elements and find out, in constant time, which one is larger and which one is smaller. They make no assumption on the values of the elements. Counting sort assumes the elements are integers between 0 and m, and m is much smaller than n. For example, let m be 3, and n be 10. Then the elements can be 0, 1, or 2, and we have ten of them. unsigned data [10] unsigned count [3]; = {0, 2, 1, 1, 0, 2, 2, 0, 1, 1}; Counting sort uses an array unsigned count [m] and initializes all elements in count to zero. Then we scan the array data. When we see a number data[i], this number is used as the index to the array count, and the corresponding count is incremented. After we finish scanning the array data, we have count [0] == 3, count [1] == 4, and count [2] == 3. How do we construct the sorted array from these counts? We write 0 for count [0] times, 1 for count [1] times, and 2 for count [2] times. Bubble sort takes O(n²) time in the worst case, and quicksort takes O(n lg n) time on average. Loosely speaking, quicksort is faster than bubble sort. You will learn the big-O notation in CS 310. Counting sort takes O(m+n) time. We say it is a linear time algorithm, which is, loosely speaking, faster than quicksort. The code in main.c is the driver. You implement counting sort in cntSort.c. The driver runs your counting sort as well as qsort () in the standard library. It verifies that your code works correctly, and reports the runtime of both sorting methods. 2* implementation of counting sort 3* 4 project: hw5 5 * name! 6 * user?? 7 * date: 8 file: cntSort.c 9* pseudo code: 10 * notes: 11 */ 12 13#include <stdlib.h> 14 15void cntSort(unsigned m, unsigned n, unsigned data[]) 16{ 17 unsigned *count; 18 19 allocate memory */ 20 count (unsigned *)malloc(sizeof(unsigned) * m); 21 = 22 / free up memory */ 23 free(count); 24} 25