selection sort

[cppnoob25]

So for the sake of practice I decided to code selection sort from memory and I came up with this. Am I doing this right? It works but I'm not sure if it works correctly. I then copied someone else which I named selection2. His is a little different but can they both be considered selection sort?

I know there are far better sorting algorithms and this was just for practice.

void selection(int arr[], int size)
{
    for(int i =0; i< size; i++)
    {
        int minimum = arr[i];
        for(int j = i+1; j < size; j++)
        {
            if(minimum > arr[j])
            {
                minimum = arr[j];
                swap(arr[i], arr[j]);
            }
        }
    }
}

void selection2(int arr[], int size)
{
    int min;
    for(int i =0; i< size; i++)
    {
        min = i;
        for(int j = i; j < size; j++)
        {
            if(arr[j] < arr[min])
            {
                min = j;
            }
        }
            swap(arr[i], arr[min]);
    }
}

[fg109]

The second one is more efficient because it only swaps after checking the rest of the array, while yours does the swap immediately. Yours is more like a bubble sort. It would also lead to a segfault when i == size - 1.

[Smac89]

The first one is more like bubblesort than selection sort, the second one looks like selectionsort.

Bubblesort and Selection sort are less interesting than Insertion sort because of the behaviour of insertion sort when the list of items to be sorted is nearly sorted.

@fg109, that last one is the most inefficient sorting algorithm just because of the same reason you said it is efficient. Why? Because we don't need to wait until we have looked at every element to determine that any intermediate element is smaller than the current one we are at. Doing that extra swapping in between means less time spent moving elements into place as the function proceeds

[fg109]

@Smac89

I forgot to consider the actual time spent on the entire sorting process. I meant efficiency as in the time taken in getting the smallest element in the array from position i to the end, and moving it to position i, which I realize is tunnel vision.

Both the bubble sort and selection sort shown here run through the outer loop the same number of times. Both of them go and check through every unsorted element of the array in the inner loops.

So for these two functions, the number of comparisons that are made are the same. If we were to count the number of swaps, well the selection sort will swap at most once at the end of every iteration of the outer loop. The bubble sort is guaranteed to swap at least as much as the selection sort (maybe not on the same iteration of the loop, but definitely over all iterations of the loop combined).

In fact, I don't think there's much of a difference in efficiency between the two in overall time taken.

http://coliru.stacked-crooked.com/a/c6b924d6996d6a68

[Smac89]

Note, I'm not saying that one is more efficient than the other, I'm just saying that selection sort is the most inefficient. To see why, type both into google and for each one click the Wikipedia link then look in the performance table at the best case running time and you will see why.

Also I said the first one is more like bubblesort than selection sort and to see why, well you are already on the Wikipedia page so you might as well compare the differences

EDIT: for timing purposes, there is a strong push to not use wall clock. See this:
http://www.cplusplus.com/forum/general/161373/#msg821490

[cppnoob25]

Thanks for the responses I agree now that I look at it.