[PYTHON] Bubble sort without using sort

Good evening. If you are a Python user, you can use sort, I wanted to taste the way of thinking I tried to summarize ٩ (ˊᗜˋ *) و

For the time being, let's arrange the following arrays in ascending order.

x = [6,4,3,7,1,9,8]

Even if you say it suddenly, the hurdle is high, so First, let's move the smallest 1 to the far left. For example, an action that compares two values and moves the smaller one to the left. How about starting from the right end? Consider x [5], x [6] as an example.

test.py

        # x[5]Is x[6]If it is larger,
        if x[6] < x[5]:
        # x[5] , x[6]Swap the values of
            x[6],x[5] = x[5],x[6] 

The image looks like this. x [5], x [6] are highlighted in blue. Next, let's compare with x [4] VS x [5]. x [4] <x [5] holds. So there is no need to change it.

If you compare them in order like this, The whole picture is as follows. Good, I was able to move 1 to the left end! (^^)! The final goal is to sort in ascending order, so other sorts are needed.

Anyway, 1 is moved to the left end, so 1 is fixed! No matter who says what, it doesn't change (laughs)! For the time being, I changed the fixed 1 to green. Let's write the flow up to this point with a for statement.

test.py

#1.start is x[6],That is, n-It is 1.
#2.end is x[1] vs x[0]So here, if you put 0
#Since the substance is an assignment up to 1, x[1] vs x[0]Will be realized.
#3.The numbers are-It will decrease by 1
#If you arrange the above, range(len(x)-1,0,-1)Will be!
    for j in range(len(x)-1,0,-1):
        #Example) x[6] < x[5]If so, replace it! 
        if x[j] < x[j-1]:
            x[j],x[j-1] = x[j-1],x[j] 

I don't think it's a problem. Please tell me if something is difficult to understand. m (_ _) m Then next. If you find that 1 is the smallest, as shown in the figure below Let's put the next smallest value next to 1. You no longer need to move the data to x [0]. It can be from x [6] to x [1]. Let's make a little code.

test.py

#↓ I changed this from 0 to 1.
    for j in range(len(x)-1,1,-1):
        #Example) x[6] < x[5]If so, replace it! 
        if x[j] < x[j-1]:
            x[j],x[j-1] = x[j-1],x[j] 

From x [6] to x [1] as above We will repeat the comparison work. The result is as follows. Next is x [6] to x [2].

test.py

#↓ I changed this from 1 to 2.
    for j in range(len(x)-1,2,-1):
        #Example) x[6] < x[5]If so, replace it! 
        if x[j] < x[j-1]:
            x[j],x[j-1] = x[j-1],x[j] 

It ’s good, right? (Lol) That's right, when nesting for statements You can express what you want to do.

test.py

for i in range (len(x)-1):
    for j in range(len(x)-1,i,-1):
        if x[j] < x[j-1]:
            x[j],x[j-1] = x[j-1],x[j] 

The whole picture is as follows.

bubble_test.py

x = [6,4,3,7,1,9,8]

for i in range (len(x)-1):
    for j in range(len(x)-1,i,-1):
        if x[j] < x[j-1]:
            x[j],x[j-1] = x[j-1],x[j] 

print(x)

Execution result.py

[1, 3, 4, 6, 7, 8, 9]

Sorting is fun to understand, There are many figures in the explanation, so I'm tired of writing articles (laughs) In fact, if the sequence doesn't need to be changed anymore, There may be a way of thinking about rounding up the sort, but ... Next is quick sort. ..