# mimic the array swaps from a sort

• Last Update :
• Techknowledgy :

Minimum number of swaps required to sort an array,Given an array of n distinct elements, find the minimum number of swaps required to sort the array.,Same as before, make a new array (called temp), which is the sorted form of the input array. We know that we need to transform the input array to the new array (temp) in the minimum number of swaps. Make a map that stores the elements and their corresponding index, of the input array.,Minimum swaps required to bring all elements less than or equal to k together

`2`

`5`

Suggestion : 2

### C++ Code

```void dfs(vector & lt; int & gt; vec[], vector & lt; bool & gt; & amp; vis, int node, int & amp; compSize) {
vis[node] = true;
compSize += 1;
for (auto x: vec[node]) {
if (!vis[x]) {
dfs(vec, vis, x, compSize);
}
}
}
int minimumSwaps(vector & lt; int & gt; & amp; a, int n) {
vector & lt;
int & gt;
vec[n + 1];
vector & lt;
pair & lt;
int, int & gt; & gt;
aux;
for (int i = 0; i & lt; n; i++) {
pair & lt;
int, int & gt;
p = {
a[i],
i + 1
};
aux.push_back(p);
}
sort(aux.begin(), aux.end());
for (auto x: aux) {
cout & lt; & lt;
x.first & lt; & lt;
" " & lt; & lt;
x.second & lt; & lt;
endl;
}
vector & lt;
bool & gt;
vis(n + 1, false);
for (int i = 0; i & lt; n; i++) {
vec[aux[i].second].push_back(i + 1);
}
int ans = 0;
for (int i = 1; i & lt; = n; i++) {
if (!vis[i]) {
int compSize = 0;
dfs(vec, vis, i, compSize);
ans += (compSize - 1);
}
}
return ans;
}```

### Java Code

```public class Pair & lt;
T, U & gt; {
private final T key;
private final U value;

public Pair(T key, U value) {
this.key = key;
this.value = value;
}

public T getKey() {
return this.key;
}

public U getValue() {
return this.value;
}
}
public void dfs(ArrayList & lt; Integer & gt; vec[], boolean[] vis, int node, int[] compSize) {
vis[node] = true;
compSize[0] += 1;
for (int i = 0; i & lt; vec[node].size(); i++) {
if (!vis[(int) vec[node].get(i)]) {
dfs(vec, vis, vec[node].get(i), compSize);
}
}
}
public int minimumSwaps(int[] a, int n) {
ArrayList & lt;
Pair & lt;
Integer, Integer & gt; & gt;
aux = new ArrayList & lt;
Pair & lt;
Integer, Integer & gt; & gt;
();
for (int i = 0; i & lt; n; i++) {
aux.add(new Pair & lt; Integer, Integer & gt;
(a[i], i + 1));
}
aux.sort(new Comparator & lt; Pair & lt; Integer, Integer & gt; & gt;
() {
public int compare(Pair & lt; Integer, Integer & gt; first, Pair & lt; Integer, Integer & gt; second) {
if (first.key & gt; second.key) {
return 1;
} else if (first.key & lt; second.key) {
return -1;
} else {
return 0;
}
}
});
boolean[] vis = new boolean[n + 1];
for (int i = 0; i & lt; = n; i++) {
vis[i] = false;
}
ArrayList & lt;
Integer & gt;
vec[] = new ArrayList[n + 1];
for (int i = 0; i & lt; n; i++) {
vec[i + 1] = new ArrayList & lt; & gt;
();
}
for (int i = 0; i & lt; n; i++) {
}
int ans = 0;
for (int i = 1; i & lt; = n; i++) {
int[] compSize = new int[1];
compSize[0] = 0;
if (!vis[i]) {
dfs(vec, vis, i, compSize);
ans += (compSize[0] - 1);
}
}
return ans;
}```

### Python Code

```def dfs(vec, vis, node, compSize):
vis[node] = True
compSize[0] += 1
for x in vec[node]:
if not vis[x]:
dfs(vec, vis, x, compSize)

def minimumSwaps(a, n):
aux = [ * enumerate(a)]
aux.sort(key = lambda it: it[1])
vis = [False] * (n + 1)
vec = [
[]
for i in range(n + 1)
]
for i in range(n):
vec[aux[i][0] + 1].append(i + 1)
ans = 0
for i in range(1, n + 1):
compSize = [0]
if not vis[i]:
dfs(vec, vis, i, compSize)
ans += compSize[0] - 1
return ans```

### Java Code

```public static int minimumSwaps(int[] a, int n) {
HashMap & lt;
Integer, Integer & gt;
m = new HashMap & lt;
Integer, Integer & gt;
();
int[] copy = new int[n];
for (int i = 0; i & lt; n; i++) {
copy[i] = a[i];
}
Arrays.sort(copy);
for (int i = 0; i & lt; n; i++) {
m.put(copy[i], i + 1);
}
int moves = 0;
for (int i = 0; i & lt; n; i++) {
if ((i + 1) != (int) m.get(a[i])) {
int temp = a[i];
int pos = m.get(a[i]) - 1;
a[i] = a[pos];
a[pos] = temp;
moves++;
}
}
return moves;
}```

### Python Code

```def minimumSwaps(a, n):
copy = a.copy()
copy.sort()
m = {}
for i in range(n):
m[copy[i]] = i + 1
moves = 0
for i in range(n):
if (i + 1) != m[a[i]]:
temp = a[i]
pos = m[a[i] - 1]
a[i] = a[pos]
a[pos] = temp
moves += 1
return moves```

