## Monday, November 28, 2016

### Minimum number of swaps required to sort an array - GeeksforGeeks

Related: Number of swaps to sort when only adjacent swapping allowed
Minimum number of swaps required to sort an array - GeeksforGeeks
Given an array of n distinct elements, find the minimum number of swaps required to sort the array.

This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i’th index must be present at j’th index in the sorted array.
```
Graph for {4, 3, 2, 1}
```
The graph will now contain many non-intersecting cycles. Now a cycle with 2 nodes will only require 1 swap to reach the correct ordering, similarly a cycle with 3 nodes will only require 2 swap to do so.
```
Graph for {4, 5, 2, 1, 5}
```
Hence,

• ans = Σi = 1k(cycle_size – 1)

• where k is the number of cycles
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
`    ``public` `static` `int` `minSwaps(``int``[] arr)`
`    ``{`
`        ``int` `n = arr.length;`

`        ``// Create two arrays and use as pairs where first`
`        ``// array is element and second array`
`        ``// is position of first element`
`        ``ArrayList <Pair <Integer, Integer> > arrpos =`
`                  ``new` `ArrayList <Pair <Integer, Integer> > ();`
`        ``for` `(``int` `i = ``0``; i < n; i++)`
`             ``arrpos.add(``new` `Pair <Integer, Integer> (arr[i], i));`

`        ``// Sort the array by array element values to`
`        ``// get right position of every element as the`
`        ``// elements of second array.`
`        ``arrpos.sort(``new` `Comparator<Pair<Integer, Integer>>()`
`        ``{`
`            ``@Override`
`            ``public` `int` `compare(Pair<Integer, Integer> o1,`
`                               ``Pair<Integer, Integer> o2)`
`            ``{`
`                ``if` `(o1.getValue() > o2.getValue())`
`                    ``return` `-``1``;`

`                ``// We can change this to make it then look at the`
`                ``// words alphabetical order`
`                ``else` `if` `(o1.getValue().equals(o2.getValue()))`
`                    ``return` `0``;`

`                ``else`
`                    ``return` `1``;`
`            ``}`
`        ``});`

`        ``// To keep track of visited elements. Initialize`
`        ``// all elements as not visited or false.`
`        ``Boolean[] vis = ``new` `Boolean[n];`
`        ``Arrays.fill(vis, ``false``);`

`        ``// Initialize result`
`        ``int` `ans = ``0``;`

`        ``// Traverse array elements`
`        ``for` `(``int` `i = ``0``; i < n; i++)`
`        ``{`
`            ``// already swapped and corrected or`
`            ``// already present at correct pos`
`            ``if` `(vis[i] || arrpos.get(i).getValue() == i)`
`                ``continue``;`

`            ``// find out the number of  node in`
`            ``// this cycle and add in ans`
`            ``int` `cycle_size = ``0``;`
`            ``int` `j = i;`
`            ``while` `(!vis[j])`
`            ``{`
`                ``vis[j] = ``true``;`

`                ``// move to next node`
`                ``j = arrpos.get(j).getValue();`
`                ``cycle_size++;`
`            ``}`

`            ``// Update answer by adding current cycle.`
`            ``ans += (cycle_size - ``1``);`
`        ``}`

`        ``// Return result`
`        ``return` `ans;`
`    ``}`

http://www.geeksforgeeks.org/minimum-swap-required-convert-binary-tree-binary-search-tree/
Given the array representation of Complete Binary Tree i.e, if index i is the parent, index 2*i + 1 is the left child and index 2*i + 2 is the right child. The task is to find the minimum number of swap required to convert it into Binary Search Tree.
The idea is to use the fact that inorder traversal of Binary Search Tree is in increasing order of their value.
So, find the inorder traversal of the Binary Tree and store it in the array and try to sort the array. The minimum number of swap required to get the array sorted will be the answer. Please refer below post to find minimum number of swaps required to get the array sorted.
Exercise: Can we extend this to normal binary tree, i.e., a binary tree represented using left and right pointers, and not necessarily complete?
http://stackoverflow.com/questions/15152322/compute-the-minimal-number-of-swaps-to-order-a-sequence/15152602#15152602