Bubble sort

Introduction

It's not the first time to implement it, but I thought that I might have deepened my understanding a little compared to when I was a beginner, so I thought I'd write an article. I think this bubble sort, the movement is amazingly beautiful. The principle of beautiful things is not intuitive. After all, I think that the opportunity to sort by familiarity is Trump's hand, but I have never used this bubble sort in the elementary alignment. (Do you have any? Lol)

code

bubble_sort.py


def bubble_sort(A):
    flag = 1
    i = 0
    while flag:
        flag = 0
        for j in range(len(A)-1,i,-1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                flag = 1
        i += 1
    return A

how to use

The argument is an arbitrary array and returns the sorted array.

Description

Loop variable i -The beginning of the sorted array ・ It increases by 1 from the beginning -The end condition is when sorting is completed = when there is no element exchange (expressed by flag)

Loop variable j -Used for exchanging adjacent elements in the end sort part ・ Decrease by 1 from the end to i + 1

flag ・ Used as a continuation condition for while ・ If there is an element exchange, it becomes 1 and the next loop continues.

in conclusion

I thought that i should simply use a for statement from the beginning to the end! However, in bubble sort, when a loop starts, it doesn't stop until all the loops are checked, so useless comparisons are made many times. That's right. I was happy when I understood that I would end it if there was no exchange using a variable called flag. If you like it, please follow me and it will be motivating. Thank you. !!!!!

References

-[Algorithm and data structure for programming contest capture] (https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957)

Recommended Posts

Bubble sort
Bubble sort
Bubble sort without using sort
sort
Bubble sort with fluffy animation
Insertion sort
Selection Sort
[Python] Sort
Python # sort
Implemented bubble sort in Java (BubbleSort)
Implemented Stooge sort in Python3 (Bubble sort & Quicksort)
AOJ Sort I-
Merge Sort Explained
Insertion sort implementation
Hands-on sleep sort
Sort by pandas
Visualize how it is sorted by bubble sort
visualize insertion sort
Python beginners challenge Cpaw CTF Q14 with bubble sort
Bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, count sort (Python)