Python beginners organize bubble sort

This is a memorandum

~~ I don't think I'll forget ~~

(Addition: 2020/06 11:13: 00) I received advice from @shiracamus, so I will correct it.

What is bubble sort

Bubble sort is a sort algorithm that is also called the basic exchange method, and ** it will be this if you try to make it properly **

bable.png

Explanation of the contents

bubble.py


'''1'''def bubble(T):
'''2'''    i = len(T)-1
'''3'''    while i:
'''4'''        for j in range(i-1):
'''5'''            if T[j] > T[i]:
'''6'''                T[j],T[i] = T[i],T[j]
'''7'''        i -= 1
'''8'''    return T

Wow, it's a very short algorithm

The side who wrote it was a little surprised. Since it is so short, I will explain it with line numbers.

  1. Function declaration, argument is T created with numeric array type.
  2. ** Caution ** The number returned by len (T) is "length", so if you insert it as it is in the array number, an error will occur that refers to the outside of the array.
  3. The while statement only needs to contain characters that are true, just like ʻif, so I added ʻi alone, which has the same meaning as ʻi! = 0. --If you really want to use for, delete the first line and write for i in range (len (T) -1,0, -1): `.
  4. Here is for. range (i) is fine, but the loop is wasted once. --T [i]> T [i] Compare the same thing with false
  5. I want the right side of the array to be large, so if the left side is large, swap it.
  6. Swap. ~~ One line is enough for Sabori Makan ~~ It's beautiful because it's put together in one line.
  7. In bubble sort, the result is fixed from the back, so -1. What I don't like most about Python is that I can't do it.
  8. Returns T. If there is a loop inside and there is a form to return, it is a weirdo who wants to make it a recurrence function, so you can play it later.

Bubble sort is actually heavy

[Wiki](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83 As you can see by referring to% 88), it is characterized by being heavy because it is an algorithm that has a double loop when sorting. Also, swapping everything one by one is also a cause of heavy weight, so the improvement algorithm saves the data.

bubble2.py


def bubble2(T):
    for i in range(len(T)-1,0,-1):
        tmp = T[0]
        for j in range(1,i+1):
            if tmp < T[j]:
                tmp , T[j] = T[j], tmp
            T[j-1]=T[j]
        T[i] = tmp
        print(T)
    return T

I tried to make it on the spot, but is there any improvement in this? It should be.

Digression

I have created a program that creates a random array with no duplicate numbers, so I will give an example.

(Corrected part)

Avoid using lists as default arguments. Reference: https://docs.python.org/ja/3/faq/programming.html#why-are-default-values-shared-between-objects

I have corrected the part that was xMake (i, T = [-1]) and the text of the program.

makeLis.py


import random as r
def xMake(i,T = None ):

    if T is None:
        T = [r.randint(1,i)]*i
        return xMake( 1 , T )
    if i == len(T):
        return T

    T[i] = r.randint(1,len(T))
    for j in range(i):
        if T[i] == T[j]:
            return xMake( i , T )
    return xMake( i+1 , T )


print(xMake(10))
>>[2, 1, 3, 6, 4, 10, 9, 5, 7, 8]
print(xMake(20))
>>[13, 20, 1, 12, 7, 8, 6, 4, 17, 11, 14, 9, 18, 3, 5, 10, 15, 2, 19, 16]

~~ People who use the recurrence function even if they are willing ~~ Please tell me if there is a better or cleaner way to write.

I learned from @shiracamus. You can write clearly by using> range and sample.

By_shiracamus.py


import random as r

def xMake(i):
    return r.sample(range(1, i + 1), k=i)

print(xMake(10))
print(xMake(20))

Using random.sample makes it so much easier ...! Thank you! I am going to use it as an example!

When declaring a function, I often name it x〇〇 () (usually a number). If you write or copy a program for no purpose and change the writing style, you will make a mistake when programming if there is no rule in the function name. Then, when you actually use it, rewrite it with the replace function of the text editor to make it a name that you can understand. I don't know if this is a good thing, but since I'm not good at English, I sometimes make embarrassing things such as spelling mistakes.

Recommended Posts

Python beginners organize bubble sort
Python beginners organize heapsort
Python beginners organize quicksort
Python beginners challenge Cpaw CTF Q14 with bubble sort
[Python] Sort
Python # sort
Bubble sort
Bubble sort
Implemented Stooge sort in Python3 (Bubble sort & Quicksort)
Beginners practice Python
Python beginner's note
Python Beginner's Guide (Functions)
Python self-made class sort
Python beginners touch Pytorch (3)
Bubble sort without using sort
[Memo] Python3 list sort
Python Dictionary Beginner's Guide
Python sort cheat sheet
Custom sort in Python3
[Python] Sort collection types
Python beginners touch Pytorch (1)
Python beginners touch Pytorch (2)
Python Beginner's Guide (Introduction)
OpenCV for Python beginners
Organize types in Python
Bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, count sort (Python)
Programming beginners compared sort times
Sort Python module imports alphabetically
Learning flow for Python beginners
Python basic dict sort order
About python beginner's memorandum function
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Bubble Sort)
python in mongodb in descending sort
Python3 environment construction (for beginners)
Organize your Python development environment
3 Reasons Beginners to Start Python
Python #function 2 for super beginners
Python Beginner's Guide (Variables / Arrays)
Basic Python grammar for beginners
100 Pandas knocks for Python beginners
Python for super beginners Python #functions 1
Python #list for super beginners
~ Tips for beginners to Python ③ ~
Bubble sort with fluffy animation
Sort by date in python
About Python sort () and reverse ()
[Python] Random processing (create, select, sort)
[Python] Sort iterable by multiple conditions
Python Exercise for Beginners # 2 [for Statement / While Statement]
Python for super beginners Python # dictionary type 1 for super beginners
Machine learning summary by Python beginners
Python #index for super beginners, slices
Typing automation notes by Python beginners
Sort large text files in Python
<For beginners> python library <For machine learning>
Python #len function for super beginners
Implemented bubble sort in Java (BubbleSort)
[Python] One-liner Stalin sort with 50 characters
Beginners use Python for web scraping (1)
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
Run unittests in Python (for beginners)