0
$\begingroup$

I was trying to come up with a formula for the number of swaps used in selection sort. So we know that selection sort gives the minimum number of swaps to sort an array.

The formula I came up with is given an unsorted array and it's descending or ascending order. We find the number of elements dissimilar to the sorted array. When we subtract 1 from this number we can get the number of swaps.

For example, Let the array be

[3, 4,2 ,9,1]

Using selection sort for descending order:

[9,4,2,3,1] ---[9,4,3,2,1] which gives a total of 2 swaps

My logic:

Descending array is [9,4,3,2,1]. So three elements are in incorrect position which are 9, 3 and 2. So, 3-1 = 2 swaps.

Let us consider ascending order:

Section sort:

[1,4,2,9,3]--[1,2,4,9,3]--[1,2,3,9,4]--[1,2,3,4,9] which gives a total of 4 swaps.

My logic:

Ascending array is [1,2,3,4,9]. So all five elements are in incorrect position from the sorted array which gives a total swap count of 5-1 = 4.

But my logic seems to be incorrect when tested on hacker rank. Could you give me an example where this logic fails. Thanks :)

$\endgroup$
  • 2
    $\begingroup$ "So we know that selection sort gives the minimum number of swaps to sort an array." -- citation needed. $\endgroup$ – Raphael Sep 21 '17 at 5:59
  • 1
    $\begingroup$ The problem with your logic is there is no logic. You are saying something about a five-element array. In algorithm analysis, you need to say something about all arrays. $\endgroup$ – Raphael Sep 21 '17 at 6:00
  • $\begingroup$ Have you tried generating all permutations of short lists, selection-sorting them, and counting the number of swaps? $\endgroup$ – adrianN Sep 21 '17 at 10:24
1
$\begingroup$

Considering following array [5,4,3,2,1]

Now for ascending order, four elements are in incorrect position i.e. 5,4,2 and 1

So according to your logic, No of swaps = No. of elements at incorrect position - 1 therefore No. of swaps = 4-1 i.e. 3

Now, according to Selection sort,

[5,4,3,2,1] Original Array

1st Pass: [1,4,3,2,5] i.e. 1 swap

2nd Pass: [1,2,3,4,5] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Similarly for Descending order,

Now, according to Selection sort,

[1,2,3,4,5] Original Array

1st Pass: [5,2,3,4,1] i.e. 1 swap

2nd Pass: [5,4,3,2,1] i.e. 2 swaps

We are done, with Only 2 swaps not 3 swaps.

Hope this helps !

$\endgroup$
  • $\begingroup$ This shows that the formula suggested by the OP is wrong. What is the correct formula? $\endgroup$ – Yuval Filmus Sep 22 '17 at 9:30
  • $\begingroup$ @YuvalFilmus I actually didn't think about it but i searched for it because of your question. Thanks. I think this link GeeksForGeeks explains it very well $\endgroup$ – rdj7 Sep 22 '17 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.