steinmal The problem description should be more clear about what a counting sort algorithm actually is. I see alot of people here sorting in all sorts of different ways, when they are intended to use a specific algorithm, counting sort.
TLS210051 Accepted Java Code.
import java.io.; import java.util.;
public class Solution {
public static void main(String[] args) { Scanner in=new Scanner(System.in); int n,i,j; n=in.nextInt(); int A[]=new int[n]; for(i=0;i<n;i++) { int x= in.nextInt(); A[x]++; } for(i=0;i<100;i++) { for(j=0;j<A[i];j++) System.out.print(i+" "); } }}
mohammedsaleem71 what is A[x]++ doing??
abhishek_singh13 I Think it is there for reading elements in that array a.
daiict_201712019 A[x] is used to increment the count in the array for that element
mohammedsaleem71 why are we using j
TLS210051 We need to print sorted elkements n no. of times as it appears. So we are first counting the no. of times the NUMBER appears between 1 to 100 and then storing (no. of times it appears) in the respective Array index.
e.g if 3 appears 5 times. We have A[3]=5;
In that way, we use j index to access sequentially all elements to print them That many times as they appear.
Anuragkumarsingh Can u please! clear my doubt what if input is:
n=6
ar={45 23 66 45 9 20}
Hooseinsaid then the output should be {9 20 23 45 45 66}
you just have to sort the integers as its in the previous array. they all should have same size. no different only sorted.
jcleyton Easy to understand Python3 solution
def count(ar): out = [0] * 100 for i in ar: out[i] += 1 return out def printOrdered(arr): for i in range(0, 100): for j in range(0, arr[i]): print(i, end=' ') m = input() ar = [int(i) for i in input().strip().split()] printOrdered(count(ar))
chirag851 n = int(input()) ar = list(map(int, input().strip().split(" "))) ar.sort() print(*ar)
alphasingh The problem wants us to use the counting sort specifically
abhiramsatpute shorter and accepted too
from collections import Counter n, a =int(input()), list(map(int, input().split())) print(*(Counter(sorted(a)).elements()))
GeoMatt22 A more "Pythonic" (?) version of the printer might be:
def printOrdered(counts): values = [] for i in range(len(counts)): values += counts[i] * [i] print(*values) return values # optional: output sorted array
(probably less clear though!)
jcleyton You're totally right :D
I didn't know about print(*something) when I wrote that answer.
sfelde21 what does print(*something) do?
GeoMatt22 The
*is used for iterable unpacking. Soprint(*x)is shorthand forprint(x[0], x[1], ..., x[-1])
ashsingh1 Actual simple counting sort algorithm. The point is here to write a counting sort not show how you can reduce the number of lines by using inbuilt sort function.
public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int arr[] = new int[n]; for(int i = 0; i < n; i++){ arr[i] = in.nextInt(); } int[] sortedArr = sort(arr); print(sortedArr); } static void print(int[] arr){ for(int i = 1; i < arr.length; i++){ System.out.print(arr[i] + " "); } System.out.println(); } static int[] sort(int[] arr){ int[] count = new int[100]; int[] newArr = new int[arr.length + 1]; for(int i = 0; i < arr.length; i++){ count[arr[i]]++; } for(int i = 0; i < count.length - 1; i++){ count[i + 1] = count[i] + count[i + 1]; } for(int i = 0; i < arr.length; i++){ int index = arr[i]; int indexCount = count[index]--; newArr[indexCount] = index; } return newArr; } }
sanjugodara13 here your code consist of so many line the simpler way to do this problem
Scanner in = new Scanner(System.in); int N= in.nextInt(); int[] arr = new int[N]; int[] a = new int[N]; for(int i=0;i<N;i++){ arr[i]=in.nextInt(); a[arr[i]]++; } for(int j=0;j<100;j++){ for(int k=0;k<a[j];k++){ System.out.print(j +" "); } }
itsrmani pretty cool to Arrays.sort command
public static void main(String[] args) { int a,i; Scanner sc=new Scanner(System.in); a=sc.nextInt(); int arr[]=new int[a]; for(i=0;i<a;i++) arr[i]=sc.nextInt(); Arrays.sort(arr); for(i=0;i<a;i++) System.out.print(arr[i] + " "); }
bibhas_abhishek The problem wants you to use counting sort, not the Java library.
vkasojhaa Even simpler, you dont need 2 arrays. We can use a variable and an array.
Scanner in = new Scanner(System.in); int N= in.nextInt(); int[] a = new int[N]; for(int i=0;i<N;i++){ int p =in.nextInt(); a[p]++; } for(int j=0;j<100;j++){ for(int k=0;k<a[j];k++){ System.out.print(j +" "); } }
sam_fold His code was readable though, yours isn't!
hbti_ankit1994 [deleted]hbti_ankit1994 int[] a = new int[N]; //This Line could be Optimized int[] a = new int[100];// as x is always less than 100 Hence Saving Memory
Reshetnyak My JavaScript solution:
function countingSort(arr) { counter=new Array(arr.length).fill(0) result=[] for(let value of arr){ counter[value]+=1 } let index=0 for(let value of counter){ result.push(...Array(value).fill(index)) index+=1 } return result }
wingz86 function processData(input) { var numCounts = []; var sortedArray = []; input = input.split(" "); input[0] = input[0].replace(/.*[0-9]\n/,""); input = input.map(function(value) { return parseInt(value) });
input.forEach(function(value) { numCounts[value] = numCounts[value] + 1 || 1; }); //index of each numCounts value is the value! for (var i = 0; i < numCounts.length; i++) { //input each index numCounts[i] number of times into sortedArray for (var j = 0; j < numCounts[i]; j++) { sortedArray.push(i); } } console.log(sortedArray.join(" "));}
wingz86 sorry not sure how to fix this editing
chadwalt Awesome solution. I actually didn't think of it this way. I have come up with my own solution basing on yours.
function processData(input) { //Enter your code here var numCounts = []; // Will hold the number of counts. var sortedArray = []; // Will hold the sorted array input = input.split("\n"); // Split to get the inputs. let elements = input[1].split(" ").map(Number); elements.forEach(function(value) { // Using the array elements as keys and counts as values. numCounts[value] = numCounts[value] + 1 || 1; }); // Loop through the array. for (var i = 0; i < numCounts.length; i++) { // Each index of numCounts has a value count. // This loop inserts into the sortedArray depending on the counts for (var j = 0; j < numCounts[i]; j++) { sortedArray.push(i); } } console.log(sortedArray.join(" ")); }
kovab93 Short, not cheating python solution:
n = int(raw_input()) cnt = [0] * 100 for i in map(int, raw_input().split()): cnt[i] += 1 print "".join((str(i) + " ") * x for i, x in enumerate(cnt))
lhs_santoss C99 Solution:
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { int n; scanf("%d", &n); int i,j,array[100] = {0}; for(i=0;i<n;i++) { int num; scanf("%d", &num); array[num]++; } for(i=0; i< 100; i++) { for(j=0; j<array[i]; j++) { printf("%d ", i); } } }
jasoncadahia Correct me if I'm wrong, but this just prints numbers, correct? So if the user's input array was an array of objects, such as files, this would not sort them? Not quite sure, but I thought this solution was otherwise elegant.
ser_jamie Simple code in java
public class Solution { static int num; public static void main(String[] args) { Scanner se=new Scanner(System.in); int n=se.nextInt(); int ar[]=new int[n]; int num[]=new int[n]; int max=0; for(int i=0;i<n;i++){ ar[i]=se.nextInt(); if(ar[i]>max) max=ar[i]; num[ar[i]]++; } for(int i=0;i<=max;i++){ for(int j=0;j<num[i];j++){ System.out.print(i+" "); } } } }
hashimshafiq0 All my test case passess expect the last one. It gives time terminated error. What is the problem.? Here is my code http://pastebin.com/r3hpmC3c
lakshmanLD you are implementing selection sort. o(n^2). Try implementing selection sort which is o(n+k).
anchitgupt I didn't get it!
Sort 145 Discussions, By:
Please Login in order to post a comment