1
$\begingroup$
#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?

$\endgroup$
  • $\begingroup$ (How did you try to determine if your friend's code implements selection sort? Can you give a reference and/or quote?) I've taught my friend the algorithm which algorithm: bubble sort or the one implemented by the first code snippet? $\endgroup$ – greybeard Mar 10 '19 at 15:26
  • $\begingroup$ This is a nice question. Upvoted. $\endgroup$ – John L. Mar 11 '19 at 2:37
  • $\begingroup$ Bubble sort runs in $O(n)$ in best case because it knows the array is already sorted if there is no swap in one pass. Your implementation does not implement this feature. $\endgroup$ – xskxzr Mar 11 '19 at 5:55
  • $\begingroup$ @Mohamed, can you edit the question and title to clarify "Is this selection sort"? People who read the title and the first snippet, your code will think "Is this algorithm bubble sort or selection sort?" is about your code. $\endgroup$ – John L. Mar 11 '19 at 7:05
3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ You misunderstand. Selection sort performs at most N swaps. Bubblesort up to N². You still haven't looked at the code. $\endgroup$ – Yves Daoust Mar 11 '19 at 0:16
  • $\begingroup$ @YvesDaoust "the given algorithm moves the largest in the last place, not the smallest in the first place" is wrong. Did you look at the code closely? "Selection sort performs at most N swaps", which is an implementation detail instead of the idea of selection sort. By the way, I did take a close look at the code as well as running it before I wrote the first version of my answer. $\endgroup$ – John L. Mar 11 '19 at 3:51
  • $\begingroup$ Trading O(N²) for O(N) has never been an implementation detail. But as raised by @greybeard, I made a confusion, sorry. $\endgroup$ – Yves Daoust Mar 11 '19 at 8:15
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Efficient versions stop at the last swap of the previous pass With that improvement, cocktail shaker sort (see the MATLAB/OCTAVE code) looks sensible (just remember there are sub-quadratic algorithms comparably difficult to test & implement). $\endgroup$ – greybeard Mar 10 '19 at 21:14
  • 1
    $\begingroup$ @Apass.Jack: I've been under the impression This is… referred to the 1st snippet, while Mohamed Magdy's explicit question was about the 2nd. $\endgroup$ – greybeard Mar 11 '19 at 6:39
  • $\begingroup$ @greybeard: you are right, by some magic I didn't see the second ! The other piece of code is closer to selection sort, but is as well a inefficient version, performing far too many swaps. $\endgroup$ – Yves Daoust Mar 11 '19 at 8:15

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.