CODEWITHSUNDEEP
calgorithmsortingbubble-sort
ThanhPT
ThanhPT

Reputation: 67

Which one is bubble sort?

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?

Upvotes: 5

Views: 347

Answers (3)

so-random-dude
so-random-dude

Reputation: 16465

1.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]);

This is Bubble Sort

2.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]);

It is selection sort

Even though at first glance it will give an impression that its a reversed implementation of bubble sort, it is not. It is selection sort as other user pointed out already

3.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;
            }
        }
    }

This is in fact, enhanced bubble sort This will improve the best case scenario

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521093

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.

Upvotes: 1

fgb
fgb

Reputation: 18569

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.

Upvotes: 7

Related Questions