I tried to implement merge sort in Python with as few lines as possible

It's probably natural to hear that my friends are studying the implementation of algorithms from time to time and working on the implementation of merge sort. A mysterious game was held in which it was better to implement it with as few lines as possible because it was a big deal. I heard that my friend wanted to do it in Python, so I decided to do it in Python. I won't lose

rule

--Use a data array in which numbers from 1 to 10 are randomly arranged. --The code of the data array generation and output part is common, so do not mess with it --Anyway, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] should be output.

The code of the common part is as follows

from data import generate_data

data = generate_data() #Numbers from 1 to 10 are lined up in pieces
print(data)

#Implemented below this

There is data.py in another file, and the generate_data function there will generate the data. The data will be something like [5, 1, 3, 9, 2, 8, 7, 4, 10, 6]. I just made the contents of data.py properly, so I will omit it here.

Implementation result

When I wrote it according to the above rules, it became like this.

from data import generate_data

data = generate_data() #Numbers from 1 to 10 are lined up in pieces
print(data)

#Implemented below this
divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]
merge = lambda left, right: [right.pop(0) if len(left) == 0 else left.pop(0) if len(right) == 0 else left.pop(0) if left[0] < right[0] else right.pop(0) for i in range(len(left) + len(right))] if type(left[0]) is int and type(right[0]) is int else merge(left, merge(right[0], right[1])) if type(left[0]) is int else (merge(merge(left[0], left[1]), right) if type(right[0]) is int else merge(merge(left[0], left[1]), merge(right[0], right[1])))
print(merge(divide(data)[0], divide(data)[1]))

output


[5, 1, 3, 9, 2, 8, 7, 4, 10, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

There was no problem even if I was told "Long. In three lines". I will explain it for the time being.

Rough flow

Merge sort seems to be based on the "divide-and-conquer method", and it seems that the data array is once divided to the minimum unit, and the data is appropriately selected from each divided data, combined, and then reordered. The person who thought Since many ancestors have explained various details of the algorithm, I will omit it here.

So, the implementation result of the above three lines is Line 1: Split Line 2: Join Line 3: Output The roles are divided like this.

Let's start with "splitting".

Implementation of "split"

Purpose

This is the code in question.

"Split" code


divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]

If the data array is [7, 6, 3, 2, 4, 5, 1, 8], the purpose of "splitting" is from this array.

[
    [
        [6, 7],
        [2, 3]
    ],
    [
        [4, 5],
        [1, 8]
    ],
]

It means to generate a multiple array with a hierarchical structure like. Divide the minimum unit in half so that the number of elements is 2 or less, and if the number of elements in the minimum unit is 2 or less, order them in ascending order. I'm doing something like that. The ones that are ordered in ascending order are originally the role of "coupling", but it is convenient to do it here, so I will do it at this point.

Rewrite

The "split" function is essentially like this.

Original shape


def divide(data):
    if (len(data) <= 2):
        return data if len(data) == 1 else [min(data), max[data]]
    else:
        half_count = len(data) // 2
        left = [data[i] for i in range(half_count)]
        right = [data[i] for i in range(half_count, len(data))]
        return [divide(left), divide(right)]

When the number of elements is 2 or less, the array is returned in ascending order, and in other cases, the above hierarchical structure can be realized by recursing in half for left and right. I will.

