CODEWITHSUNDEEP
c++algorithmbubble-sort
DEF2
DEF2

Reputation: 11

Understanding Bubble Sort (Algorithm)

I'm trying to understand the simplest of all swapping algorithms, the bubblesort. Yet I seem to be confused on the steps of actually swapping values, for instance consider the code :

void bubbleSort(int arr[], int n) {

      bool swapped = true;

      int j = 0;

      int tmp;

      while (swapped) {

            swapped = false;

            j++;

            for (int i = 0; i < n - j; i++) {

                  if (arr[i] > arr[i + 1]) {

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        swapped = true;

                  }

            }

      }

}

Let's say I have a list of numbers like this:

7 1 3 4 6 3 5

And I want to swap the first two values, 7 and 1:

By my logic, this is how I'm understanding this code:

set a temp variable equal to 7, so

temp = 7;

set 7 equal to the next value, so

7 = 1; ? The list at the moment is:

1 1 3 4 6 3 5
Where temp = 7

Now set 1 equal to temp, which is 7? 1 = temp;

So the list is now:
1 7 3 4 6 3 5

Is my understanding correct on this?

Upvotes: 1

Views: 166

Answers (2)

graham.reeds
graham.reeds

Reputation: 16476

First, you do seem to be on the right track.

Some tips to help you progress further on your journey.

Learn the standard template library. There is a function called swap which does exactly what it says on the tin.

Secondly use containers. They are less error prone than C-style arrays.

Finally here is bubble sort explained via the medium of folk dancing.

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 311058

In this code snippet

if (arr[i] > arr[i + 1]) {

      tmp = arr[i];

      arr[i] = arr[i + 1];

      arr[i + 1] = tmp;

      swapped = true;
}

you need to swap two objects arr[i] and arr[i + 1]

If you write directly

      arr[i] = arr[i + 1];

then the two objects will have the same value that is the previous value of arr[i] will be lost.

So at first you need to preserve this value somewhere. To do so there is declared an auxiliary intermediate variable tmp

So at first the value of arr[i] is preserved in variable tmp Let's assume that arr[i] has value 7 and arr[i + 1] has value 1.

      tmp = arr[i];

Now tmp and arr[i] has the same value 7.

Then arr[i] is overwritten by the value of arr[i + 1]

      arr[i] = arr[i + 1];

Now these two variables have the same value 1 that is the value of arr[i + 1]

We have tmp is equal to 7, arr[i] and arr[i + 1] are equal to 1

However the previous value of arr[i] was preserved in variable tmp So now this value is assigned to arr[i + 1]

      arr[i + 1] = tmp;

And we are getting arr[i + 1] is eqal to 7 and arr[i] is equal tp 1

Thus the values were swapped.

Upvotes: 0

Related Questions