• Anderson (unregistered)

    Would this runin O(n^n) time?

  • chris (unregistered)

    I admit to having done worse. I would state that it does not matter. Moreover, Big-O notation is important but does not take into account the bussiness-world-centric rules of development time vs runtime. If you know your datasets are smallish, a quick hack search with little development time is always better than a well thought out search that takes even just an hour or so longer.

    This is precisely why I left the world of business applications.

  • arty (unregistered)

    By my calculation, this will do 55 comparisons on a 5 element reverse-sorted list. Congratulations, you've "beaten" O(n^2) by getting a "higher score". You should be "proud". Even just inserting return after line 8 will save over half of this bad boy's run time.

  • Mike Dimmick (unregistered)

    Let's assume this is Java, C# or C++. In all three cases you have better sorts in the library. C# uses the .NET Base Class Library, where ArrayList and Array have Sort methods (for ArrayList it's an instance method but to sort an array you use Array.Sort).

    C++ inherits C's standard library, which contains qsort. If you're using standard C++ library container templates, you can use the sort<> or stable_sort<> template functions.

    Sorting is a problem that's solved. Reinventing it is ridiculous. Of course, you don't say what ListType is. Again, reinventing your own container is in general ridiculous - use a tested one from your environment's libraries. If you have some requirement that isn't met by the standard containers and algorithms, you need a seriously skilled person to write ones that meet the requirements.

  • Bob Dole (unregistered)

    What language is this, and is it pass by reference, or pass by value?

  • Alex Papadimoulis (unregistered)

    The language is C++.

  • Guayo (unregistered)

    What's wrong with this fine implementation of bogo sort?
    Anyway I have a better implementations that sometimes approach to 2n efficiency:

    void Ultimate1337Sort(ListType list)
    {
    Random rdm = new Random();
    for(int i = 0; i < (list.entries() - 1); i++)
    {
    if (rdm.nextInt(2) > 0)
    {
    list.swap(i, i+1);
    }
    }
    if (!list.isSorted())
    {
    Ultimate1337Sort(list);
    }
    }

  • fluffy (unregistered)

    Then there's always the joy of naive sorts in Prolog, which work by checking every possible permutation of the array and seeing which one is ordered. O(n!) time. Yay!

  • Name (unregistered)

    this looks worse than Bubble Sort. It doesn't just bubble down the newly swapped element, it does extra useless sorts at every step down.

    As the other poster suggested, often for small data sets it's perfectly reasonable to use O(n^2) algorithms if they're quick to implement. They can even be faster run time since they have very small code size and often very little setup time. Usually people use insertion sort or selection sort for such cases though.

  • Tim (unregistered)

    Yup, I've done pretty much the same thing :|

    But to my defence it was an academic exercise in learning haskell, which is a pure functional language (no loops!).

  • Thomas (unregistered)

    One thing to keep in mind there is that in languages where recursion is the only way to loop it tends to be very heavily optimized, and in fact tail recursion is often compiled/interpeted nearly exactly how a loop would be.

    C++ is not one of these languages.

    Before someone tries to argue that maybe the coder came from one of these languages, note the (inefficient) for loop.

  • Frijoles (unregistered)

    We need the specs, apparently.

  • Ron (unregistered)

    Actually the point that fluffy mentions sounds very well suited for quantum computing. (inspecting every permutation of a list and returning the sorted one)


    The nice thing about the sort in this post is it feels like it takes the typical nested for loops in a bubble sort and it explodes one of the for loops orthogonally, along the call stack. I think it's a neat bit of code.

  • josh (unregistered)

    Even if this were a language that optimizes tail recursion, there's no tail recursion here.

  • Mr. Pass By Value (unregistered)

    Uh. If this is C++, the list never gets sorted since it's passed by value (i.e. copied).
    Although seeing how McNasty this code is, the coder probably found a way to break that rule too.
    Lemme guess:
    class ListType {
    public:
    ...
    int operator;
    void swap(int,int);
    int entries();
    private:
    int* myStuff;
    }
    Hey, now I can just pass my list around without having to deal with ugly references! R0x0r!!

  • foxyshadis (unregistered)

    Maybe the spec was "Test all values after sorting to ensure sortedness on each iteration, just to make sure the changes really did go through after each return."

    I suppose there's a very tiny window where comparison is negligible compared to swapping, and the call stack is dynamically resizable, where this could be less than brain-dead. I'm not betting on it.

  • Centaur (unregistered)

    2Mr. Pass By Value:
    Congratulations, you’ve just invented the Smart Reference pattern.

  • Alain T&#233;sio (unregistered) 
        bool sortMe2(ListType list, int nbTries)


    {
    int nb;

    for (nb = 0; nb < nbTries; nb++)
    {

    int i1;
    int i2;

    i1 = new Random().Next(list.entries());
    i2 = new Random().Next(list.entries());

    if ((i1 > i2) != (list[i1] > list[i2]))
    {
    list.swap(i1, i2);
    return true;
    }

    }

    return false;

    }

    void sortMe(ListType list)
    {
    // If after (10 times the size list) lookups nothing was swapped
    // we can assume the list is sorted
    // You can put 100 here to be really safe
    while (sortMe2(list, 10 * list.entries())) { }
    }

  • Bart (unregistered)
    1. I'm pritty sure this isn't C++ This is C# or Java (no way to tell the difference) If this is C++ - this really would be the most serious WTF ever, and this guy should be shot on sight.


    2) There is a much better sort algorithm for doing such things:

    while(!list.isSorted()) { list.randomize(); }

    Much less code, so probably much faster!!! *grin*

    3) I think this guy has seen some kind of recursive quicksort algorithm and didn't know anymore how it exactly worked. He made something recursive, and messed around 'till something sorted came out... EUREKA!!! - implemented the quicksort!!! (or so he thought) - not as quick though... Maybe should give this a new name... The slowsort...

  • Warp (unregistered)

    If you know the amount of items to sort will always be very small (like a few tens of them), it's ok to use a O(n^2) algorithm, but why the heck must it always be bubblesort? And why the heck is it always taught as the first sorting algorithm?

    As said at the beginning of this page, bubblesort is one of the slowest O(n^2) sorting algorithms. Usually people advocate it for its simplicity. I don't understand why: Insertion sort is much simpler to understand (it resembles a lot more how people sort things in real life), practically equally simple to implement, and usually much faster (with less than 20 items it's probably the fastest existing sorting algorithm based on comparison of the items).

  • Christian (unregistered)

    The problem with saying that O(n^2) algorithms are okay for small data sets in business applications is the data sets never stays small. Before you know it, people are sorting 20K data points and cursing your name!

  • Sort this! (unregistered)
  • init6 (unregistered)

    Bah, datasets sometimes grow and you should ask about it before hand. Sometimes they don't and you don't worry about it. Often I just call Perl's sort() and don't worry about it. If things are too slow then I can look to optimize it.

    That said I've seen a webpage that made over 90,000 MySQL queries. It took nearly 10 minutes to load. The problem was stuff like:

    foreach( user_id ) {

    foreach( domain owned by user_id ) {

    foreach( month from start_of_time to now ) {
    // Note: start_of_time is when the system was
    // developed and not when the domain created

    $username = user_name_by_id_from_mysql();


    // tons more stuff cut out here that calculates
    // the account balance.
    }
    }
    }

    One user with two domain names when the system has run for 5 years involves 600 queries just looking up the username on the account!

    I still have a copy of the code but it's thousands of lines long and took days to trace through to find out why it was so slow so I don't plan on posting it.

  • Guayo (unregistered)

    @Bart
    Damn it! you stole my sorting algorithm!

    Note to self: Don't post great innovative code in the net before filling a patent.

  • WaveyDave (unregistered)

    It definitely isn't java - you can't access elements in any old list using the [i] notation - it has to be an array (which ListType isn't), so :
    if(list[i] > list[i+1])

    ...would not compile. It would have to do something like list.get(i).

  • (cs) in reply to Thomas
    Anonymous:

    One thing to keep in mind there is that in languages where recursion is the only way to loop it tends to be very heavily optimized, and in fact tail recursion is often compiled/interpeted nearly exactly how a loop would be.

    C++ is not one of these languages.

    Before someone tries to argue that maybe the coder came from one of these languages, note the (inefficient) for loop.

    Actually, it depends on the C++ compiler. The GNU compiler will optimize out tail recursion. Richard Stallman is a big lisp fan after all. Sadly, that isn't tail recursive since the loop continues on after the recursive call.

  • Rachel Blum (unregistered) in reply to chris

    Oy. Business rules or not, this is utterly stupid. Even a proper bubble sort is implemented in the same amount of dev. time.

    It does matter, even for biz apps - because this is a deeper indication of incompetence. Any programmer who wrote this should possibly consider working as administrative assistant instead.

  • Ahminus Glob (unregistered) in reply to chris
    chris:
    I admit to having done worse. I would state that it does not matter. Moreover, Big-O notation is important but does not take into account the bussiness-world-centric rules of development time vs runtime. If you know your datasets are smallish, a quick hack search with little development time is always better than a well thought out search that takes even just an hour or so longer.

    This is precisely why I left the world of business applications.

    And you'd be wrong. Even if you consulted no references, and did what every newbie programmer would do in the absence of any education for this, you'd code up a selection or an insertion sort, and it would take you less time to figure out and faster than this.

    Of course, you'd still be doing it wrong because you should just be using your languages qsort implementation anyways, which requires the least amount of time to code. And is much faster.

  • TheCPUWizard (unregistered)

    Why to people make the stupid assumption that "Big-O" has anything to do with actual time????

    It is simply a matter of measuring how a given item will scale.

    For examply an O(n!) where each element takes 10nS will be much faster than even an O(1) algroithm with a constant time of 10 seconds for a fairly large ranger of n.

  • (cs) in reply to TheCPUWizard
    TheCPUWizard:
    For examply an O(n!) where each element takes 10nS will be much faster than even an O(1) algroithm with a constant time of 10 seconds for a fairly large ranger of n.

    If you consider 1 through 9 a rather long range, as 10! is about 3.6 billion and thus would take 36 seconds, longer then your O(1) algorithm.

  • maderchod (unregistered)

    Oh boy, what a gem. This dummy managed to turn the already-inefficient O(n^2)-time, O(1)-space algorithm into an O(n^3)-time, O(n^2)-space one. Quite a genius innit.

Leave a comment on “HowBigIsMyCallStackSort()”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article