FilesExpand file tree

 master

/

RadixSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (43 loc) · 1.32 KB

 master

/

RadixSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (43 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

package Sorts;

import java.util.Arrays;

class RadixSort {

private 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;

}

private 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];

}

private 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)