FilesExpand file tree

 main

/

BucketSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (58 loc) · 2.19 KB

 main

/

BucketSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (58 loc) · 2.19 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

/**

* BucketSort implementation.

*

* Wikipedia says: Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array

* into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by

* recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the

* most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be

* implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational

* complexity estimates involve the number of buckets.

*

* @see https://en.wikipedia.org/wiki/Bucket_sort#:~:text=Bucket%20sort%2C%20or%20bin%20sort,applying%20the%20bucket%20sorting%20algorithm.&text=Sort%20each%20non%2Dempty%20bucket.

*

* Time Complexity of Solution:

* Best Case O(n); Average Case O(n); Worst Case O(n)

*

* @param {number[]} list The array of numbers to be sorted.

* @param {number} size The size of the buckets used. If not provided, size will be 5.

* @return {number[]} An array of numbers sorted in increasing order.

*/

export function bucketSort (list, size) {

if (undefined === size) {

size = 5

}

if (list.length === 0) {

return list

}

let min = list[0]

let max = list[0]

// find min and max

for (let iList = 0; iList < list.length; iList++) {

if (list[iList] < min) {

min = list[iList]

} else if (list[iList] > max) {

max = list[iList]

}

}

// how many buckets we need

const count = Math.floor((max - min) / size) + 1

// create buckets

const buckets = []

for (let iCount = 0; iCount < count; iCount++) {

buckets.push([])

}

// bucket fill

for (let iBucket = 0; iBucket < list.length; iBucket++) {

const key = Math.floor((list[iBucket] - min) / size)

buckets[key].push(list[iBucket])

}

const sorted = []

// now sort every bucket and merge it to the sorted list

for (let iBucket = 0; iBucket < buckets.length; iBucket++) {

const arr = buckets[iBucket].sort((a, b) => a - b)

for (let iSorted = 0; iSorted < arr.length; iSorted++) {

sorted.push(arr[iSorted])

}

}

return sorted

}