I tried to make a new sorting algorithm, but I don't know if it's really new

I made a new sorting algorithm!

At the moment, I came up with a sorting algorithm. I thought, "Isn't it going to work?", And when I wrote a little flow on a piece of paper around that area, there seems to be nothing strange about it. I implemented it with the glue of "Then, do you want to implement it! W".

Recently, due to lack of material, I have only introduced past programs, but this is one of them, and it is implemented in java. I think this was about a year ago.

The name of the algorithm is "Hanoi Sort"

The reason for this naming is that the move to achieve sorting using two stacks was similar to solving the Tower of Hanoi.

ハノイの塔.png

The following shows how to sort by Hanoi sort.

hanoi.gif

Explanation of the algorithm

This sorting algorithm uses two stacks, a sorting stack and a temporary storage stack. The sort flow is shown below.

  1. Fill the sort stack with one value
  2. Replace the contents of the sort stack with the temporary storage stack.
  3. Store the first value of the input array in the comparison variable
  4. Compare the value on the temporary storage stack with the value at the beginning of the array, and pack the smaller value on the sort stack.
  5. Do until the temporary storage stack is empty
  6. Repeat 2-5

Please forgive me for the poor explanation. I think that the movement of the value is easy to understand if you can see the gif video above.

For the time being, I make full use of the stack and put in and out values while interposing comparisons. I'm not very confident in calculating the amount of calculation, but I think it's probably O (n ^ 2), so it's not an excellent sort. By the way, when comparing the sort time of 30,000 integers with the bubble sort, the processing time

Hanoi sort Bubble sort
3.997s 1.53s

I ended up with a miserable result. Is the amount of calculation more than O (n ^ 2)?

I think I thought about it myself, but maybe it already exists

I don't even know all the sorting algorithms. Maybe there is already a sort with the same mechanism, so if anyone knows it, please let me know!

Finally drop the fucking code

hanoi_sort.java


import java.util.*;
import java.io.*;

class hanoi_sort{
    static int[] data;
    public static void main(String[] args) {
        int dataNum = 30000;
        data = new int[30000];
        String[] strarray = new String[30000];
        int k = 0;

        try{
             File file = new File("numbers.txt");
             BufferedReader br = new BufferedReader(new FileReader(file));
             String str= null;
             k = 0;
             while((str = br.readLine()) != null){
                 strarray[k]=str;
                 data[k] = Integer.parseInt(strarray[k]);
                 System.out.println("[" + k + "]" + data[k]);
                 k++;
             }

             br.close();
        }catch(FileNotFoundException e){
              System.out.println(e);
        }catch(IOException e){
              System.out.println(e);
        }

        for(int i = 0; i < dataNum; i++){
            System.out.println("[" + i + "]: " + data[i]);
        }

        System.out.println("--------------sort---------------");

        Deque<Integer> dequeFirst = new ArrayDeque<>();
        Deque<Integer> dequeSecond = new ArrayDeque<>();
        int box = 0;
        int count = 0;
        int countF = 0;
        boolean flag = true;
        dequeFirst.push(data[0]);
        countF++;
        double start = System.currentTimeMillis();
        for(int i = 1; i < dataNum; i++){
            flag = true;
            while(flag){
                box = dequeFirst.pop();
                countF--;
                if(box <= data[i]){
                    dequeFirst.push(box);
                    countF++;
                    dequeFirst.push(data[i]);
                    countF++;
                    for(int j = 0; j < count; j++){
                        dequeFirst.push(dequeSecond.pop());
                        countF++;
                    }
                    count = 0;
                    flag = false;
                }else{
                    dequeSecond.push(box);
                    count ++;
                    if(countF == 0){
                        dequeFirst.push(data[i]);
                        countF++;
                        for(int j = 0; j < count; j++){
                            dequeFirst.push(dequeSecond.pop());
                            countF++;
                        }
                        count = 0;
                        flag = false;
                    }
                }
            }
        }
        double end = System.currentTimeMillis();

        for(int i = 0; i < dataNum; i++){
            System.out.println("[" + i + "]: " + dequeFirst.pop());
        }
        System.out.println("sort time: " + (end - start)  + "ms");
        System.out.println("sort time: " + (end - start)/1000  + "s");
    }
}

By the way, the input is a text file, and by reading the one with an integer written on each line, the numerical value is stored in the array (everywhere fucking specification) Like this ↓

6418
18183
13643
6535
8436
3820
8969
19150
11902
4122
.
.
.

The programs and ideas of a year ago are embarrassing to look back on.

Until the end Thank you for reading!

Recommended Posts

I tried to make a new sorting algorithm, but I don't know if it's really new
11 items I don't know if it's good to know about JAVA
It's new, but I tried using Groonga
I tried to make a login function in Java
I tried using Hotwire to make Rails 6.1 scaffold a SPA
I tried to make a client of RESAS-API in Java
[Unity] I tried to make a native plug-in UniNWPathMonitor using NWPathMonitor
[Java] I tried to make a maze by the digging method ♪
I tried to make a group function (bulletin board) with Rails
I don't know anything, I tried to make TODO while studying ruby ​​on rails for 3 days by myself
[Java beginner] I got a little deeper understanding of "It's time to use new", so make a note
I tried to make a parent class of a value object in Ruby
I tried to make a simple face recognition Android application using OpenCV
[iOS] I tried to make a processing application like Instagram with Swift
I tried to make a Web API that connects to DB with Quarkus
I made a virtual currency arbitrage bot and tried to make money
I tried to make a talk application in Java using AI "A3RT"
If you want to make a zip file with Ruby, it's rubyzip.
[LINE @] I tried to make a Japanese calendar Western calendar conversion BOT [Messaging API]
I tried to make a machine learning application with Dash (+ Docker) part3 ~ Practice ~
Java String class methods that are a little useful to know but don't know
A story when I tried to make a video by linking Processing and Resolume
I tried to make a simple game with Javafx ① "Let's find happiness game" (unfinished)
[Android] I tried to make a material list screen with ListView + Bottom Sheet
[Small story] I tried to make the java ArrayList a little more convenient
I tried to make Basic authentication with Java
java I tried to break a simple block
I tried to develop a man-hour management tool
I did Java to make (a == 1 && a == 2 && a == 3) always true
I tried to develop a DUO3.0 study website.
I wanted to make (a == 1 && a == 2 && a == 3) true in Java
I tried to create a LINE clone app
I tried to develop a website to record expenses.
I tried to implement a server using Netty
I tried to break a block with java (1)
I don't know, so I'm going to write a list (you don't have to read it)
I tried to make a simple game with Javafx ① "Let's find happiness game" (unfinished version ②)
MockMVC returns 200 even if I make a request to a path that does not exist
I tried to make a message function of Rails Tutorial extension (Part 1): Create a model
I tried to develop a ramen shop sharing website.
I tried to decorate the simple calendar a little
[Rails] I don't know how to use the model ...
I tried to create a Clova skill in Java
I tried to make FizzBuzz that is uselessly flexible
I tried to implement the Euclidean algorithm in Java
I tried to make a reply function of Rails Tutorial extension (Part 3): Corrected a misunderstanding of specifications
I tried to make the sample application into a microservice according to the idea of the book "Microservice Architecture".
[Java] I tried to make a rock-paper-scissors game that beginners can run on the console.
I tried to make a message function of Rails Tutorial extension (Part 2): Create a screen to display