FilesExpand file tree

 master

/

CountingSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (46 loc) · 1.34 KB

 master

/

CountingSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (46 loc) · 1.34 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

// Java implementation of Counting Sort

class CountingSort

{

void sort(char arr[])

{

int n = arr.length;

// The output character array that will have sorted arr

char output[] = new char[n];

// Create a count array to store count of inidividul

// characters and initialize count array as 0

int count[] = new int[256];

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

count[i] = 0;

// store count of each character

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

++count[arr[i]];

// Change count[i] so that count[i] now contains actual

// position of this character in output array

for (int i=1; i<=255; ++i)

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

// Build the output character array

// To make it stable we are operating in reverse order.

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

{

output[count[arr[i]]-1] = arr[i];

--count[arr[i]];

}

// Copy the output array to arr, so that arr now

// contains sorted characters

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

arr[i] = output[i];

}

// Driver method

public static void main(String args[])

{

CountingSort ob = new CountingSort();

char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o',

'r', 'g', 'e', 'e', 'k', 's'

};

ob.sort(arr);

System.out.print("Sorted character array is ");

for (int i=0; i<arr.length; ++i)

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

}

}

/*This code is contributed by Rajat Mishra */