Detailed graphic explanation of Python bubble sort algorithm

This article brings you relevant knowledge about python, which mainly introduces related issues about bubble sorting, including algorithm description, analysis, code implementation, etc. The following is Let's take a look, hope it helps everyone.

Recommended learning: python video tutorial

1. Algorithm description

##Bubble Sort (Bubble Sort) is a simple sorting algorithm. It repeatedly iterates through the array to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The work of traversing the array is repeated until no more exchanges are needed, which means that the array has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the array through swapping.

2. Algorithm analysis

1. Compare adjacent elements. If the first is greater than the second (in ascending order), swap them both.

#2. Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step is completed, the final element will be the largest number.

3. Repeat the above steps for all elements except the last one.

4. Continue repeating the above steps for fewer and fewer elements each time until there are no pairs of numbers left. Need to compare.
Then we need to perform n-1 bubbling processes, and the corresponding number of comparisons for each time is as shown in the figure below:

3. GIF display

Now that we understand the running process, let’s take a look at the GIF implementation:

4. Code implementation

We sort the following unordered list

Implementation code:

import timepop_list = [19, 14, 10, 4, 15, 26, 20, 96]print("没排序前的列表为：", pop_list)# 记录开始时间start = time.time()# 外层循环控制轮数for i in range(len(pop_list) - 1):
    # 内层循环控制比较次数
    for j in range(len(pop_list) - i - 1):
        # 如果前一个数字比后一个数字大，就交换位置
        if pop_list[j] > pop_list[j + 1]:
            # python特有交换位置方式
            pop_list[j], pop_list[j + 1] = pop_list[j + 1], pop_list[j]print("排序好的列表为：", pop_list)# 记录结束时间end = time.time()print("算法总耗时：", end - start)

Running result:

5. Algorithm upgrade

A variable count is defined in the loop. If the first The count has not changed after the loop, which means that the input is an ordered sequence. At this time, we directly return to exit the loop. The time complexity at this time is

O(n)

Implementation code:

import timedef bubble_sort(pop_list):
    for j in range(len(pop_list) - 1, 0, -1):
        count = 0
        for i in range(0, j):
            if pop_list[i] > pop_list[i + 1]:
                pop_list[i], pop_list[i + 1] = pop_list[i + 1], pop_list[i]
                count += 1
        if count == 0:
            returnpop_list = [19, 14, 10, 4, 15, 26, 20, 96]print("没排序前的列表为：", pop_list)# 记录开始时间start = time.time()bubble_sort(pop_list)print("排序好的列表为：", pop_list)# 记录结束时间end = time.time()print("算法总耗时：", end - start)

Running results:

6. Time complexity analysis

• Optimum time complexity: O(n) (meaning that after traversing once, it is found that there is nothing that can be exchanged Elements, sorting ends.)
• Worst time complexity: O(n^2)
• Stability : Stable
  
  
• # Sorting analysis: There are 8 numbers in the array to be sorted. 7 comparisons were made in the first round of sorting, and 7 comparisons were made in the second round of sorting. 6 comparisons were made, and so on, and 1 comparison was made in the last round.
  
  
• When the total number of array elements is N, the total number of comparisons required is: (N-1) (N-2) (N-3 ) ...1=N*(N-1)/2
  
  
• The algorithm does approximately N^2/2 comparisons. Because data is exchanged only when the preceding element is greater than the following element, the number of swaps is less than the number of comparisons. If the data is random and about half of the data needs to be exchanged, the number of exchanges is N^2/4 (but in the worst case, when the initial data is in reverse order, every comparison requires exchange) .
  
  
• The number of exchange and comparison operations is proportional to N^2. Since in the big O notation, constants are ignored, the time of bubble sorting is complicated. The degree is O(N^2).

Recommended learning: python video tutorial

The above is the detailed content of Detailed graphic explanation of Python bubble sort algorithm. For more information, please follow other related articles on the PHP Chinese website!