Suggestion : 3

There were names for all of the important things that went on here: breaking a stack into two smaller stacks was known as partitioning, and the value we chose to use as the division point in partitioning is called the "pivot". The algorithm for quick sort is fairly easy: if we want to sort elements left through right of our array, chose some pivot value, partition the elements into parts, put the pivot value into the appropriate location, and then recursively sort each of our two parts. , Suppose we are unlucky though: suppose we break our array such that we put n-1 elements in the left and 1 element in the right. Then, our time becomes: , Stable sorting: Stability has to do with sorting algorithms deal with duplicate values in our array. A stable algorithm is one which keeps these elements in the same relative order: if an element was further to the left of a duplicate value, when we are done sorting these element should still be to the left. , We will discuss 5 algorithms that sort these elements, and compare and contrast them to see which algorithm may be best in a given situation.

bubbleSort(A)
Input: an unsorted array, A
Postcondition: A is sorted in ascending order

```    for pass = 1 to length(A) - 1
for j = 0 to length(A) - pass
if A[j] > A[j + 1]
swap(A, j, j + 1)```

SelectionSort(A)
Input: an unsorted array, A
Postcondition: A is sorted in ascending order

```    for s = 0 to length(A) - 2
m = s
for i = s + 1 to length(A) - 1
if A[i] < A[m]
m = i
swap(A, s, m)```

insertionSort(A)
Input: an unsorted array, A
Postcondition: A is sorted in ascending order

```    for j = 1 to length(A) - 1
key = A[j]
i = j - 1
while i >= 0 && A[i] > key
A[i + 1] = A[i]
i--
A[i + 1] = key```

merge(left_array, right_array)
Input: two sorted arrays
Returns: A single sorted array whose elements were all contained in left_array and right_array

```    left_index = 0
right_index = 0
merged_index = 0

while (left_index < length(left_array) && (right_index < length(right_array) if left_array[left_index] <= right_array[right_index] merged_array[merged_index++] = left_array[left_index++]
else
merged_array[merged_index++] = right_array[right_index++]

// Copy all of the remaining left_array into the merged_array
while left_index < length(left_array) merged_array[merged_index++] = left_array[left_index++]

// Copy all of the remaining right_array into the merged_array
while right_index < length(right_atrray) merged_array[merged_index++] = right_array[right_index++]```

mergeSort(A, left, right)
Input: An unsorted array
Returns: An array with A's elements in ascending order

```    if (length(A) <= 1)
return A
center = (length(A) - 1) / 2
unsorted_left = copyArray(A, 0, center)
unsorted_right = copyArray(A, center + 1, length(A) - 1)
sorted_left = mergeSort(unsorted_left)
sorted_right = mergeSort(unsorted_right)
return merge(sorted_left, sorted_right)```
Time Analysis
```T(n) = O(n / 2) + // Copying left half
O(n / 2) + // Copying right half
T(n / 2) + // Sorting left half
T(n / 2) + // Sorting right half
O(n) // Merging our halves together

= 2 * O(n / 2) + O(n) + 2 * T(n / 2) = 2 * O(n) + 2 * T(n / 2)```
```T(n) = 2*O(n) + 2*(2*O(n/2) + 2*T(n/4))
= 2*O(n) + 2*(O(n) + 2*T(n/4))
= 2*O(n) + (2*O(n) + 4*T(n/4))
```
`T(n) = 2 * O(n) + 2 * O(n) + (2 * O(n) + 8 * T(n / 8))`
```T(n) = 2*O(n) + 2*O(n) + (2*O(n) + 8*T(n/8))
```
`T(n) = 2 * O(n) + 2 * O(n) + 2 * O(n) + ... + 2 * O(n) + x * T(1)`

quickSort(A, left, right)
Input: An unsorted array, A, left and right indices into A
Postcondition: Elements of A between left and right are sorted

```    if (left < right)
middle = partition(A, left, right)
quickSort(A, left, middle - 1)
quickSort(A, middle + 1, right)```
Input: An unsorted array, A, left and right indices into A
Postcondition: creates a middle element such that for all indices l in [left, middle), A[l] <= A[middle] and for all indices r, (middle, right], A[r] >= A[middle]
Returns: the middle index which satisfies above
```    if right - left <= 1
if A[left > A[right] swap(array, left, right) return left

pivot_position = choosePivot(array, left, right) pivot = A[pivot_position] l = left r = right swap(A, pivot_position, right)

while l < r
while A[l] <= pivot && l < right l++
while A[r] > pivot && r > left r--
if l < r swap(A, l, r)

middle = l swap(A, middle, right) return middle```

```Several possibilities:
return left
return random(left, right)
return median(A[left], A[(left + right) / 2], A[right])```
Input: An unsorted array, A, left and right indices into A
Postcondition: creates a middle element such that for all indices l in [left, middle), A[l] <= A[middle] and for all indices r, (middle, right], A[r] >= A[middle]
Returns: the middle index which satisfies above
```    if right - left <= 1
if A[left > A[right] swap(array, left, right) return left

pivot_position = choosePivot(array, left, right) pivot = A[pivot_position] l = left r = right swap(A, pivot_position, right)

while l < r
while A[l] <= pivot && l < right l++
while A[r] > pivot && r > left r--
if l < r swap(A, l, r)

middle = l swap(A, middle, right) return middle```

```Several possibilities:
return left
return random(left, right)
return median(A[left], A[(left + right) / 2], A[right])```