FilesExpand file tree

 master

/

SwapSort.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

31 lines (29 loc) · 992 Bytes

 master

/

SwapSort.js

Copy path

Top

File metadata and controls

• Code
• Blame

31 lines (29 loc) · 992 Bytes

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

/**

* @function SwapSort

* @description Swap Sort is an algorithm to find the number of swaps required to sort an array.

Time complexity of Swap Sort Algorithm is O(nlogn).

Auxiliary Space required for Swap Sort Algorithm is O(n).

* @param {Integer[]} items - Array of integers

* @return {Integer} - Number of swaps required to sort the array.

* @see [SwapSort](https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/)

*/

export function minSwapsToSort (items) {

const sortedArray = items.slice()

sortedArray.sort()

const indexMap = {}

for (let i = 0; i < items.length; i++) {

indexMap[items[i]] = i

}

let swaps = 0

for (let i = 0; i < items.length; i++) {

if (items[i] !== sortedArray[i]) {

const temp = items[i]

items[i] = items[indexMap[sortedArray[i]]]

items[indexMap[sortedArray[i]]] = temp

indexMap[temp] = indexMap[sortedArray[i]]

indexMap[sortedArray[i]] = i

swaps++

}

}

return swaps

}