Which one is bubble sort?

Question

The first:

for(int i=0;i<n-1;i++)
  for(int j=n-1; j>i;j--)
    if(a[j] < a[j-1])
        swap(a[j], a[j-1]);

or the second:

for(int i=0; i<n-1; i++)
  for(int j=i+1; j<n; j++)
    if(a[j] < a[i])
        swap(a[j],a[i]);

or third version:

int temp, i, j = 0;
    boolean swaped = true;

    while (swaped) {
        swaped = false;
        j++;
        for(i = 0; i < arr.length - j; i++){
            if(arr[i] > arr[i+1]){
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                swaped = true;
            }
        }
    }

Someone say the first and someone say the second. So which one is right? Someone say the second is interchange sort. Many book say bubble sort is the third version, but many people called the first version is bubble sort. Any comment?

Answer 1

The first version is the bubble sort, because it's comparing each pair of adjacent items.

The second version is a selection sort because a[i] ends up being the smallest item in the unsorted right portion of the array after each iteration of the outer loop.

Answer 2

I tested both your code snippets on an actual array using Java in IntelliJ. Both versions generated an array in ascending sorted order.

Here is the array I used:

int[] a = {1, 9, 3, 5, 4, 2, 8, 6, 7};

And here is the output from the two versions:

Version 1

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Version 2

[1, 2, 3, 4, 5, 6, 7, 8, 9]

The first version looks like a standard bubble sort, while the second version appears to be something else.