- Prepare
- Algorithms
- Sorting
- Counting Sort 1
- Discussions

# Counting Sort 1

# Counting Sort 1

+ 0 comments php :

**Time Complexity:**The program has two loops. The first loop has a constant number of iterations, i.e., 100 iterations. Therefore, the time complexity of the first loop is O(1).

The second loop has n iterations, where n is the size of the input array. Inside the loop, a constant amount of work is done in each iteration, i.e., incrementing the counter at an index in the frequency array. Therefore, the time complexity of the second loop is O(n).

Thus, the overall time complexity of the program is O(n).

**Space Complexity:**The program creates a new array of size 100 to store the frequency counts. Therefore, the space complexity of the program is O(1) for the frequency array.

In addition, the program uses a few constant amount of space to store the input array and some loop variables. Therefore, the space complexity of the program is also O(1) for these variables.

Thus, the overall space complexity of the program is O(1).

function countingSort($arr) { // Write your code here $res = []; for($i=0;$i<100;$i++){ if(!isset($res[$i])){ $res[$i] = 0; } } for($i=0;$i<count($arr);$i++){ $res[$arr[$i]]++; } return $res; }

+ 0 comments C++ solution

vector<int> countingSort(vector<int> arr) { vector<int>mp(arr.size()); for(auto it:arr){ mp[it]++; } return mp; }

+ 0 comments **Solution in Python 3**def countingSort(arr): arr.sort() result = [] sorted_tuple = tuple(arr) for i in range(100): value = sorted_tuple.count(i) result.append(value) return result

+ 0 comments py

def countingSort(a): r=[0 for i in range(100)] for i in a: r[i]+=1 return r

+ 0 comments public static List<Integer> countingSort(List<Integer> arr) { int[] frequency = new int[100]; for(int i = 0; i < arr.size(); i++) { frequency[arr.get(i)] = ++frequency[arr.get(i)]; } List<Integer> answer = Arrays.stream(frequency) .boxed() .collect(Collectors.toList()); return answer; }

Sort 414 Discussions, By:

Please Login in order to post a comment