[Neta] Sorting algorithm of O (1)

Introduction

One day, I found an article like this. Sort of O (1) faster than Stalin sort

"Crush the truth and give out predetermined information"

This sort, which was named ** Large Headquarters Announcement Sort **, looks interesting. When I checked if there was anything else, I found various things, so I will summarize them.

Try to implement

Large headquarters announcement sort

Propaganda.py


def propaganda_sort(list):
    return [1, 2, 3]

input [3, 4, 6, 1, 2, 5, 9, 8, 10, 7] output [1, 2, 3] It's an algorithm that feels like that.

Autoclassy sort

Discovered Auto Classy Sort.

Autocracy.py


def autocracy_sort(list):
    return [list[0]]

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

Compared to the sort announced by the main headquarters, the original arrangement is considered for the time being. Of course, the amount of calculation is also $ O (1) $.

Spiritual sort

This sort was posted on the Kuina-Chan site.

I came up with an algorithm called "spiritual sort". It is a miracle algorithm of O (1) that makes you think that it is arranged in order by deeply believing that it is arranged in order for a data string that is not arranged in order. Try to implement it.

Spiritual.py


def spiritual_sort(list):
    return list

input [3, 4, 6, 1, 2, 5, 9, 8, 10, 7] output [3, 4, 6, 1, 2, 5, 9, 8, 10, 7] This sorting algorithm is amazing. You can see that they are lined up in order. e? Isn't it in order? **What are you saying? Please take a closer look. Isn't it lined up firmly? Don't you know? ** **

There is no novelty as it is

If it ends like this, it's okay because I'm just wrestling with someone else's loincloth. That's why I think about it.

There is only one requirement below! ** Must be $ O (1) $. ** ~~ Honestly, isn't it too much game? ~~ I tried my best and came up with only one.

Name it ** Censorship Sort **.

Censorship sort

To be honest, the content announced by the large headquarters announcement sort has only changed, so it is subtle as a novelty, but I could only think of this. The contents are as follows.

  1. Upon receiving input, ** squeeze everything to get started. ** **
  2. After squeezing, view the censored and empty list.

When this is implemented, it looks like this.

Censorship.py


def censorship_sort(list):
    print("WARNING: This input array was deleted for legal reasons.")
    return []

input [3, 4, 6, 1, 2, 5, 9, 8, 10, 7] output WARNING: This input array was deleted for legal reasons. [] Since all the elements have been erased, it can be sorted naturally, and the output is the same when an array of infinite length is brought in, so it is $ O (1) $.

reference

Sort of O (1) faster than Stalin sort Autoclassy sort with improved "Stalin sort" Kuina-Chan: Kuina-chan Note

Recommended Posts

[Neta] Sorting algorithm of O (1)
Visualize the behavior of the sorting algorithm with matplotlib
Explanation and implementation of ESIM algorithm
Sorting algorithm and implementation in Python
Implementation of original sorting in Python
Implementation of Dijkstra's algorithm with python