Sorting by methods and built-in functions

First, consider sorting the following list.

data = [5, 3, 2, 4, 1, 6]

There are two types of sorting list types in Python, sort () and sorted (). --List-type method sort (): Sorts the list itself --Built-in function sorted (): Returns a sorted list as a new return value

List type method sort ()

Rewrite the original list itself.

data.sort()
print(data)
# [1, 2, 3, 4, 5, 6]

The default is ascending sort. Set the argument reverse to True to sort in descending order.

data.sort(reverse = True)
print(data)
# [6, 5, 4, 3, 2, 1]

Note that sort () returns None.

x = data.sort()
print(x)
# None

Built-in function sorted ()

If you specify the list you want to sort in the argument, a newly sorted list is generated and returned as a return value.

new_data1 = sorted(data)
print(new_data1)
# [1, 2, 3, 4, 5, 6]

Like sort (), sorted () is in ascending order by default. Set the argument reverse to True to sort in descending order.

new_data2 = sorted(data, reverse = True)
print(new_data2)
# [6, 5, 4, 3, 2, 1]

Sorting algorithm

Let's summarize the three sorting algorithms. I don't care about speed, memory usage, etc. because I only look at them all together. The default is ascending order, and by changing to comment, it becomes descending order.

Think sort algorithm

--Bubble sort --Insert sort --Merge sort

Bubble sort

It repeats comparing two adjacent values and sorting according to the conditions.

`bubble_sort`


for i in range(len(data)):
    for j in range(len(data) - 1):
        if data[j] > data[j+1]: # data[j] < data[j+1]
            data[j], data[j+1] = data[j+1], data[j]
print(data)
# [1, 2, 3, 4, 5, 6]

Insertion sort

Put (insert) the target in the appropriate position for the aligned data. This time, the 2-minute search is not used.

`insert_sort`


for i in range(1, len(data)):
    j = i - 1
    target = data[i]
    while data[j] > target and j >= 0: # data[j] < target
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = target
print(data)
# [1, 2, 3, 4, 5, 6]

Merge sort

Divide the list into smaller units, compare the beginnings of the two lists and combine them into one.

`merge_sort`


import math

def merge(x,y):
    m = []
    i = 0
    while i < len(x):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1
    i = 0
    while i < len(y):
        i += 1
        j = 1
        while j < len(x):
            if x[j-1] > x[j]: # x[j-1] < x[j]
                x[j-1] , x[j] = x[j] , x[j-1]
            j += 1

    while x != [] and y != []:
        if x[0] < y[0]: # x[0] > y[0]
            m.append(x.pop(0))
        else:
            m.append(y.pop(0))
    if x == []:
        m += y
    else:
        m += x
    return m

data=[7,4,2,8,1,5,3,9,6]
n = 0
i = math.log2(len(data))
while n < i+1:
    tmp = []
    k=0
    while k < len(data):
        tmp = tmp
        m=merge(data[k:k+2**n],data[k+2**n:k+2**(n+1)])
        tmp += m
        k += 2**(n+1)
    data.clear()
    data += tmp
    n += n+1

print(data)
# [1, 2, 3, 4, 5, 6]

At the end

Since this is Qiita's first post, I think there are many points that cannot be reached, so please point out. Bubble sort and insertion sort were relatively quick, but merge sort took quite some time.

Sort in Python. Next, let's think about the algorithm.