CODEWITHSUNDEEP
algorithmsorting
Rajdeep Biswas
Rajdeep Biswas

Reputation: 307

Identify this sorting algorithm

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.

Upvotes: 0

Views: 93

Answers (1)

Nelfeal
Nelfeal

Reputation: 13269

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.

Upvotes: 4

Related Questions