fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class countingSortWithNegative{
  5. 	public static void main(String[] arg) throws IOException{
  6. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7.  
  8. 		int len = Integer.parseInt(br.readLine());
  9. 	//	int range = Integer.parseInt(br.readLine());
  10.  
  11. 		String st[] = br.readLine().split(" ");
  12.  
  13. 		int arr[] = new int[len];
  14.  
  15. 		int i;
  16.  
  17. 		for(i = 0; i < len; i++){
  18. 			arr[i] = Integer.parseInt(st[i]);
  19. 		}
  20.  
  21. 		countSort(arr);
  22. 	}
  23.  
  24. 	static void countSort(int arr[]){
  25. 		int len = arr.length;
  26.  
  27. 		int min = arr[0];
  28. 		int max = arr[0];
  29. 		int i;
  30. 		for(i = 1 ; i < len; i++){
  31. 			if(arr[i] > max){
  32. 				max = arr[i];
  33. 			}
  34. 			else if(arr[i] < min){
  35. 				min = arr[i];
  36. 			}
  37. 		}
  38. 		int range = max-min+1;
  39.  
  40. 		int count[] = new int[range+1];
  41.  
  42. 		for(i = 0 ; i < len; i++){
  43. 			count[arr[i]-min]++;
  44. 		}
  45.  
  46. 		for(i = 1; i < count.length; i++){
  47. 			count[i] += count[i-1];
  48. 		}
  49.  
  50. 		int result[] = new int[len];
  51.  
  52. 		for(i = len-1; i >= 0; i--){
  53. 			result[count[arr[i]-min]-1] = arr[i];
  54. 			count[arr[i]-min]--;
  55. 		}
  56.  
  57. 		for(i = 0 ; i <len; i++){
  58. 			System.out.print(result[i] + " ");
  59. 		}
  60. 	}
  61. }
Success #stdin #stdout 0.06s 3359744KB
comments (?)
stdin
copy 
10
-5 -1 0 5 -3 10 9 1 12 4
stdout
copy 
-5 -3 -1 0 1 4 5 9 10 12
https://ideone.com/QBLo9h
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!