Is the number of swap function calls and the number of swaps done while selection sort the same thing?

Question

I know that for n elements, in selection sort:

Best cases: 1 swap done. Worst cases: n-1 swaps done. Average cases: (n-1)/2 swaps done.

So, if i were to say that the number of times the swap function has been called is same as the number of swaps done in 3 different cases, would I be correct?

Answer 1

Well, for a start, I'm not sure why the minimum swap count would be one. For an array that's already sorted, it should be zero.

Any half-decent algorithm would detect that the fact that the current smallest item in the unsorted section was already at the right place, forget the swap and just move the boundary between the sorted and unsorted section.

In other words, something like (pseudo-code):

def selSort(items):
    # This position is the ever-moving border between
    # 'sorted on left' and 'unsorted from here to end'.

    for position in 0 thru items.length - 2 inclusive:
        # Scan all unsorted, finding the lowest (starting
        # default is the first unsorted).

        lowestUnsorted = position
        for checkPos = position + 1 thru items.length inclusive:
            # If lower than current lowest, replace.

            if items[checkPos] < items[lowestUnsoreted]:
                lowestUnsorted = checkPos

        # Swap if need be.

        if lowestUnsorted != position:
            temp = items[position]
            items[position] = items[lowestUnsorted]
            items[lowestUnsorted] = temp

---

But, in terms of your actual question, I'd say it a good bet that they're the same thing. Unless your swap function has conditional code to possibly not swap under certain circumstances^(a), or code that swaps more than one thing each time, each call to the swap function is the same as a swap.

---

^(a) You could make the case that the swap function may be called regardless of whether the item is already in the correct position and it simply detects that and doesn't swap, something like:

void doSwap (Item *item1, Item * item2) {
    if (item1 != item2):
        Item tempItem = *item1;
        *item1 = *item2;
        *item2 = tempItem;
}

In that case, the calls to the swap function may differ from the actual swaps. But, to be honest, that check is probably better done in the layer above (as per the pseudo-code) since function calls, while relatively cheap, are rarely zero-cost.