Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Is this considered a valid sorting algorithm?

  1. Dec 6, 2015 #1
    Let me know if I've invented a valid O(n) sorting algorithm.

    Code (Text):

    public void Sort ( this List<T> L )
    {
       // Check every second whether L is sorted
       // Given enough time, natural bit flips will eventually make L sorted
        while ( !L.IsSorted() ) Thread.Sleep(1000);
    }

    public bool IsSorted ( this List<T> L )
    {
        // Returns true or false depending on whether L is in ascending order
       for ( int i = 1, n = L.Length; i < n; ++i ) if ( L[i-1] > L[i] ) return false;
       return true;
    }
     
     
  2. jcsd
  3. Dec 6, 2015 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Have you tested this sorting method, and does it actually work?
    If so, can you explain the concept "natural bit flips"?
     
  4. Dec 6, 2015 #3

    Filip Larsen

    User Avatar
    Gold Member

    No, not unless you use a very alternative definition of what "valid" means.

    Assuming that you algorithm comprise of waiting for stray cosmic rays and other quantum phenomenon to flip bits and then hope luck will turn it into a sorted array, you may want to ask yourself some questions:
    • How many times will IsSorted be called before the array is sorted? If we call that number M (and ignore the 1 sec sleep) the time-complexity of your algorithm is now O(M*N).
    • If the likelihood of a single bit flip (uncorrected and undetected by the memory subsystem) is p, then what is the likelihood of a sequence of bit flips will produce a sorted array (that is, an array with the same elements as before, but now just in ordered sequence) relative to the likelihood of a different array.
    • Can you express an average M as a function of p and N?
    • Would your "algorithm" be faster if you instead of waiting for natural bit flips just inserted some random numbers here? Would that make sense?
    • Do you know what a standard sorting algorithm look like?
    • Can you see any qualitative difference between such an algorithm and what you are proposing?
    • Have you read up on Bogosort? Even that algorithm have an advantage over yours, can you see what?
     
  5. Dec 6, 2015 #4

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Thanks to @Filip Larsen (love the Tintin avatar) I now know what "natural bit flips" means.

    But then the "algorithm" is not even theoretically correct, as it will stop (if it stops) when the array is sorted.
    However, there is no reason to assume that the sorted array will be in any way connected to the original array (except for having the same length).
     
  6. Dec 6, 2015 #5
    That makes a lot of sense! Great idea.

    Code (Text):

    public static void Sort ( this List<T> L )
    {
        while ( !L.IsSorted() ) L.RearrageRandomly();
    }
     
     
  7. Dec 6, 2015 #6

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    That would make it a O(n*n!) "algorithm", I think.
     
  8. Dec 6, 2015 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Rearranging randomly is almost the worst possible sorting algorithm. The only thing worst would be something that maliciously un-sorts it. You need to add something that will actively put it in order.
     
  9. Dec 7, 2015 #8

    Svein

    User Avatar
    Science Advisor

    With modern memories and hardware error checks, your algorithm would not terminate as long as the machine it is running on is working.
     
  10. Dec 7, 2015 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    No, for two reasons. One is that this isn't a valid sorting algorithm. Secondly, this isn't an O(n) algorithm. It's O(n!), or worse.

    Thread closed.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Is this considered a valid sorting algorithm?
  1. Sorting algorithm? (Replies: 2)

Loading...