We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The Full Counting Sort
The Full Counting Sort
+ 0 comments public static void countSort(List<List<String>> arr) { int middle = arr.size() / 2; int temp[] = new int[100]; Map<Integer, List<String>> map = new HashMap<>(); // Traverse the list and populate hashmap // with keys being the "weight" of the pair. // Also replace the str to "-" if it is between [0..n/2]. for(int i = 0; i < arr.size(); i++) { List<String> a = arr.get(i); int weight = Integer.parseInt(a.get(0)); String str = a.get(1); if(i < middle) { str = "-"; } temp[weight]++; if(map.containsKey(weight)) { map.get(weight).add(str); } else { map.put(weight, new ArrayList<String>()); map.get(weight).add(str); } } // The base of count sort adapted to // this challenge. for(int i = 0; i < temp.length; i++) { int repeat = temp[i]; for (int j = 0; j < repeat; j++) { System.out.print(map.get(i).get(j) + " "); } } }
+ 0 comments def countSort(arr): # Write your code here # the number of element in the array_res is max(arr[:,0]) + 1 length_arr_res = 0 for i in arr: if int(i[0]) > int(length_arr_res): length_arr_res = int(i[0]) arr_res = [[] for i in range(length_arr_res+1)] # find first half array and convert it to '-'. for i in range(len(arr)//2): arr_res[int(arr[i][0])].append('-') # add last half array for i in range(len(arr)//2,len(arr)): arr_res[int(arr[i][0])].append(arr[i][1]) # print it out for i in arr_res: for j in i: print(j,end=' ')
+ 0 comments -- JavaScript --
function countSort(arr) { // Write your code here const obj = {}; const mid = arr.length / 2; arr.forEach((e, i) => { if (i < mid) { if (obj[e[0]]) obj[e[0]].push('-'); else obj[e[0]] = ['-'] return } if (obj[e[0]]) obj[e[0]].push(e[1]) else obj[e[0]] = [e[1]] }) console.log(Object.values(obj).map((e) => e.join(' ')).join(' ')); }
+ 0 comments Hope this helps, this is my solution in C
void countSort(int arr_rows, int arr_columns, char*** arr) { int i; int range[100] = {0}; int new_range[100] = {0}; char ** res = (char**)malloc(sizeof(char) * 10 * arr_rows); // step 0: replace first half with '-' for (i = 0; i < arr_rows / 2; i++) strcpy(arr[i][1], "-"); // step 1: populating range for (i = 0; i < arr_rows; i++){ int num = atoi(arr[i][0]); range[num]++; } // step 2: inctremting range for (i = 1; i < 100; i++) range[i] += range[i - 1]; // step 3: shifting range array by 1 for (i = 1; i < 100; i++) new_range[i] = range[i - 1]; // step 4: sort for (i = 0; i < arr_rows; i++){ int num = atoi(arr[i][0]); int r_i = new_range[num]; res[r_i] = arr[i][1]; new_range[num]++; } // step 5: print sorting result for (i = 0; i < arr_rows; i++) printf("%s ", res[i]); free(res); printf("\n"); }
+ 0 comments Very hard to understand the problem statement. Not very hard to solve.
Explanation:
- For each, track each digit char (arr[0])
- For each string char (arr[1]) , associate it with the digit (arr[0]) in the tracker, keeping them in order
- But, if point is less than midpoint or arr, insert "-" instead
No Idea how to do it in C though. Can't even index into the correct part of the array without a seg fault occuring.
Load more conversations
Sort 670 Discussions, By:
Please Login in order to post a comment