Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Hence, Quicksort can give the minimum number of swaps required to sort an array in ascending order with the permission of only swapping two elements at a time.
The minimum number of swaps required to sort an array in ascending order using quick sort is O(n log n) where n is the number of elements in the array.
- Select an element as a pivot (preferably the rightmost or last index of the array).
- Partition the array into two subarrays such that all values lesser than the pivot are positioned at the left of the pivot and all values greater than the pivot are positioned at the right of the pivot.
- We then choose another pivot each in the subarrays and perform same action as step 2. This will be done until a single item array is reached.