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]
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
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]
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]
-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]
variable. Used to specify temporary variables whose values are being added or removed sequentially. Abbreviation for temporary.
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]