2

I have been given an array and I'm asked to find out the number of Swaps required to sort the array using Bubble Sort

Now we know that, we can find the comparisons by n(n-1)/2 but what I need is the number of actual swaps

My first instinct was to use bubble sort and with each swap(), I incremented a Swap variable. But the time complexity of this is a very slow process and I'd like your help to find an optimized way to solve my dilemma

P.S.: I also need to compare whether it is faster to sort it in ascending or descending.... Sorting it twice doubles the time.

Edit:

Sorry if I wan't clear enough. I want to find the swaps without using Bubble Sort at all.

dingalapadum
  • 2,077
  • 2
  • 21
  • 31
Rajkumar Pagey
  • 61
  • 2
  • 10
  • 3
    Go with your first instinct. Having an additional constant-time operation (incrementing a count), won't change the asymptotic runtime of the whole sorting method... Why would that be a 'slow process'? – dingalapadum Aug 09 '15 at 11:25
  • 1
    "_But the time complexity of this is a very slow process_" Wrong. Adding one more operation does nothing to the time complexity in this case. Besides, it's bubble sort. If time complexity was an issue you would NEVER use bubble sort. – takendarkk Aug 09 '15 at 11:29
  • Sorry for the miscommunication, I don't want to use Bubble Sort at all. I want to know if there is any algorithm to find swaps without using Bubble Sort – Rajkumar Pagey Aug 09 '15 at 12:00
  • 1
    Does this answer your question? [Sorting a sequence by swapping adjacent elements using minimum swaps](https://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps) – Endle_Zhenbo Jul 12 '21 at 09:18

1 Answers1

4

Regard the applied swap() to a[i] and a[i+1] as a bubble-up of a[i]. Now, asking how many swaps are going to happen is the same as asking how many bubble-up operations are going to happen. Well, and how many do we have of those?

Each a[i] will bubble-up for each position j > i, where a[j]<a[i]. In words a[i] will bubble-up for each position to the right, where the elements value at that position is smaller than a[i] itself. A pair of elements satisfying this condition is what is known as an inversion of a[].

So reformulating your question we could ask: What is the total number of inversions in a[]? (a.k.a. What is the inversion number of a[]?)

This is a well known problem and besides some obvious approaches running in O(n^2) a typical approach to this problem is to tweak merge-sort a bit in order to find this number. And since merge-sort runs in O(n*log(n)) you get the same running time to find the inversion number of a[].

Now that you know that you can tweak merge-sort, I suggest you give it a try on your own on how to do it exactly.

Hint: The main question you have to answer is: When positioning a single element during a merge-step of two arrays, how many inversion did I fix? Then simply add up all of those.

In case you still are stuck after giving it some thought, you can have a look at some full blown solutions here:

Community
  • 1
  • 1
dingalapadum
  • 2,077
  • 2
  • 21
  • 31