FilesExpand file tree

 master

/

BucketSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (60 loc) · 2.06 KB

 master

/

BucketSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (60 loc) · 2.06 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

/**

* BucketSort: mainly sort an array with elements uniformly distributed over a range.

*

* Worst Case Time Complexity: O(n^2).

* Best and Average Case Time Complexity: O(n + k).

* Space Complexity: O(n * k).

*

*/

import java.util.Arrays;

import java.util.List;

import java.util.ArrayList;

/**

* http://www.growingwiththeweb.com/2015/06/bucket-sort.html

*/

public class BucketSort {

private static final int DEFAULT_BUCKET_SIZE = 5;

public static void sort(int[] arr) {

bucketSort(arr, DEFAULT_BUCKET_SIZE);

}

public static void bucketSort(int arr[], int size) {

if (arr.length == 0) return;

Integer minValue = arr[0];

Integer maxValue = arr[0];

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

if (arr[i] < minValue) {

minValue = arr[i];

} else if (arr[i] > maxValue) {

maxValue = arr[i];

}

}

int bucketCount = (maxValue - minValue) / size + 1;

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

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

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

}

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

buckets.get((arr[i] - minValue) / size).add(arr[i]);

}

int currentIndex = 0;

for (int i = 0; i < buckets.size(); i++) {

Integer[] bucketArray = new Integer[buckets.get(i).size()];

bucketArray = buckets.get(i).toArray(bucketArray);

InsertionSort.sort(bucketArray);

for (int j = 0; j < bucketArray.length; j++) {

arr[currentIndex++] = bucketArray[j];

}

}

}

public static void main(String[] args) {

int[] arr1 = {10, 3, 7, 5, 1, 15, 20};

BucketSort.sort(arr1);

System.out.println(Arrays.toString(arr1));

int[] arr2 = {};

BucketSort.sort(arr2);

System.out.println(Arrays.toString(arr2));

int[] arr3 = {10};

BucketSort.sort(arr3);

System.out.println(Arrays.toString(arr3));

}

}