FilesExpand file tree

 master

/

BucketSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

112 lines (96 loc) · 2.51 KB

 master

/

BucketSort.java

Top

File metadata and controls

• Code
• Blame

112 lines (96 loc) · 2.51 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

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

package Sorts;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Random;

/** Wikipedia: https://en.wikipedia.org/wiki/Bucket_sort */

public class BucketSort {

public static void main(String[] args) {

int[] arr = new int[10];

/* generate 10 random numbers from -50 to 49 */

Random random = new Random();

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

arr[i] = random.nextInt(100) - 50;

}

bucketSort(arr);

/* check array is sorted or not */

for (int i = 0, limit = arr.length - 1; i < limit; ++i) {

assert arr[i] <= arr[i + 1];

}

}

/**

* BucketSort algorithms implements

*

* @param arr the array contains elements

*/

private static void bucketSort(int[] arr) {

/* get max value of arr */

int max = max(arr);

/* get min value of arr */

int min = min(arr);

/* number of buckets */

int numberOfBuckets = max - min + 1;

List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);

/* init buckets */

for (int i = 0; i < numberOfBuckets; ++i) {

buckets.add(new ArrayList<>());

}

/* store elements to buckets */

for (int value : arr) {

int hash = hash(value, min, numberOfBuckets);

buckets.get(hash).add(value);

}

/* sort individual bucket */

for (List<Integer> bucket : buckets) {

Collections.sort(bucket);

}

/* concatenate buckets to origin array */

int index = 0;

for (List<Integer> bucket : buckets) {

for (int value : bucket) {

arr[index++] = value;

}

}

}

/**

* Get index of bucket which of our elements gets placed into it.

*

* @param elem the element of array to be sorted

* @param min min value of array

* @param numberOfBucket the number of bucket

* @return index of bucket

*/

private static int hash(int elem, int min, int numberOfBucket) {

return (elem - min) / numberOfBucket;

}

/**

* Calculate max value of array

*

* @param arr the array contains elements

* @return max value of given array

*/

public static int max(int[] arr) {

int max = arr[0];

for (int value : arr) {

if (value > max) {

max = value;

}

}

return max;

}

/**

* Calculate min value of array

*

* @param arr the array contains elements

* @return min value of given array

*/

public static int min(int[] arr) {

int min = arr[0];

for (int value : arr) {

if (value < min) {

min = value;

}

}

return min;

}

}