After `ʻelse, if you use the variable of half_countdirectly by replacing it with len (data) // 2, you can avoid using the variable. Oh, I used leftand right`` only once! If you do it as it is within the return value

The return value is crazy ~


def divide(data):
    if (len(data) <= 2):
        return data if len(data) == 1 else [min(data), max[data]]
    else:
        return [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]

Will be. Ah, both ʻif`` and ʻelsehave only one return`` sentence. It ’s a ternary operator and it ’s just one line.

One line with ternary operator


def divide(data):
    return data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]

It calms down to the feeling. If there is only one return in the function, use a lambda expression

Make it a lambda expression


divide = lambda data: data if len(data) == 1 else [min(data), max(data)] if len(data) <= 2 else [divide([data[i] for i in range(len(data) // 2)]), divide([data[i] for i in range(len(data) // 2, len(data))])]

It fits perfectly in one line. It's nice to be able to use recursion even with lambda expressions.

Implementation of "join"

Purpose

This is the code in question.

"Join" code


merge = lambda left, right: [right.pop(0) if len(left) == 0 else left.pop(0) if len(right) == 0 else left.pop(0) if left[0] < right[0] else right.pop(0) for i in range(len(left) + len(right))] if type(left[0]) is int and type(right[0]) is int else merge(left, merge(right[0], right[1])) if type(left[0]) is int else (merge(merge(left[0], left[1]), right) if type(right[0]) is int else merge(merge(left[0], left[1]), merge(right[0], right[1])))

Guhe, Nageyo ... The purpose of "joining" is

Data after division


[
    [
        [6, 7],
        [2, 3]
    ],
    [
        [4, 5],
        [1, 8]
    ],
]

It is to combine the divided data in order from the lower layer, and finally combine all the data to return to the original form of one layer. As a flow

Flow 1


[
    [2, 3, 6, 7],
    [1, 4, 5, 8]
]

Flow 2


[1, 2, 3, 4, 5, 6, 7, 8]

And so on. To achieve this flow, the merge function

--Both the left and right elements of the argument are combined when their child elements are numeric --Joining is done by pop the smaller of the first elements on the left and right and add them as child elements of the new array. --Otherwise, recurse with the child elements of the left and right elements so that the child elements of the left and right elements are numerical values.

I will do something like that. It's hard to understand even if you explain it in words, so let's look at the code.

Rewrite

The "join" function originally looks like this.

Original shape


def merge(left, right):
    if type(left[0]) is int and type(right[0]) is int: #Both when the child element is a number
        result = [] #Prepare a new array
        for i in range(len(left) + len(right)):
            # left,When the right element disappears, pop the one that still exists
            if len(left) == 0:
                result.append(right.pop(0))
            elif len(right) == 0:
                result.append(left.pop(0))
            #If both are still left, pop the smaller one
            elif left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        return result
    else:
        """ 
Depending on the hierarchy, the child elements may be numbers or arrays even at the same level.
Recurse leaving the one whose child element is numeric
        """
        if type(left[0]) is int:
            return merge(left, merge(right[0], right[1]))
        elif type(right[0]) is int:
            return merge(merge(left[0], left[1]), right)
        else:
            return merge(merge(left[0], left[1]), merge(right[0], right[1]))

See comments for implementation details. I intentionally made it complete with `ʻif-elif-else``. This means that you can use the ternary operator to make the return value one line, and you can write the function in one line with a lambda expression, just like in the case of "split"!

When I tried to express result in a list comprehension notation, I was worried that pop would reduce the elements properly, but when I actually tried it, it decreased properly. I was able to represent the for part in one line using list comprehensions and ternary operators.

Implementation of "output"

"Output" code


print(merge(divide(data)[0], divide(data)[1]))

Originally here

data = divide(data)
print(merge(data[0], data[1]))

And divide should be executed only once, but as you can see, it is a waste of the number of lines to exercise 1 for securing variables, so I forcibly execute it twice. Well, if the number of elements is about 10, it's an error.

end

I'm sure it will be the winning code for the Fucking Code of the Year Awards in me. Thank you very much.

Recommended Posts

I tried to implement merge sort in Python with as few lines as possible
I tried to implement selection sort in python
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
I tried to implement ADALINE in Python
I tried to implement PPO in Python
I tried to implement TOPIC MODEL in Python
I tried to implement Minesweeper on terminal with python
I tried to implement a pseudo pachislot in Python
I tried to implement Dragon Quest poker in Python
I tried to implement an artificial perceptron with python
I tried to implement GA (genetic algorithm) in Python
I tried to implement a one-dimensional cellular automaton in Python
I tried to implement the mail sending function in Python
I tried to implement Harry Potter sort hat with CNN
I tried to implement blackjack of card game in Python
I tried to implement Autoencoder with TensorFlow
I tried to implement a misunderstood prisoner's dilemma game in Python
I tried to find out if ReDoS is possible with Python
I tried to implement CVAE with PyTorch
I tried to implement a blockchain that actually works with about 170 lines
I tried to implement Bayesian linear regression by Gibbs sampling in python
I tried to implement a card game of playing cards in Python
I tried to implement reading Dataset with PyTorch
I tried to integrate with Keras in TFv1.1
I tried to get CloudWatch data with Python
I tried to output LLVM IR with Python
I want to merge nested dicts in Python
I tried to automate sushi making with python
I tried to explain what a Python generator is for as easily as possible.
I tried to implement what seems to be a Windows snipping tool in Python
I tried to graph the packages installed in Python
I want to easily implement a timeout in python
I tried to implement and learn DCGAN with PyTorch
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to draw a route map with Python
I tried to solve the soma cube with python
I tried to get started with blender python script_Part 02
I was addicted to scraping with Selenium (+ Python) in 2020
I tried to implement time series prediction with GBDT
I want to work with a robot in python.
I tried to automatically generate a password with Python3
I tried to summarize how to use pandas in python
I tried to solve the problem with Python Vol.1
I tried to analyze J League data with Python
I tried to implement Grad-CAM with keras and tensorflow
I tried to implement SSD with PyTorch now (Dataset)
I tried to solve AOJ's number theory with Python
I tried fp-growth with python
I tried scraping with Python
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
I tried to implement PCANet
I tried gRPC with Python
I tried scraping with python
I tried to implement StarGAN (1)
I tried to implement a volume moving average with Quantx
I tried to find the entropy of the image with python
I tried to simulate how the infection spreads with Python
I tried to create API list.csv in Python from swagger.yaml