CODEWITHSUNDEEP
algorithmsortingbubble-sort
Onki
Onki

Reputation: 2095

Why bubble sort is called bubble sort?

I am learning bubble sort. And I tend to forget about the type of sort everytime. So I am trying to find the logical meaning of each sort so that it helps in recalling the logic of sort :

I could not understand exact meaning that why bubble sort is named bubble sort?

Upvotes: 12

Views: 15405

Answers (5)

Baiyan Huang
Baiyan Huang

Reputation: 6781

Because for each iteration, one element bubbles up to the last of unsorted subsequence by compare & swap

auto bubble_sort(vector<int>& vs)
{
  int n = vs.size();
  bool swapped = false;
  for(int i = 0; i < n-1; ++i)     // total # of iterations
  {
    for(int j = 0; j < n-i-1; ++j) // each iterations bubbles up 1 element
    {
      if(vs[j] > vs[j+1])
      {
        swap(vs[j], vs[j+1]);
        swapped = true;
      }
    }
    if(!swapped) break;
  }
  return vs;
}

Upvotes: 1

mpekim
mpekim

Reputation: 29

As the other answers have already stated, "Bubble Sort" is named the way that it is because elements will slowly move to the desired end of the list, similar to how bubbles will move towards a surface.

Upvotes: 2

Barranka
Barranka

Reputation: 21057

Quoting from Wikipedia:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements "bubble" to the top of the list.

Upvotes: 4

Jean Logeart
Jean Logeart

Reputation: 53839

Why is it called bubble sort?

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface.

Upvotes: 18

Ivan Mushketyk
Ivan Mushketyk

Reputation: 8305

It's called bubble sort because in one iteration of the algorithm smallest/largest element will result at its final place at end/beginning of an array.

So in some sense movement of an element in an array during one iteration of bubble sort algorithm is similar to the movement of an air bubble that raises up in the water

Upvotes: 4

Related Questions