fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void countingSort(int[] arr, int n, int exp) {
  5.         int[] output = new int[n];
  6.         int[] count = new int[10];
  7.  
  8.         for (int i = 0; i < n; i++) {
  9.             count[(arr[i] / exp) % 10]++;
  10.         }
  11.  
  12.         for (int i = 1; i < 10; i++) {
  13.             count[i] += count[i - 1];
  14.         }
  15.  
  16.         for (int i = n - 1; i >= 0; i--) {
  17.             output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  18.             count[(arr[i] / exp) % 10]--;
  19.         }
  20.  
  21.         for (int i = 0; i < n; i++) {
  22.             arr[i] = output[i];
  23.         }
  24.     }
  25.  
  26.     public static void radixSort(int[] arr, int n) {
  27.         if (n == 0) return;
  28.  
  29.         int maxVal = arr[0];
  30.         for (int i = 1; i < n; i++) {
  31.             if (arr[i] > maxVal) {
  32.                 maxVal = arr[i];
  33.             }
  34.         }
  35.  
  36.         for (int exp = 1; maxVal / exp > 0; exp *= 10) {
  37.             countingSort(arr, n, exp);
  38.         }
  39.     }
  40.  
  41.     public static void main(String[] args) {
  42.         Scanner scanner = new Scanner(System.in);
  43.  
  44.         int n = scanner.nextInt();
  45.         int[] arr = new int[n];
  46.  
  47.         for (int i = 0; i < n; i++) {
  48.             arr[i] = scanner.nextInt();
  49.         }
  50.  
  51.         radixSort(arr, n);
  52.  
  53.         for (int i = 0; i < n; i++) {
  54.             System.out.print(arr[i] + " ");
  55.         }
  56.         System.out.println();
  57.         scanner.close();
  58.     }
  59. }
Success #stdin #stdout 0.17s 56904KB
comments (?)
stdin
copy 
7
10 5 8 4 3 11 1
stdout
copy 
1 3 4 5 8 10 11
https://ideone.com/ry7gv3
language:
Java (HotSpot 12)
created:
2 days 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!