8.2.4. Make an array Count[0...k] which stores the frequency of each element in the range 0 to k.Now, make another array Cumulative[0...k+1] which store the cumulative values corresponding to the Count array already made with Cumulative[0] = 0.
Then the answer to every query will be Cumulative[b+1] -Cumulative[a].
We can also save space by making the Cumulative array in the Count array itself.
8.3.2. Insertion Sort and Merge Sort are stable sorting algorithms.Whereas Quicksort satbility depends upon the implementation and Heap Sort isn't stable.
Maintaining Stability: We can maintain stability by keeping the index of the element along with the element values and breaking ties based on the element which has lower index.
8.3.4. Since we know the range we can employ Counting Sort algorithm to achieve O(n) time complexity.
8.2. (a.) Counting Sort
(b.) Counting Sort and Quicksort both can be used.(Think about the implementation using quicksort)
(c.) Insertion Sort
(d.)
(e.) For sorting the numbers inplace we can use counting sort method in which the first k indices of the array itself represents the count of each element in the input array.
Algorithm: (i.) Traverse the input array from left to right.
(ii.) For each element make A[A[i]%(k+1)] = A[A[i]%(k+1)] + (k+1) where i is the index used in the loop.
(iii.) Now again traverse the array A from 0 to K-1 and print each value A[i]/(k+1) times.
Thus we've the sorted array as output.
