Minimum number of swaps needed to sort the array

Question

I have an array of size n, which contain elements from 1 to n, in random order. So, we'd have as input an unordered array of integers.

Considering I can swap any two elements any number of times, how can I find minimum numbers of such swap to make array sorted?

Answer 1

Here is my code for minimumsawap function using java 7

static int minimumSwaps(int[] arr) {
        int c=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=(i+1)){
                int t= arr[i];
                arr[i]=arr[t-1];
                arr[t-1]=t;
                c++;
                i=0;
            }
        }
        return c;
    }

Answer 2

There's an interesting take in GeeksForGeeks with

• Time Complexity: O(N) where N is the size of the array.
• Auxiliary Space: O(1)

The used approach was

1. For each index in arr[], check if the current element is in it’s right position or not. Since the array contains distinct elements from 1 to N, we can simply compare the element with it’s index in array to check if it is at its right position.
2. If current element is not at it’s right position then swap the element with the element which has occupied its place (using temp variable)
3. Else check for next index (i += 1)

This is the code

def minimumSwaps(arr):
    min_num_swaps = 0; 
    i = 0; 
    while (i < len(arr)):  
        if (arr[i] != i + 1): 
            while (arr[i] != i + 1): 
                temp = 0; 
                temp = arr[arr[i] - 1]; 
                arr[arr[i] - 1] = arr[i]; 
                arr[i] = temp; 
                min_num_swaps += 1; 

        i += 1; 
      
    return min_num_swaps;

that could easily be updated to

• Remove semicolons

• Remove the need for temp

• Substitute len(arr) with a given integer input n with the size of the array

  def minimumSwaps(arr):
      min_num_swaps = 0
      i = 0
      while (i < n-1):  
          if (arr[i] != i + 1): 
              while (arr[i] != i + 1): 
                  arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1]
                  min_num_swaps += 1
  
          i += 1; 
  
       return min_num_swaps
  

They both are gonna pass all the current 15 Test cases in HackerRank

Answer 3

I'll try to answer this question using javascript. This is most optimal code I have tried so far :

function minimumSwaps(arr) {
    var arrLength = arr.length;

    // create two new Arrays 
    // one record value and key separately
    // second to keep visited node count (default set false to all)

    var newArr = [];
    var newArrVisited = [];
    for (let i = 0; i < arrLength; i++) {
        newArr[i]= [];
        newArr[i].value = arr[i];
        newArr[i].key = i;
        newArrVisited[i] = false;
    }

    // sort new array by value

    newArr.sort(function (a, b) {
        return a.value - b.value;
    })

    var swp = 0;
    for (let i = 0; i < arrLength; i++) {

        // check if already visited or swapped
        if (newArr[i].key == i || newArrVisited[i]) {
            continue;
        }

        var cycle = 0;
        var j = i;
        while (!newArrVisited[j]) {

            // mark as visited
            newArrVisited[j] = true;
            j = newArr[j].key; //assign next key
            cycle++;
        }
        if (cycle > 0) {
            swp += (cycle > 1) ? cycle - 1 : cycle;
        } 

    }
    return swp;
}

reference -1

reference -2

Answer 4

Hackerrank Python code for minimum swaps 2 using hashmaps

length = int(input())
arr= list(map(int,input().split()))
hashmap = {}

for i in range(0,len(arr)):
    hashmap[i+1] = [arr[i],False]

swap_count = 0
for e_pos, e_val in hashmap.items():
    if e_val[1] == False:
        e_val[1] = True
        if e_pos == e_val[0]:
            continue
        else:
            c = e_val[0]
            while hashmap[c][1] == False:
                hashmap[c][1] = True
                b = hashmap[c][0]
                c = b
                swap_count+=1
print(swap_count)

Answer 5

This can be done in O(n). Assuming elements are in range 1 to n and there're no duplicates.

noofswaps = 0
for i in range(len(A)):
    while A[i] != i + 1:
        temp = A[i]
        A[i] = A[A[i] - 1]
        A[temp - 1] = temp
        noofswaps += 1
print noofswaps

Answer 6

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean newarr[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,count=0;

            while(!newarr[j]){
                newarr[j]=true;
                j=arr[j]-1;
                count++;
            }

            if(count!=0)
                swap+=count-1;
        }
        return swap;
}