Identify this sorting algorithm

Question

While browsing old code I had written in freshman year of college, I found the following snippet marked as 'bubble sort'. (here n is the size of the array; eg. for an array of 10 elements n = 10).

for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++) {
        if(arr[i] > arr[j]) {
            int temp  = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

Now, i can tell that this certainly isn't bubble sort, but maybe a very poor implementation of it. Fact is it works and I'm curious if this is an algorithm that already exists or if it is something that I came up on my own albeit it being very inefficient.

Your first sort implementation you learn at school. To teach you what is slow.. — Aldert
– Aldert, Commented Dec 8, 2018 at 17:35
@RaymondNijland Bubble sort only uses one index since it compares adjacent pairs. That is not the case here. — Nelfeal
– Nelfeal, Commented Dec 8, 2018 at 17:35
@RaymondNijland I don't see how. The inner loop is from 1 to n-j (which would be n-i here), and the comparison is between [i] and [i-1], not [i] and [j]. If what you mean is that there are two (nested) loops and a swap, then I've got news for you: a whole lot of sorting algorithms match that description. — Nelfeal
– Nelfeal, Commented Dec 8, 2018 at 17:48
well geuss iám wrong in this case and seriously need some caffaine to wake up @Nelfeal this indeed looks more like selection sort algorithm indeed — Raymond Nijland
– Raymond Nijland, Commented Dec 8, 2018 at 18:21

Nelfeal · Accepted Answer · 2018-12-08 17:34:00Z

4

This is a poor implementation of selection sort. Take a reference implementation (from Wikipedia):

for (j = 0; j < n-1; j++) {
    int iMin = j;
    for (i = j+1; i < n; i++) {
        if (a[i] < a[iMin]) {
            iMin = i;
        }
    }

    if (iMin != j) {
        swap(a[j], a[iMin]);
    }
}

Instead of finding the minimum in the unsorted part and placing it at the end of the sorted part with a swap, your snipper just swaps everytime it finds a "potential minimum", that is a value lesser than the one past the end of the sorted part. That's inefficient because swaps simply cost more than index assignment.

answered Dec 8, 2018 at 17:34

Nelfeal

13.3k1 gold badge23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Identify this sorting algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related