#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define MAX 50


double getRandomNumber(double min, double max)
{
    double range = max - min;
    double randomNum = (double)rand() / RAND_MAX;
    return min + randomNum * range;
}



void counting_sort(int array[], int size, int place) {
  const int max = 10;
  int output[size];
  int count[max];

  for (int i = 0; i < max; ++i)
    count[i] = 0;

  for (int i = 0; i < size; i++)
    count[(array[i]/place) % 10]++;

  for (int i = 1; i < max; i++)
    count[i] += count[i - 1];

  for (int i = size - 1; i >= 0; i--) {
    output[count[(array[i]/place) % 10] - 1] = array[i];
    count[(array[i]/place) % 10]--;
  }

  for (int i = 0; i < size; i++)
    array[i] = output[i];
}

void radixsort(int array[], int size) {
  int max = abs(array[0]);
  for (int i = 1; i < size; i++)
    if (abs(array[i]) > max)
      max = abs(array[i]);

  for (int place = 1; max/place > 0; place *= 10)
    counting_sort(array, size, place);
}

void split_and_sort(int arr[], int n) {
    int max = 0;
    for(int i = 0; i < n; i++) {
        if(abs(arr[i]) > max) {
            max = abs(arr[i]);
        }
    }

    int negCount = 0, posCount = 0;
    int negArray[n], posArray[n];
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            negArray[negCount++] = -arr[i];
        } else {
            posArray[posCount++] = arr[i];
        }
    }

    radixsort(negArray, negCount);
    radixsort(posArray, posCount);

    for(int i = 0; i < negCount / 2; i++) {
        int temp = negArray[i];
        negArray[i] = negArray[negCount - i - 1];
        negArray[negCount - i - 1] = temp;
    }

    printf("Array after sorting: \n");
    for(int i = 0; i < negCount; i++) {
        printf("%d ", -negArray[i]);
    }
    for(int i = 0; i < posCount; i++) {
        printf("%d ", posArray[i]);
    }
}

int main() {
  int array[] = {19, -52, 53, 56, -12, 46, 91, 76, -23, -82, 88, -38, -73, 14, 49, -3, -39, 58, -79, 98, 90, 37, 18, 25, 94, -78, -4, -80, 34, -32, -63, -46, 14, 89, -89, -97, 36, -97, 78, -86, -80, 66, -25, -54, -18, -76, 42, 41, 82, 62};
  int n = sizeof(array)/sizeof(array[0]);
  split_and_sort(array, n);
  return 0;
}