What type of sort is this?

Question

The C++ book I'm reading described a sort algo, saying it is the Bubblesort yet I cannot find a single variation of bubblesort just like it. I understand the differences are minor, but is it exactly as efficient as a regular bubblesort ?

BubbleSort(int A[], int length)
for (j=0; j < length-1; j++)
  for (i=j+1; i < length; i++)
    if (A[i] < A[j])
      Swap()

Basically, instead of comparing two adjacent values, it compares the first A[0] with every entry, on the next pass it compares A[1] with the remaining entries, then A[2] etc.

Is it really just a regular bubblesort, is the characteristics and performance exactly the same?

Answer 1

This is selection sort. On each pass you find the i'th smallest element and put it in position i. After the first pass, it is not necessary to look at A[0] anymore, and so on. Selection sort is worst-case O(n²) and best-case O(n), just like bubble sort, but it has a smaller constant factor than bubble sort. Insertion sort, an additional refinement, is even better, to the point where it's faster than most O(n log n) algorithms for very small arrays (fewer than ten elements or so) and so serious library sort primitives will cut over to it for small subproblems.

Answer 2

The algorithm looks more like insert sort to me, as they share the same (outer) loop invariant -- after j-th iteration of the outer loop, the j smallest elements are in their correct positions.

On the other hand, the characteristic property of bubble sort is that it always swaps neighboring elements (a property which is not satisfied in your snippet).

The time complexity of this algorithm is O(n^2), just like bubble sort and insert sort (and quick sort in the worst case).

Answer 3

It looks like a Selection Sort to me.

Answer 4

This sort is similar to selection sort, in that each pass through the outer loop identifies the best element and removes it from further consideration. In a traditional selection sort, however, the best element is swapped with the element to be removed and other elements are left alone. In the sort you list (found, IIRC, in "A Basic Approach to Basic" among other places) some other elements will get swapped around as well. I don't think the extra swaps accomplish anything particularly useful, and the sort loses out on just about the only advantage bubble sort has (suitability for implementation on purely-sequential-access media)