Find minimum "swaps" needed to sort an array

An operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array. 

Eg :- 3124 
Output: 2 (3124->1243->1234) 

How to do it less than O(n^2) ?

Doing it in less than O(n^2) time means that we cannot actually perform the "swap". The idea is that we need to calculate the number of elements that are already sorted in the array, and the rest elements needs to be "swapped".

e.g., 3124: 1, 2 are sorted, swap 3, 4
7, 9, 8, 3, 5: 3, 5 are sorted, swap 7, 9, 8

public static int minSwap(int[] array) {
  if (array == null || array.length == 0)
   throw new IllegalArgumentException("Invalid input!");
  int[] sorted = new int[array.length];
  for (int i = 0; i < array.length; i++) {
   sorted[i] = array[i];
  }
  Arrays.sort(sorted);
  int j = 0;
  for (int i = 0; i < array.length; i++) {
   if (array[i] == sorted[j])
    j++;
  }
  return array.length - j;
 }