It?s still under development, but it?s gonna be big!
http://www.ninjasort.com/

 

 

I'll wait on dry land, thank you ;~)

 

 

They laughed at Galileo, too. Or was that Einstein they laughed at? I forget.

 

 

Ya, but think of all the people that were laughed at and were also failures.

From the website: " Achieving this goal would mean computer science majors would no longer be forced to learn Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort, Radix Sort, Bucket Sort, etc."

I think he's missing the point of why those algorithms are taught. The fact that he's trying to beat Radix sort (assuming his is a general sorting algorithm that has no knowledge of the data, and can only get results of >, < and =) leads me to believe he doesn't understand sorting algorithms that well in the first place.

This could just be a joke, or maybe he'll stumble upon parallel computing.

 

 

I listed Radix Sort because although it?s fast, it usually requires an undesirably large amount of memory. This is a flaw. Imagine a sorting algorithm that was ultra efficient in both speed (perhaps linear) and in memory usage? that would be Ninja Sort, the ultimate sorting algorithm. Unfortunately, I haven?t figured it out yet. Oh and yes? it?s just for fun.

 

 

Sigh... dreams are good, but don't waste your life on this one.

"There are essentially two parts in creating an algorithm, coming up with a name and actually creating the algorithm. I?ve gotten the hard part over with, now I just need to create an algorithm.

So you don?t even have an algorithm?
Oh I have an algorithm, it just sucks. Below is the current source code for Ninja Sort. I?ll update it as it improves."

Sorting isn't as dead as many believe though 1995 an article that produced an algorithm that sorted in O(n log log n) (For what they exactly mean, read more yourself, it's rather complex). "Sorting in Linear Time? - Andersson, Hagerup, Nilsson, Raman (1995)"

Dream on!

Gil

 

 

Is there a lower bound for sorting? A sorting algorithm based on comparing elements with each other has a theoretical lower bound of O(n log(n)). That is not too hard to prove (typical homework in an algorithms course)...

So to beat O(n log(n)) you have to do something other than comparing the elements with each other!

 

 

Simple (using pseudo code)....

    Array sortArray(Array a)
    {
        return a;
    }
 

Sorting is only problem and limited when the data is not sorted in the first place.

It is all in the assumptions.

There are other problems that not knowing the assumptions can cause. For instance when someone tries to implement a binary sort on data which only lives on the hard drive.

 

 

As the last person pointed out, some algorithms (including Ninja Sort) can sort in linear time as a best case (if the numbers happen to be sorted). Because this is pretty obvious, I?m assuming that the other guy was speaking of a lower bound for the worst case time complexity of all comparison based sorting algorithms. If this is the case, I?d like to see such a proof. Not because I don?t believe it, but because I?m interested.

 

 

******?.

http://www.bowdoin.edu/~ltoma/teaching/cs231/fall04/Lectures/sortLB.pdf

 

 

The proof has a fundamental flaw in that it assumes that one can't travel above the speed of light. We all know it is posible to travel at up to Warp 9 before the wheels drop off!

 

 

Okay, maybe they didn't laugh at Einstein, but we did laugh at Capt Kirk when he attempted the flying leg kick.

 

 

public final class NinjaSort
{
      private static final java.util.Random rng = new java.security.SecureRandom();
      private NinjaSort(){}
      public static void sort(List<Comparable> c)
      {
         while(!isSorted(c))
            java.util.Collections.shuffle(c, rng);
      }
      private static boolean isSorted(Comparable[] c)
      {
         for(int x = 0, N = c.size() - 1 ; x < N ; x++)
            if(c.get(x).compareTo(c.get(x + 1)) > 0)
               return false;
         return true;
      }
}

 

 

So ah? I was thinking? what if there was some magical clever way to sort numbers using the concept of Radix Sort but by only swapping numbers. Like maybe the first 10 positions of the array can somehow be used as a bases for how and where numbers would be swapped. I realize there would be conflicts, but maybe they can be ?controlled? by simply being shifted as numbers are inserted. I don?t know? but does anything like this exist?

 

 

Like a counting sort, or an attempt to get a better log base?
If you can find a way, and you've got the time, more power to ya'.

It seems like the only way to get a better log base would be probablistically...
Now I've got a sort to chew on, heh...