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. 図1.PNG Next, let's compare with x [4] VS x [5]. 図2.PNG 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. 図3.PNG 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. 図4.PNG 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. 図4.PNG 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. 図5.PNG 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. ..

Recommended Posts

Bubble sort without using sort
Quicksort without using sort
Bubble sort
Bubble sort
Modulo without using%
Bubble sort in Python
Merge sort using recursion
Write FizzBuzz without using "="
Python beginners organize bubble sort
Gamma correction without using OpenCV
Bubble sort with fluffy animation
[Python3] Google translate google translate without using api
Slice without using Python, colon (:). a.__getitem__ (slice (3,5)).
Implemented bubble sort in Java (BubbleSort)
sort
Save files using EC2 storage without using S3
Implement OAuth without using client library (Java)
Swap 1 and 2 without using an if statement
Use webcam without screen display using python-zbar
Implemented Stooge sort in Python3 (Bubble sort & Quicksort)