FilesExpand file tree

 master

/

CycleSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (54 loc) · 1.61 KB

 master

/

CycleSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (54 loc) · 1.61 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

/**

* Cycle sort is an in-place, unstable sorting algorithm,

* a comparison sort that is theoretically optimal in terms of the total

* number of writes to the original array, unlike any other in-place sorting

* algorithm. It is based on the idea that the permutation to be sorted can

* be factored into cycles, which can individually be rotated to give a sorted result.

*

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

*/

/**

* cycleSort takes an input array of numbers and returns the array sorted in increasing order.

*

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

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

*/

function cycleSort (list) {

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

let value = list[cycleStart]

let position = cycleStart

// search position

for (let i = cycleStart + 1; i < list.length; i++) {

if (list[i] < value) {

position++

}

}

// if it is the same, continue

if (position === cycleStart) {

continue

}

while (value === list[position]) {

position++

}

const oldValue = list[position]

list[position] = value

value = oldValue

// rotate the rest

while (position !== cycleStart) {

position = cycleStart

for (let i = cycleStart + 1; i < list.length; i++) {

if (list[i] < value) {

position++

}

}

while (value === list[position]) {

position++

}

const oldValueCycle = list[position]

list[position] = value

value = oldValueCycle

}

}

return list

}

export { cycleSort }