radix_serial.c

// C++ implementation of Radix Sort 
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
  
// A utility function to get maximum value in arr[] 
int getMax(int arr[], int n) 
{ 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > mx) 
            mx = arr[i]; 
    return mx; 
} 
  
// A function to do counting sort of arr[] according to 
// the digit represented by exp. 
void countSort(int arr[], int n, int exp) 
{ 
    int output[n]; // output array 
    int i, count[10] = {0}; 
  
    // Store count of occurrences in count[] 
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 
  
    // Change count[i] so that count[i] now contains actual 
    //  position of this digit in output[] 
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    // Build the output array 
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 
  
    // Copy the output array to arr[], so that arr[] now 
    // contains sorted numbers according to current digit 
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
// The main function to that sorts arr[] of size n using  
// Radix Sort 
void radix_sort(int arr[], int n) 
{ 
    // Find the maximum number to know number of digits 
    int m = getMax(arr, n); 
  
    // Do counting sort for every digit. Note that instead 
    // of passing digit number, exp is passed. exp is 10^i 
    // where i is current digit number 
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 
} 
  
// A utility function to print an array 
// void print(int arr[], int n) 
// { 
//     for (int i = 0; i < n; i++) 
//         cout << arr[i] << " "; 
// } 

void rng(int* arr, int n) {
    int seed = 13515024; // Ganti dengan NIM anda sebagai seed.
    srand(seed);
    for(long i = 0; i < n; i++) {
        arr[i] = (int)rand();
    }
}

// Driver program to test above functions 
int main(int argc, char *argv[]) 
{ 
    int n = strtol(argv[1], NULL, 10);
    struct timeval start, end;
    long double cpu_time_used = 0.0;
    int arr[400000] = {0};

    FILE *o_file;

    o_file = fopen("output.txt","w");

    rng(arr, n);
    gettimeofday(&start, NULL);
    radix_sort(arr, n);
    gettimeofday(&end, NULL);
    // for (int i = 0; i < n; i++) {
    //     printf("%d ", arr[i]);
    // }
    for (int i = 0; i < n; i++) {
        if (i == n-1)
            fprintf(o_file,"%d", arr[i]);
        else
            fprintf(o_file,"%d, ",arr[i]);
    }
    fclose(o_file);

    cpu_time_used = (end.tv_sec - start.tv_sec)*1e6;
    cpu_time_used = (long double) (cpu_time_used + (end.tv_usec - start.tv_usec))*1e-6;
    cpu_time_used *= 1000;
    printf("Time of execution: %Le microseconds\n", cpu_time_used);
    return 0; 
}