BubbleSort bubble sorting algorithm

Tram Ho

This is the first article in the series of common programming algorithms in programming I will share with everyone. In this article, we will learn about the bubble sort algorithm. The sections in this article include:

  1. Thought of the algorithm
  2. Code Demo
  3. Algorithm evaluation.

Start.

1. Algorithm thought: This algorithm has the following arrangement:

  • Perform element swapping from beginning to end of the array. Swap 2 elements next to each other according to their arrangement convention (depending on the arrangement from large to small or small to large, we decide whether or not to exchange two elements), this swap step Perform sequential and sequentially from the beginning to the end of the array. After performing a complete swap, there will be 1 element in the right position is the last standing element of the array.
    For example, we have an array of numbers 4, 5, 2, 3, 7, 6, 1, and need to sort from big to small. The steps to change seats are as follows:
    B1 : We determine 2 elements to be swapped 1 and 5. Because 4 <5, we keep the position of two numbers => [ 4 , 5 , 2, 3, 7, 6, 1].
    B2 : We determine the 2 elements to be swapped next to 5 and 2. Because 5> 2 we change the position of two numbers => [4, 2 , 5 , 3, 7, 6, 1].
    B3 : We determine the 2 elements to be swapped next to 5 and 3. Because 5> 3 we change the position of two numbers => [4, 2, 3 , 5 , 7, 6, 1].
    B4 : We determine 2 elements to be swapped next to 5 and 7. Because 5 <7, we keep the position of two numbers => [4, 2,3, 5 , 7 , 6, 1].
    B5 : We determine the next 2 elements to be swapped as 7 and 6. Because 7> 6, we change the position of two numbers => [4, 2,3, 5, 6 , 7 , 1].
    B6 : We determine the next 2 elements to be swapped as 7 and 1. Because 7> 1, we change the position of two numbers => [4, 2,3, 5, 6, 1 , 7 ].
  • Repeat the above process, but by reducing the size of the array, each time 1.
    It’s a bit difficult to understand. So let’s go into the code.

2. Code Demo

3. Algorithm evaluation:
Algorithm complexity

  • Good case: O (n)
  • Medium: O (n ^ 2)
  • Bad case: O (n ^ 2)
Share the news now

Source : Viblo