Is this algorithm bubble sort or selection sort?

Question

#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = 0;  j < 9; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
    // now the array is sorted!

    return 0;
}

I've just studied bubble sort and tried to implement that in c++ as the code above.

I've taught my friend the algorithm, but he implemented it as the following code, which worked and sorted the array, but I don't know what the name of algorithm he used. Here is a sample of what he used:

#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1;  j < 10; j++) {
            if (arr[i] > arr[j]) {
                std::swap(arr[i], arr[j]);
            }
        }
    }
    // now the array is sorted!
    return 0;
}

Is this selection sort?

Answer 1

Yes, the code written by your friend implements the selection sort. It is not exactly how the selection sort is usually implemented, though.

What is done in your friend's code?

1. At the first iteration where i=0, it finds the smallest element by comparing the element at index 0 with all other element, swapping if necessary so that the minimum element so far will stay at index 0.

   At the end of this iteration, the smallest element is at index 0.

2. At the next iteration where i=1, it finds the next smallest element by comparing the element at index 1 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 0.

   At the end of this iteration, the smallest and second smallest element is at index 0 and 1, respectively.

3. At the next iteration where i=2, it finds the next smallest elements by comparing the element at index 2 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 2.

   At the end of this iteration, the first 3 smallest elements are sorted at index 0, 1 and 2.

4. And so on.

5. Finally, at the beginning of last iteration where i=9, the first 9 smallest elements are sorted at first 9 indices. The 10th smallest elements, which is also the largest element in this 10-element array, must have been at the last index.

   So the sorting is done.

---

Your friend implements the selection sort.

Let us check what is selection sort. According to the Wikipedia article, here is the idea of selection sort.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

We can verify that your friend's code implements exactly that idea above. In fact, if you replace int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; with int arr[5]= {11, 25, 12, 22, 64};, updating the bounds accordingly, your friend's code will produce exactly the same sublists at end of each outer loop as shown in the example in Wikipedia.

Your friends' code is different from how the selection sort is usually implemented. The common implementation uses an index iMin to track the minimal element while your friend uses the element at the expected location to track the minimal element.

Your friend's code runs slower than the usual implementation because it uses much more swaps in average although both implementation uses exactly the same number of comparisons, $n(n-1)/2$. On the other hand, it uses no more swaps than a bubble sort.

Your friend's code is simpler to write and ends up even shorter than the common implementation, supporting the claim "selection sort is noted for its simplicity".

You may want to enjoy visualization of various sorting algorithms at Topal.com.

---

Exercise

1. If arr[j] > arr[j + 1] in your code is changed to arr[j] < arr[j + 1], what is the result? Does it implement bubble sort still?
2. If arr[i] > arr[j] in your friend's code is changed to arr[i] < arr[j], what is the result? Does it implement selection sort still?
3. Show that your friend's code uses no more swaps than a bubble sort. Give an example when your friend's code uses less swap than a bubble sort.

Answer 2

The first snippet is an inefficient version of bubble sort. Inefficient because more than half of the comparisons it performs are useless (after the first pass, the largest element is put in the last position, and the next loop can stop earlier; and so on). Efficient versions stop at the last swap of the previous pass.

The second snippet may be considered a selection sort because it bring the smallest element in the first position repeatedly, but does it in an inefficient way as it can move many elements on every pass (at worse O(N²) moves in total). True selection sort looks for the smallest element without moving any (at worse O(N) moves).