[Python] Try to make a sort program by yourself. (Selection sort, insertion sort, bubble sort)

[Python] Try to make a sort program by yourself. (Selection sort, insertion sort, bubble sort)

  1. [Selection sort](#selection sort)
  2. [Insert Sort](# Insertion Sort)
  3. [Bubble Sort](#Bubble Sort)

Selection sort

Find the minimum value and replace it with the first element.

In the actual processing, it is necessary to combine multiple ideas. (1) Find the minimum value (2) Replace the minimum value with the first value (3) Repeat (1) and (2) in a value whose beginning is not fixed


Selection sort


def min_init(arr, x):
  min = x
  for i in range(x, len(arr)):
    if arr[min] > arr[i]:
      arr[i], arr[min] = arr[min], arr[i]

def min_sort(arr):
  for j in range(0, len(arr)-1):
    min_init(arr, j)
  print(arr)

Execution example


a = [2,4,5,3,10,1,8,6]
min_sort(a)

#[1, 2, 3, 4, 5, 6, 8, 10]

Way of thinking

(1) Find the minimum value

First, consider the formula for finding the minimum value. The initial value of min is set to 0th, and it is compared with the next numerical value. Swap min when the next number is small

python


#Find the minimum value
def min_val(arr):
  min = 0
  for i in range(1, len(arr)):
    if arr[min] > arr[i]:
      min = i
  print(a[min])


#Verification
a = [2,4,5,3,10,1,8,6,3,2]
min_val(a)

#1

(2) Replace the minimum value with the first value

By applying the above program for finding the minimum value, the value is exchanged with the first value when the minimum value is found.

Finally, find the array with the smallest value at the beginning.

python


#Find the minimum value and move it to the beginning of the array
def min_first(arr):
  min = 0
  for i in range(1, len(arr)):
    if arr[min] > arr[i]:
      arr[i], arr[min] = arr[min], arr[i]
  print(a)


#Verification
a = [2,4,5,3,10,1,8,6]
min_first(a)

#[1, 4, 5, 3, 10, 2, 8, 6]

(3) Repeat (1) and (2) in a value whose beginning is not fixed

The process is repeated by applying the above. Note that the initial value of min is a variable. By doing this, the comparison target range shifts backward one by one.

If it is set to a constant, it will always be compared with the same value and the target output will not be obtained.

python


def min_init(arr, x):
  min = x
  for i in range(x, len(arr)):
    if arr[min] > arr[i]:
      arr[i], arr[min] = arr[min], arr[i]

def min_sort(arr):
  for j in range(0, len(arr)-1):
    min_init(arr, j)
  print(arr)

#Verification
a = [2,4,5,3,10,1,8,6]
min_sort(a)

#[1, 2, 3, 4, 5, 6, 8, 10]

## Insertion sort How to determine where to add the next number, assuming that the beginning has been sorted.

-Compare the unsorted first value with the previous value -If the unsorted value is smaller, the unsorted value is overwritten with a larger value. (Unsorted values are stored as variables) ・ Confirm when the unsorted one becomes larger

python


def insert_sort(arr):
  for i in range(1,len(arr)):
    tmp = arr[i]  #Unsorted top
    j = i -1   #Sorted last (one before unsorted)
    
    #Compare the elements and if tmp is smaller, j+Replace the value of 1
    while arr[j] > tmp and j >= 0:
      arr[j+1] = arr[j]
      j -= 1

    #If tmp is larger, j+Confirm 1 with tmp
    arr[j+1] = tmp

Verification


a = [2,4,5,3,10,1,8,6]
insert_sort(a)
print(a)

#[1, 2, 3, 4, 5, 6, 8, 10]

What is tmp

variable. Used to specify temporary variables whose values are being added or removed sequentially. Abbreviation for temporary.


## Bubble sort From behind, compare and exchange adjacent elements.

When the first two are compared, the first is fixed. Repeat the same operation for the remaining elements.

As a processing flow, (1) Compare the last value with the adjacent value and exchange if it is smaller. (2) Repeat the work of (1). The beginning is fixed once.

python


def bubble_sort(arrs):
  for j in range(0, len(arrs)):
    exchange(arrs, j)

def exchange(arr, j):
  for i in range(len(arr)-1, j, -1):
    if arr[i-1] > arr[i]:
      arr[i-1], arr[i] = arr[i], arr[i-1]
#Verification
a = [2,4,5,3,10,1,8,6]
bubble_sort(a)
print(a)

#[1, 2, 3, 4, 5, 6, 8, 10]

** ▼ (Reference) Compare and exchange adjacent values **

python


#Move small numbers forward
def exchange(arr):
  for i in range(len(arr)-1, 0, -1):
    if arr[i-1] > arr[i]:
      arr[i-1], arr[i] = arr[i], arr[i-1]
  print(arr)


#Verification
a=[8,2,6,1]
exchange(a)

#[1, 8, 2, 6]

Recommended Posts

[Python] Try to make a sort program by yourself. (Selection sort, insertion sort, bubble sort)
I tried to program bubble sort by language
Try to make a "cryptanalysis" cipher with Python
Try to make a dihedral group with Python
Try to make a Python module in C language
Try to make a command standby tool with python
Bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, count sort (Python)
[Python] How to make a list of character strings character by character
Answer to AtCoder Beginners Selection by Python3
[Python] How to make a class iterable
Try to make a capture software with as high accuracy as possible with python (2)
[Ev3dev] Let's make a remote control program by Python with RPyC protocol
How to sort by specifying a column in the Python Numpy array.
Try to calculate a statistical problem in Python
Try to make BOT by linking spreadsheet and Slack with python 2/2 (python + gspread + slackbot)
Try to draw a life curve with python
I want to make a game with Python
Try to make BOT by linking spreadsheet and Slack with python 1/2 (python + gspread + slackbot)
[python] How to sort by the Nth Mth element of a multidimensional array
WEB scraping with python and try to make a word cloud from reviews
[Python] How to sort instances by instance variables
I tried to implement selection sort in python
Lark Basics (Python, Lark to make a shell-like guy)
Try to make a blackjack strategy by reinforcement learning (② Register the environment in gym)
Let's make a leap in the manufacturing industry by utilizing the Web in addition to Python
(Python) Try to develop a web application using Django
How to make a Python package using VS Code
[Python] I want to make a nested list a tuple
Machine learning beginners try to make a decision tree
A program to write Lattice Hinge with Rhinoceros with Python
How to save a table scraped by python to csv
Bubble sort in Python
Try to make a blackjack strategy by reinforcement learning (③ Reinforcement learning in your own OpenAI Gym environment)
Try to make it using GUI and PyQt in Python
How to run a Python program from within a shell script
I wrote a program quickly to study DI with Python ①
Write a python program to find the editing distance [python] [Levenshtein distance]
Experiment to make a self-catering PDF for Kindle with Python
[Python] A program that creates a two-dimensional array by combining integers
Try to bring up a subwindow with PyQt5 and Python
[Python] Try to classify ramen shops by natural language processing
I tried to sort a random FizzBuzz column with bubble sort.
I tried to make a stopwatch using tkinter in python
How to override a user-defined method generated by python swig
[Introduction to Tensorflow] Understand Tensorflow properly and try to make a model
I want to make input () a nice complement in python
Just try to receive a webhook in ngrok and python
[Python] I tried to make a simple program that works on the command line using argparse.
A road to intermediate Python
Newcomer training program by Python
Try to understand Python self
Make a bookmarklet in Python
Make a fortune with Python
Python beginners organize bubble sort
Try to select a language
Sort by date in python
[5th] I tried to make a certain authenticator-like tool with python
How to batch start a python program created with Jupyter notebook
Join csv normalized by Python pandas to make it easier to check
Rubyist tried to make a simple API with Python + bottle + MySQL
[2nd] I tried to make a certain authenticator-like tool with python