Instant sort - A new sorting algorithm

[urntme]

Hello Encode.su community members!

My name is Ananth Gonibeed and my username is urntme on this forum.

I previously posted on the data compression section of this forum.

Following some messages by other members of this community on other threads that I posted in, I decided to try and figure out how to code.

However, instead of trying to code the Data compression algorithm I mentioned in those threads, I decided to try something much simpler and much more accessible to my coding level for a first attempt.

I decided to try and code my “Instant sort” sorting algorithm.

So this sorting algorithm is called “Instant sort” and it basically instantly sorts numbers. It is an algorithm that I came up with. It has a time complexity of O(1) and it accomplishes this because it’s a new and different type of sorting algorithm.

You can read all about it in the attached paper.

I have attached a couple of things to the zip archive attached to this thread:

1) The paper describing “Instant Sort” the algorithm and the basic concept around it.
2) The executable you can run to test out a very very primitive version of the algorithm.
3) A document explaining how the code for the very very primitive version of the algorithm works.
4) The source code for the program I created.

I used C++ and the syntax was a bit unfamiliar to me at first but the thing works the way it’s supposed to so I can’t complain.

This is version 1 and I will probably build upon it further over time once I figure out how to do more complex versions of it.

Let me know your thoughts and anything you want to say.

Kudos,
Ananth.

P.S: You can contact me at this email id: ananth.gonibeed@gmail.com if you want to contact me personally for any reason.

[Gotty]

Interesting solution, indeed.I believe, the time complexity is O(n), not O(1). You need n-1 multiplications, n-1 divisions, and n-1 modulus operations with the current implementation.

Sorting just a few very small numbers puts this algorithm in a different category from the general sorting algorithms (like the mentioned quick sort). So saying that your method is faster than quick sort is kind of cheating. The same way I could say, that I have just implemented a sorting method even faster than yours: it sorts two numbers:
if(a<b)printf("%d, %d",a,b); else printf("%d, %d",b,a);
It is certainly faster than yours and uses no extra memory.

>>Here the range is 0-50 and the number of items n is 7.
Memory requirement in this case is... how much?

To be fixed: "database" should be renamed to "array"; "speed" to "time complexity", "searching" to "lookup".

[urntme]

Thank you very much for your comment.

Interesting solution, indeed.I believe, the time complexity is O(n), not O(1). You need n-1 multiplications, n-1 divisions, and n-1 modulus operations with the current implementation.

Hmmmm. Well, okay, I have attached an implementation of the algorithm that uses 3d arrays instead of the technique I used in version 1. How about now? What do you estimate the time complexity to be?

Sorting just a few very small numbers puts this algorithm in a different category from the general sorting algorithms (like the mentioned quick sort). So saying that your method is faster than quick sort is kind of cheating.

Yes. Well I agree with you here. But I wouldn't call it cheating. It depends on the perspective you use. I believe the apt expression that my mother always tells me in these situations is: "Both are right and both are wrong."

>>Here the range is 0-50 and the number of items n is 7.
Memory requirement in this case is... how much?

To be honest it would require a colossal amount of memory here. I don't know for sure. The exact details depend on how it is implemented. However, I already mentioned that this is one of the drawbacks of this algorithm in the paper.

To be fixed: "database" should be renamed to "array"; "speed" to "time complexity", "searching" to "lookup".

Okay. I will do that. Thank you for your comment.

[Gotty]

Hmmmm. Well, okay, I have attached an implementation of the algorithm that uses 3d arrays instead of the technique I used in version 1. How about now? What do you estimate the time complexity to be?

The system will need to access an array element in a 2d array (with the current concrete implementation it needs to do one multiplication by 5 (or an equivalent operation, like (i<<2)+1) to find the row of the 2nd dimension in the 1st dimension.
Being in the 2nd dimension it will need to read the 2 sorted elements (that's the 3rd dimension). Generally it needs n-1 multiplications and read n elements. ((Supposing that the c++ compiler optimized the the code properly otherwise it will do n*(n+1) multiplications with the current implementation instead of n+1.))
The relationship between the number of elements and the time it needs "to sort" them is linear. That's O(n).
Simply put: the more numbers to be sorted the more time it needs (linearly).

To be honest it would require a colossal amount of memory here. I don't know for sure.

Yes. Since it is not really feasible it's not a very good example. Could you replace it with something "smaller"? Examples are best when realistic.

[urntme]

Thank you for the feedback and your comments.

The system will need to access an array element in a 2d array (with the current concrete implementation it needs to do one multiplication by 5 (or an equivalent operation, like (i<<2)+1) to find the row of the 2nd dimension in the 1st dimension.
Being in the 2nd dimension it will need to read the 2 sorted elements (that's the 3rd dimension). Generally it needs n-1 multiplications and read n elements. ((Supposing that the c++ compiler optimized the the code properly otherwise it will do n*(n+1) multiplications with the current implementation instead of n+1.))
The relationship between the number of elements and the time it needs "to sort" them is linear. That's O(n).
Simply put: the more numbers to be sorted the more time it needs (linearly).

Yes. Hmmm. Thank you for your response. My confusion was that I thought array output was always a O(1) process. But I guess I was mistaken.

Well, I did a bit of searching and as you say I couldn't figure out how to make this algorithm a O(1) process for most practical applications.

However, I think I did manage to make it a O(1) process in an odd way, and I have attached the C++ source files to this so you can see how I did it. Now it might not be the most practical way of doing this, but... you be the judge. I don't want to say anything else.

Yes. Since it is not really feasible it's not a very good example. Could you replace it with something "smaller"? Examples are best when realistic.

Yes. Okay. I will do that. Thank you for your response.

Okay. Thank you for the time, your patience, and your perseverance and for all the feedback you've given me.

Take care.

Kudos,
Ananth.

[Gotty]

My confusion was that I thought array output was always a O(1) process.

Accessing an array element in a one dimensional array is indeed O(1). What you are doing is however accessing an array element in an n dimensional array. For the system to calculate exact the memory position it needs to do n-1 multiplications (and n-1 additions).

However, I think I did manage to make it a O(1) process in an odd way, and I have attached the C++ source files to this so you can see how I did it.

That's still O(n). Whenever you are unsure, just extend your algorithm to more elements, and figure out if it will need the same amount of time as with 2 elements or more. If it is more, it cannot be O(1) (meaning "constant time").
Your 2 new versions will need to process some characters from the input and output some characters. With 2,3,4,... numbers to be sorted is the number of characters to be processed the same or more as we increase n? It is more and more.
You cannot ever make a sorting algorithm better than O(n) - only if you have a way of parallel processing the inputs and outputting the result.

Now you have more implementations for your sorting idea and that means you spent some time for thinking, also got a bit more experienced in coding. How about doing something more complex?
You don't need to try inventing something extraordinary ("the best" or "the fastest") for now. Just learn. Later you will get there. Give yourself time.

[urntme]

Now you have more implementations for your sorting idea and that means you spent some time for thinking, also got a bit more experienced in coding. How about doing something more complex?
You don't need to try inventing something extraordinary ("the best" or "the fastest") for now. Just learn. Later you will get there. Give yourself time.

Okay. I will do that.

Thank you for all your inputs so far. It is greatly appreciated.

I am person who believes that we just need to trust our hearts and keep moving forward. So yes, I will do that.