2

Given an array with distinct elements, what is the minimum number of swap needed to sort it?

For example, the array [4, 2, 1, 3] needs at least 2 swaps (e.g. swapping 4 and 1 then 4 and 3).

This is my approach:

B = sort(copy(A))
for i = 0 ... len(A) - 1
    if A[i] != B[i]
        find j such that A[j] == B[i]
        swap(A[i], A[j])

Is my approach corrert? Is there another way to solve it?

johnchen902
  • 9,531
  • 1
  • 27
  • 69
Sandeep Kumar
  • 49
  • 8

1 Answers1

4

That depends on whether you're trying to find the minimum number of swaps, or actually trying to sort the array.

If you're trying to sort the array, the minimum number of swaps will not help you sort it faster. Finding the best sorting algorithm will help you sort faster. Generally, that means finding one with an O(n log(n)) complexity (unless the array is small or memory is a major constraint). For help with this problem, Google is your friend.

If you're just trying to find the minimum number of swaps needed, without actually sorting it, you're looking at some modification of the selection sort. The way that one goes is find the lowest value, swap with the first index, find the second-lowest, swap with the second index, etc.

But as I said, finding the minimum amount of swaps does not optimize sorting. The selection sort may have fewer swaps than the quicksort, for example, but it takes longer for the selection sort to determine which indeces to swap. The time complexity of the selection sort is O(n^2).

The difference between O(n^2) and O(n log(n)) is not as trivial as it looks, by the way. If the number is around 1,000,000, it could be the difference between 20,000,000 and 1,000,000,000,000.

SarcasticSully
  • 442
  • 4
  • 14
  • 1
    Determining minimum amount of swap can still be done in O(n log(n)). All you have to do is finding the minimum element in O(log(n)). Segment tree, priority queue, pre-sort the array, etc. – johnchen902 Aug 16 '16 at 17:33
  • @SarcasticSully Thanks for the efforts, But i donot want to actually sort the array . Nor the time complexity of any issue to me. I just wanted to know What is the actual number of swaps (The minimum possible) to make the array sorted. And i want to repeat that i wanted to know if my approach to get the minimum number of swaps correct or is there a case that my approach will not give the optimally minimum number of swaps. – Sandeep Kumar Aug 18 '16 at 03:37
  • Thanks for the reply @johnchen902 . I have no issues with time-Complexity. Even my O(n^2) is totally fine. I just wanted to know the correctness of my approach or any other approach ,if possible. Thanks – Sandeep Kumar Aug 18 '16 at 03:41
  • Although as u pointed out, My algorithm is more like selection Sort, except that my problem can be done in O(n) time, by predetermining the position of A[j] and updating it accordingly. Thanks. – Sandeep Kumar Aug 18 '16 at 03:51
  • 1
    How can you prove that some modification of selection sort employs minimum number of swaps? – voipp Jun 19 '19 at 09:57