Minimum number of swaps required to sort an array

By | November 27, 2016
Minimum number of swaps required to sort an array

Minimum number of swaps required to sort an array

Problem Statement

Here Swap means removing element from array and append it to the back of the array. Given an array of integers find the minimum number of swaps needed to sort the array.

Example 1:

Input Array Example[] = [7,3,4,1]  By swapping 1 and 7, we get [1,3,4,7]. So,here one swap is the best solution.

Example 2:

Input Array Example[] = [1,2,6,4,8,7,9]. We first swap 6 with 4, so, Example[] = [1,2,4,6,8,7,9]. Then 7 with 8. So -> [1,2,4,6,7,8,9].So,here two swaps are the best solution

Example 3:

Input Array Example[] = [2,5,4,3]  By swapping 5 and 3, we get [2,3,4,5]. So,here one swap is the best solution.

Example 4:

Input Array Example[] = [3,1,5,2,4]  By swapping 5 and 3, we get [2,3,4,5]. So,here one swap is the best solution.

Idea Behind the Main Program

Find the Elements that are already sorted and focus on the rest of the elements for swapping.

Let’s go through the program logic.

public static int minimumSwap (int[] inputarray) 

{

    int[] sorted = new int[inputarray.length];//take new array of size of the input array

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

     sorted[i] = inputarray[i];

   }//copy the input array into sorted array using for loop

   int n = sizeof(arr)/sizeof(arr[0]);

   //now sort the inputarray using below method.

   inputarray.sort(inputarray,inputarray+n);

   int j = 0;

   //now compare the sorted array with input array

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

    if (inputarray[i] == sorted[j])

    j++;
 
   }

   //now we have count of not moved elements.Just subtract it from array lengths,

   will get the  minimum number of swaps required to sort.

   return array.length - j;

}

// Driver program to test the above minSwap Method.

int main()

{

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

    if (inputarray == null || inputarray.length == 0)

    throw new IllegalArgumentException("Invalid input Array");

    cout << minimumSwap(inputarray);

    return 0;

}

The following two tabs change content below.

SRINIVAS DARIPELLI

Myself SRINIVAS DARIPELLI. I have 15+ Years of Experience in Programming worked on multiple technologies.Apart from it,I am a blogger, writer, editor, artist and dad 🙂 .I believe in reality.I love to share the Helpful things around the Technology. Feel free to connect with me

Leave a Reply