Search
 
SCRIPT & CODE EXAMPLE
 

JAVA

radix sort

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10,i)) % 10
}

function digitCount(num) {
  if(num === 0 ) return 1
  return Math.floor(Math.log10(Math.abs(num))) + 1
}

function mostDigitCount(nums) {
  let maxDigit = 0
  for(let i = 0;i< nums.length;i++) {
    maxDigit = Math.max(maxDigit, digitCount(nums[i]))
  }
  return maxDigit
}

function Radix(nums){
  let maxDigitCount = mostDigitCount(nums)
  for(let k=0; k< maxDigitCount; k++) {
    let digitbucket = Array.from({length:10} , () => [])
    for(let i=0; i< nums.length; i++) {
      let digit = getDigit(nums[i], k)
      digitbucket[digit].push(nums[i])
    }
    nums = [].concat(...digitbucket)
  }
  return nums
}

console.log(Radix([23,123, 23333,444444,55555555]))
Comment

radix sort

function countingSort(arr, size, place){
  
  let output = new Array(size + 1).fill(0);
  let max = Math.max(...arr);
  
  let freq = new Array(max + 1).fill(0);
  
  // Calculate count of elements
  for (let i = 0; i < size; i++){
      const num = Math.floor(arr[i] / place) % 10;
      freq[num]++;
  }
  
  // Calculate cummulative count
  for (let i = 1; i < 10; i++){
      freq[i] += freq[i - 1];
  }

  // Place the elements in sorted order
  for (let i = size - 1; i >= 0; i--) {
      const num = Math.floor(arr[i] / place) % 10;
      output[freq[num] - 1] = arr[i];
      freq[num]--;
  }
  
  //Copy the output array
  for (let i = 0; i < size; i++){
    arr[i] = output[i];
  }
}

function radixSort(arr, size = arr.length){
  //Get the max element
  let max = Math.max(...arr);
  
  //Sort the array using counting sort
  for(let i = 1; parseInt(max / i) > 0; i *= 10){
    countingSort(arr, size, i);
  }
}
Comment

radix sort

// Radix sort Java implementation
import java.io.*;
import java.util.*;
 
class Radix {
 
