FilesExpand file tree

 master

/

radixSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (49 loc) · 1.32 KB

 master

/

radixSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (49 loc) · 1.32 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

import java.io.*;

import java.util.*;

class Radix {

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;

}

static void countSort(int arr[], int n, int exp)

{

int output[] = new int[n];

int i;

int count[] = new int[10];

Arrays.fill(count,0);

for (i = 0; i < n; i++)

count[ (arr[i]/exp)%10 ]++;

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

for (i = n - 1; i >= 0; i--)

{

output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

count[ (arr[i]/exp)%10 ]--;

}

for (i = 0; i < n; i++)

arr[i] = output[i];

}

static void radixsort(int arr[], int n)

{

int m = getMax(arr, n);

for (int exp = 1; m/exp > 0; exp *= 10)

countSort(arr, n, exp);

}

static void print(int arr[], int n)

{

for (int i=0; i<n; i++)

System.out.print(arr[i]+" ");

}

public static void main (String[] args)

{

int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

int n = arr.length;

radixsort(arr, n);

print(arr, n);

}

}

// Written by James Mc Dermott(theycallmemac)