Minimum number of swaps required to sort an array - 2

Software Development
#1

Approach: As Pair class available in java from java 8 so we can use hashmap in older java version.

Below is the implementation of the idea.

import java.util.*;

import java.io.*;

class GfG

{

// Function returns the

// minimum number of swaps

// required to sort the array

public static int minSwaps( int [] nums)

{

int len = nums.length;

HashMap<Integer, Integer> map = new HashMap<>();

for ( int i= 0 ;i<len;i++)

map.put(nums[i], i);

Arrays.sort(nums);

// To keep track of visited elements. Initialize

// all elements as not visited or false.

boolean [] visited = new boolean [len];

Arrays.fill(visited, false );

// Initialize result

int ans = 0 ;

for ( int i= 0 ;i<len;i++) {

// already swapped and corrected or

// already present at correct pos

if (visited[i] || map.get(nums[i]) == i)

continue ;

int j = i, cycle_size = 0 ;

while (!visited[j]) {

visited[j] = true ;

// move to next node

j = map.get(nums[j]);

cycle_size++;

}

// Update answer by adding current cycle.

if (cycle_size > 0 ) {

ans += (cycle_size - 1 );

}

}

return ans;

}

}

// Driver class

class MinSwaps

{

// Driver program to test the above function

public static void main(String[] args)

{

int []a = { 1 , 5 , 4 , 3 , 2 };

GfG g = new GfG();

System.out.println(g.minSwaps(a));

}

}

Time Complexity: O(n Log n)

Auxiliary Space: O(n)

Straight forward solution

While iterating over the array, check the current element, and if not in the correct place, replace that element with the index of the element which should have come in this place.

Below is the implementation of the above approach:

// Java program to find

// minimum number of swaps

// required to sort an array

import java.util.*;

import java.io.*;

class GfG

{

// Return the minimum number

// of swaps required to sort the array

public int minSwaps( int [] arr, int N)

{

int ans = 0 ;

int [] temp = Arrays.copyOfRange(arr, 0 , N);

Arrays.sort(temp);

for ( int i = 0 ; i < N; i++)

{

// This is checking whether

// the current element is

// at the right place or not

if (arr[i] != temp[i])

{

ans++;

// Swap the current element

// with the right index

// so that arr[0] to arr[i] is sorted

swap(arr, i, indexOf(arr, temp[i]));

}

}

return ans;

}

public void swap( int [] arr, int i, int j)

{

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public int indexOf( int [] arr, int ele)

{

for ( int i = 0 ; i < arr.length; i++)

{

if (arr[i] == ele) {

return i;

}

}

return - 1 ;

}

}

// Driver class

class Main

{

// Driver program to test

// the above function

public static void main(String[] args)

throws Exception

{

int [] a

= { 101 , 758 , 315 , 730 , 472 ,

619 , 460 , 479 };

int n = a.length;

// Output will be 5

System.out.println( new GfG().minSwaps(a, n));

}

}

Output:

5

Time Complexity: O(n*n)
Auxiliary Space: O(n)