Bubble Sort (Bubble Sort)

What is Bubble Sort?

Bubble arrangement is a simple sort algorithm. This sorting algorithm is carried out based on comparing pairs of adjacent and swap elements if they are not in order.

This algorithm is not suitable for use with large data sets where the worst case complexity and the average case are Ο (n2) where n is the number of elements.

Foam sorting algorithm is the slowest algorithm among basic sorting algorithms. This algorithm is even slower than the direct displacement algorithm even though the number of comparisons is equal, but due to the displacement of two adjacent elements, the number of swapped places is more.

How to arrange foam to work?

Suppose we have an unordered array of elements like below. Now we use the bubble sort algorithm to sort this array.

Bubble Sort (Bubble Sort) Picture 1

The bubble sort algorithm starts with the first two elements, comparing them to check which element is larger.

Bubble Sort (Bubble Sort) Picture 2

In this case, 33 is greater than 14, so these two elements were in order. Next we compare 33 and 27.

Bubble Sort (Bubble Sort) Picture 3

We see that 33 is greater than 27, so these two values ​​need to be swapped in order.

Bubble Sort (Bubble Sort) Picture 4

New arrays will be as follows:

Bubble Sort (Bubble Sort) Picture 5

Next we compare 33 and 35. These two values ​​are in order.

Bubble Sort (Bubble Sort) Picture 6

Then we compare the next two values ​​of 35 and 10.

Bubble Sort (Bubble Sort) Picture 7

Since 10 is less than 35, these two values ​​are not in order.

Bubble Sort (Bubble Sort) Picture 8

Swap the order of two values. We have reached the end of the array. So after a loop, the array will look like this:

Bubble Sort (Bubble Sort) Picture 9

For simplicity, I will display the image of the array after each loop. After the second iteration, the array will look like:

Bubble Sort (Bubble Sort) Picture 10

After each loop, at least one value will move to the last position. After the third loop, the array will look like:

Bubble Sort (Bubble Sort) Picture 11

And when there is no need to swap any element order, the bubble sort algorithm finds that the array has been sorted.

Bubble Sort (Bubble Sort) Picture 12

Next, we learn some more practical aspects of sorting algorithms.

Solution for bubble sort (Bubble Sort)

Suppose the list is an array with n elements. Then assume the swap function to swap the values ​​of the elements in the array (this is assuming, of course, you can write your own code for this swap function).

 B ắ t đầ u gi ả i thu ậ t BubbleSort ( list ) for t ấ t c ả ph ầ n t ử trong list if list [ i ] > list [ i + 1 ] swap ( list [ i ], list [ i + 1 ]) k ế t th ú c if k ế t th ú c for return list K ế t th ú c BubbleSort 

Sample algorithm for bubble sort (Bubble Sort)

We see that the bubble sort algorithm compares each pair of elements in the array unless the entire array is completely sorted in ascending order. This can increase complexity, ie increase unnecessary comparison and swap operations if this array does not need any swap when all the elements are sorted in ascending order. already.

To avoid this happening, we can use a swapped variable for example to help us know whether to perform a swap operation. If not necessary, exit the loop.

You follow the following sample illustration algorithm:

 B ắ t đầ u h à m bubbleSort ( list : m ả ng c á c ph ầ n t ử ) loop = list . count ; for i = 0 t ớ i loop - 1 th ự c hi ệ n : swapped = false for j = 0 t ớ i loop - 1 th ự c hi ệ n : /* so sánh các phần tử cạnh nhau */ if list [ j ] > list [ j + 1 ] then /* tráo đổi chúng */ swap ( list [ j ], list [ j + 1 ] ) swapped = true k ế t th ú c if k ế t th ú c for /*Nếu không cần tráo đổi phần tử nào nữa thì tức là mảng đã được sắp xếp. Thoát khỏi vòng lặp.*/ if ( not swapped ) then break k ế t th ú c if k ế t th ú c for K ế t th ú c h à m return list 

Deploy the algorithm of arranging foam in C

One more thing that we have not mentioned in the two parts of algorithm design is that after each loop, the largest values ​​will appear at the end of the array (as shown in the illustration: after the 1st loop is 35 ; after loop 2 is 33 and 35; .). Therefore, the next loop will not need to include these sorted elements. To do this, in the code we limit the loop iteration side to avoid having to repeat these sorted values.

According to Tutorialspoint

Previous lesson: Algorithms arranged in data structures & algorithms

Next lesson: Insertion sort algorithm (Insertion Sort)