fork download 
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <fstream>
  5. #include <string>
  6. #include <time.h>
  7. #include <sstream>
  8.  
  9. using namespace std;
  10.  
  11. int getMax(int arr[], int n)
  12. {
  13.     int max = arr[0];
  14.     for (int i = 1; i < n; i++)
  15.         if (arr[i] > max)
  16.             max = arr[i];
  17.     return max;
  18. }
  19.  
  20. void countSort(int arr[], int n, int exp)
  21. {
  22.     int output[n];
  23.     int i, count[10] = {0};
  24.     for (i = 0; i < n; i++)
  25.         count[(arr[i] / exp) % 10]++;
  26.     for (i = 1; i < 10; i++)
  27.         count[i] += count[i - 1];
  28.     for (i = n - 1; i >= 0; i--)
  29.     {
  30.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  31.         count[(arr[i] / exp) % 10]--;
  32.     }
  33.     for (i = 0; i < n; i++)
  34.         arr[i] = output[i];
  35. }
  36.  
  37. void radixsort(int arr[], int n)
  38. {
  39.     clock_t clockStart;
  40.     clockStart = clock();
  41.  
  42.     int m = getMax(arr, n);
  43.     for (int exp = 1; m / exp > 0; exp *= 10)
  44.         countSort(arr, n, exp);
  45.  
  46.     cout << "\nTime taken by radix sort: " << (double)(clock() - clockStart) / CLOCKS_PER_SEC << endl;
  47. }
  48.  
  49. int StrToInt(string sti) 
  50. {
  51.     int f;
  52.     stringstream ss(sti); //turn the string into a stream
  53.     ss >> f;
  54.     return f;
  55. }
  56.  
  57. int main()
  58. {
  59.     int arr[10000];
  60.     int n = 0;
  61.     while(cin >> arr[n]) {
  62.     	n++;
  63.     }
  64.     radixsort(arr, n);
  65.     for (int i = 0; i < n; i++) {
  66.         cout << arr[i] << "\n";
  67.     }
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
1244 3455 6565 55 765 8768 687 879
stdout 
Time taken by radix sort: 3e-06
55
687
765
879
1244
3455
6565
8768
https://ideone.com/wfXxsl
language:
C++14 (gcc 8.3)
created:
8 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!