FilesExpand file tree

 master

/

BeadSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (48 loc) · 1.4 KB

 master

/

BeadSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (48 loc) · 1.4 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

/**

* Bead Sort, also known as Gravity sort.

*

* This algorithm was inspired from natural phenomena and was designed keeping in mind objects (or beads) falling under

* the influence of gravity.

*

* NOTE: It only works for arrays of positive integers.

*

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

*/

export function beadSort (sequence) {

/* Let's ensure our sequence has only Positive Integers */

if (sequence.some((integer) => integer < 0)) {

throw RangeError('Sequence must be a list of Positive integers Only!')

}

const sequenceLength = sequence.length

const max = Math.max(...sequence)

// Set initial Grid

const grid = sequence.map(number => {

const maxArr = new Array(max)

for (let i = 0; i < number; i++) {

maxArr[i] = '*'

}

return maxArr

})

// Drop the Beads!

for (let col = 0; col < max; col++) {

let beadsCount = 0

for (let row = 0; row < sequenceLength; row++) {

if (grid[row][col] === '*') {

beadsCount++

}

}

for (let row = sequenceLength - 1; row > -1; row--) {

if (beadsCount) {

grid[row][col] = '*'

beadsCount--

} else {

grid[row][col] = undefined

}

}

}

/* Finally, let's turn our Bead rows into their Respective Numbers */

return grid.map((beadArray) => {

const beadsArray = beadArray.filter(bead => bead === '*')

return beadsArray.length

})

}