FilesExpand file tree

 master

/

BubbleSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (54 loc) · 1.52 KB

 master

/

BubbleSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (54 loc) · 1.52 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

/* Bubble Sort is an algorithm to sort an array. It

* compares adjacent element and swaps their position

* The big O on bubble sort in worst and best case is O(N^2).

* Not efficient.

* Somehow if the array is sorted or nearly sorted then we can optimize bubble sort by adding a flag.

*

* In bubble sort, we keep iterating while something was swapped in

* the previous inner-loop iteration. By swapped I mean, in the

* inner loop iteration, we check each number if the number proceeding

* it is greater than itself, if so we swap them.

*

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

* Animated Visual: https://www.toptal.com/developers/sorting-algorithms/bubble-sort

*/

/**

* Using 2 for loops.

*/

export function bubbleSort (items) {

const length = items.length

let noSwaps

for (let i = length; i > 0; i--) {

// flag for optimization

noSwaps = true

// Number of passes

for (let j = 0; j < (i - 1); j++) {

// Compare the adjacent positions

if (items[j] > items[j + 1]) {

// Swap the numbers

[items[j], items[j + 1]] = [items[j + 1], items[j]]

noSwaps = false

}

}

if (noSwaps) {

break

}

}

return items

}

/**

* Using a while loop and a for loop.

*/

export function alternativeBubbleSort (arr) {

let swapped = true

while (swapped) {

swapped = false

for (let i = 0; i < arr.length - 1; i++) {

if (arr[i] > arr[i + 1]) {

[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]

swapped = true

}

}

}

return arr

}