Introduction
Imagine you are given a bunch of food items to eat. It includes your favourite as well as your non-favourite food items.
Now you have to decide according to your preference which item you would like to eat first. And then, you will make necessary shuffling among the food items and sort them according to your eating preference.
Image source:giphy
Like many food items, an array is a programming tool that stores similar data together under a single name.
Consider elements in an unsorted array:
4 | 10 | 2 | 56 | 19 |
Like we sorted the food items according to our eating preference, we also sorted the elements in an array. And in both cases, we exchange the places of elements to assign them their correct position.
We swapped the elements of an array to sort them in ascending order.
2 | 4 | 10 | 19 | 56 |
Now, after Sorting, since we know the address of the first element, we can access other elements one after the other.
Thus, we can define swapping in array as:
The number of exchanges that occur while arranging or sorting the elements in the desired order.
So let us discuss all these methods one by one to know about various swaps used while sorting.
Minimum swaps to sort an array
Consider an unsorted array consisting of integers, where n is the size of the array. We need to find the minimum number of swaps to sort an array in ascending order.
Let the array be:
1 | 4 | 11 | 2 | 5 |
What is the basic/brute approach one could go on with to minimise the number of swaps and sort the array side-by-side?
Well, let's have 11 at the second index, as shown in the above example. Now we have 2 options. Swap 11 with 2 or with 5. Which one would you choose?
The obvious answer would be swapping with 5 because swapping with 2 would mean another swap with 5, which would result in 2 swaps for the same element, but to find the minimum number of swaps to sort the array, it only makes sense to swap with the number such that both the elements are swapped in the correct sorted order.
NOTE: The above explanation is just to understand what choices are available and which one to choose and why?
So at each index, we should find the one that places a particular element in just a single swap at its correct place.
Do you recall, Which sorting algorithm we are talking about?
If your answer is Selection Sort. You got it correct.
Selection sort makes at most N-1 swaps. Nevertheless, we found an algorithm that fulfils the criteria and takes O(n2) time.
Remember, we always want to get better and better. So let's try to rethink and improve our solution.
If you are stuck on how one improves their solution, then the tip of advice is to check redundancies, repetitive work, which could be prevented. Try to think whether any other technique does the same job in less time.
Why does the above idea work? (Intuition)
Consider an array to be written as a1, a2, …aj-1, aj , aj+1, .. aN .
and assume that {a1 , aj-2} and {aj+2 , aN} are already at their correct positions.
The algorithm gave us the correct answers for sorting both parts in a minimum number of steps. Say it took X steps.
The only segment to be sorted in minimum number moves is the segment containing aj-1, aj , aj+1.
Now consider the following cases:
- aj-1 <= aj <= aj+1 no swaps are needed.
- aj-1 > aj >= aj+1 , only 1 swap is needed.
- aj-1 >= aj > aj+1 , only 1 swap is needed.
-
aj-1 < aj > aj+1 , we can 2 sub-cases here,
- aj-1 <= aj+1 , only 1 swap is needed.
-
aj-1 > aj+1 , here 2 swaps are needed.
We have exhausted all the possible cases. See, every time we search for the element to be placed at a particular position in sorted order, we search for the minimum on the right-hand side and swap it with the current element, which gives us the optimal answer.
Choosing another swapping mechanism would be contradictory if we assumed that the above algorithm gave us the incorrect result.
Read more, Bubble Sort