    // A utility function to get maximum value in arr[]
    static 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.
    static void countSort(int arr[], int n, int exp)
    {
        int output[] = new int[n]; // output array
        int i;
        int count[] = new int[10];
        Arrays.fill(count, 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
    static void radixsort(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
    static void print(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
 
    /*Driver Code*/
    public static void main(String[] args)
    {
        int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
        int n = arr.length;
           
          // Function Call
        radixsort(arr, n);
        print(arr, n);
    }
}
/* This code is contributed by Devesh Agrawal */
Comment

Radix sort

1 #include <assert.h>
   2 #include <limits.h>
   3 #include <string.h>
   4 
   5 #include "radixsort.h"
   6 
   7 /* in-place MSB radix sort for null-terminated strings */
   8 
   9 /* helper routine for swapping */
  10 static void
  11 swapStrings(const char **a, const char **b)
  12 {
  13     const char *temp;
  14 
  15     temp = *a;
  16     *a = *b;
  17     *b = temp;
  18 }
  19 
  20 /* this is the internal routine that assumes all strings are equal for the
  21  * first k characters */
  22 static void
  23 radixSortInternal(int n, const char **a, int k)
  24 {
  25     int i;
  26     int count[UCHAR_MAX+1];  /* number of strings with given character in position k */
  27     int mode;                /* most common position-k character */
  28     const char **bucket[UCHAR_MAX+1]; /* position of character block in output */
  29     const char **top[UCHAR_MAX+1];    /* first unused index in this character block */
  30 
  31     /* loop implements tail recursion on most common character */
  32     while(n > 1) {
  33 
  34         /* count occurrences of each character */
  35         memset(count, 0, sizeof(int)*(UCHAR_MAX+1));
  36 
  37         for(i = 0; i < n; i++) {
  38             count[(unsigned char) a[i][k]]++;
  39         }
  40 
  41         /* find the most common nonzero character */
  42         /* we will handle this specially */
  43         mode = 1;
  44         for(i = 2; i < UCHAR_MAX+1; i++) {
  45             if(count[i] > count[mode]) {
  46                 mode = i;
  47             }
  48         }
  49 
  50         if(count[mode] < n) {
  51 
  52             /* generate bucket and top fields */
  53             bucket[0] = top[0] = a;
  54             for(i = 1; i < UCHAR_MAX+1; i++) {
  55                 top[i] = bucket[i] = bucket[i-1] + count[i-1];
  56             }
  57 
  58             /* reorder elements by k-th character */
  59             /* this is similar to dutch flag algorithm */
  60             /* we start at bottom character and swap values out until everything is in place */
  61             /* invariant is that for all i, bucket[i] <= j < top[i] implies a[j][k] == i */
  62             for(i = 0; i < UCHAR_MAX+1; i++) {
  63                 while(top[i] < bucket[i] + count[i]) {
  64                     if((unsigned char) top[i][0][k] == i) {
  65                         /* leave it in place, advance bucket */
  66                         top[i]++;
  67                     } else {
  68                         /* swap with top of appropriate block */
  69                         swapStrings(top[i], top[(unsigned char) top[i][0][k]]++);
  70                     }
  71                 }
  72             }
  73 
  74             /* we have now reordered everything */
  75             /* recurse on all but 0 and mode */
  76             for(i = 1; i < UCHAR_MAX+1; i++) {
  77                 if(i != mode) {
  78                     radixSortInternal(count[i], bucket[i], k+1);
  79                 }
  80             }
  81 
  82             /* tail recurse on mode */
  83             n = count[mode];
  84             a = bucket[mode];
  85             k = k+1;
  86 
  87         } else {
  88 
  89             /* tail recurse on whole pile */
  90             k = k+1;
  91         }
  92     }
  93 }
  94 
  95 void
  96 radixSort(int n, const char **a)
  97 {
  98     radixSortInternal(n, a, 0);
  99 }
Comment

Radix Sort

Used to sort integer numbers
sort by:
first sorting the first rightmost digit of every number
then move to the next number to the left and then sort it (if no such digit exists, then it is 0).
after we're totally done, the numbers will be sorted in order.

for example
10, 5, 4, 3, 2
in this case:
if we want to sort these in ascending order
the first sort will result in
10, 2, 3, 4, 5
10 will be the "smallest" number
however, the next sort with the next digit will put things in proper order
In that case we are sorting
1-0, 0-2, 0-3, 0-4, 0-5
1 is (obviously) the largest of the digits. 
So it is in the rightest.
The correct order is now 2,3,4,5,10
Comment

PREVIOUS NEXT
Code Example
Java :: object in java 
Java :: method overloading 
Java :: extends class in java 
Java :: Add Elements in java map 
Java :: android studio tabbed activity 
Java :: java unicode characters 
Java :: java pass by reference 
Java :: |= java operation 
Java :: javafx 
Java :: Java Access LinkedList elements 
Java :: android java how to stop users fromgoing back too much 
Java :: enter a word and print letters java 
Java :: in dom parser how to find processing instruction in java 
Java :: prefix vs postfix increment java 
Java :: method object class in android 
Java :: java method overloading 
Java :: android adb is using too much cpu 
Java :: AccountDriver.java 
Java :: functionality of consumer functional interface in java 
Java :: Calculator repeat 
Java :: how to select a audio from android programmaticly 
Java :: print method in java 
Java :: how to switch between two stylesheets in javafx. 
Java :: java platform runlater keeps running 
Java :: java catch stop signal 
Java :: lcd initialize arduino 
Java :: spring import properties file xml 
Java :: resources/android/xml/network_security_config.xml 
Java :: enum to get status name from list using status id 
Java :: Spring security avec spring version 2.5.6 
ADD CONTENT
Topic
Content
Source link
Name
3+6 =