• fake armadillo (unregistered) in reply to bstorer
    bstorer:
    Mr Fred:
    I like the random sort algorithm better - take the data, put it in random order then check to see if it is sorted. If so then you are done.
    Many moons ago in school, the students in one of my classes were each given a different search or sort routines to implement and demonstrate to the rest of the class. I did the random sort, and, to demonstrate the sheer stupidity of such a sort, wrote a program to sort a deck of cards using it. Naturally, when I demonstrated it, it sorted it on the ninth pass, which was vastly superior to every other sort's performance. That was pretty comical.
    Do you mean "random sort" as Mr. Fred described it; shuffle the whole deck, then check the whole deck for being correctly ordered? If so, it's pretty astonishing that it finished at all, let alone that it found the correct ordering among 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 possibilities before the ninth pass. If I were you, I'd have taken up gambling after that!
  • (cs) in reply to Mr Fred
    Mr Fred:
    I like the random sort algorithm better - take the data, put it in random order then check to see if it is sorted. If so then you are done.

    That's actually the basis for the O(1) quantum sort algorithm. If it turns out that the "multiple parallel universes" theory is correct, then all you have to do to sort in O(1) is randomize with a quantum process, check the data, and if not sorted, destroy the universe.

    ...

    You know, that was much funnier before I thought of it in the context of this blog. I suggest we all make a pact to kill anyone who suggests that this be developed. Would you want to experience the debugging process on that one?

  • Matthew (unregistered) in reply to Mr Fred
    Mr Fred:
    I like the random sort algorithm better - take the data, put it in random order then check to see if it is sorted. If so then you are done.

    Nothing like O(rand(n)) efficiency!

  • Matthew (unregistered) in reply to CastrTroy
    CastrTroy:
    Using bubble sort can be a valid solution. First of all, if the number of items you are sorting is small, let's say, under 1000, then you're probably not going to find any reasonable difference in speed. Since the algorithm is for sorting entries in an RSS feed, it should be easily assumed that there aren't millions of entries. Also, using the built in sort functions usually requires that it knows how to compare your objects. In this case, it seems like the standard sort functions wouldn't understand the data, and the programmer would have to write a class that stored his data and then write the logic into the class for comparing the data. Sometimes using bubble sort is sufficiently fast, and less error prone, and at those times it's the right solution. Just like the rule of never using GoTos, it's not something you must absolutely do. Sometimes adding a single GoTo can greatly improve how readable the code is, while doing everything you can to avoid a goto can make code quite unreadable.

    I have never found an appropriate use for a GOTO outside of BASIC when I was 12. Really, there is no excuse for it. If you're using GOTOs, your functions are probably too long. Work on breaking it up into smaller chunks. Oh, and always use the built in sort functions. :-)

  • wth (unregistered)

    You all complain about O(n). A RSS feed ? OMG ?!! NO !!! 50 items !!! that will take like .... forever !!!!

  • mike (unregistered) in reply to phaedrus
    phaedrus:
    That's actually the basis for the O(1) quantum sort algorithm. If it turns out that the "multiple parallel universes" theory is correct, then all you have to do to sort in O(1) is randomize with a quantum process, check the data, and if not sorted, destroy the universe.

    The time taken to check if it is sorted would be O(n) :)

  • (cs) in reply to mike
    mike:
    phaedrus:
    That's actually the basis for the O(1) quantum sort algorithm. If it turns out that the "multiple parallel universes" theory is correct, then all you have to do to sort in O(1) is randomize with a quantum process, check the data, and if not sorted, destroy the universe.

    The time taken to check if it is sorted would be O(n) :)

    Oops. My bad. You're right. I wasn't a CS major, so I often @#$% up the big-O stuff.

    Anyway, I think I can sum up the main WTF with this: [image]

  • (cs)

    I worked on a program once where the lead developer coded his own bubble sort routine to sort, at most, 10 items. And on a class that already implemented ISortable.

    It then bypassed the bubble sort and took the classes position attribute and put it there in that array position. Needless to say it didn't handle a position of -1 too well.

    Same guy also had a profound dislike for collections (coz arrays are faster). The code was littered with redim preserve.....

  • O(Rubik) (unregistered)

    I coded an n cubed sort. I forgot what language I did it in. Though whatever language it was, it didn't have a built-in sort. I was in first year university. Fortunately it wasn't needed for a class, so I could sort of forget about it and dump it.

  • James (unregistered)

    OK, ignoring the fact that having arrays of strings is a really lousy way of storing data in a language like C# (object with named properties would be so much nicer, no?) ... here's some slightly modified code that does what he did:

    List<string[]> arrTotal;

    public int RssDateComparer( string[] a, string[] b ) { return DateTime.Parse(a).CompareTo(DateTime.Parse(b)); }

    And, here's how to call the sort:

    arrTotal.Sort( RssDateComparer );

    Sooooo much easier. So, yeah, NIH bites.

  • James (unregistered)

    Oops, that should be:

    return DateTime.Parse(a[2]).CompareTo(DateTime.Parse(b[2]));

    Of course, this makes ALL kinds of assumptions about the arrays having enough elements and that the date elements are actually valid and parsable. This is why one should really use objects with typed fields/properties rather than string arrays.

  • Nelle (unregistered) in reply to It's a Feature
    It's a Feature:
    CastrTroy:
    Using bubble sort can be a valid solution. First of all, if the number of items you are sorting is small, let's say, under 1000, then you're probably not going to find any reasonable difference in speed. Since the algorithm is for sorting entries in an RSS feed, it should be easily assumed that there aren't millions of entries. Also, using the built in sort functions usually requires that it knows how to compare your objects. In this case, it seems like the standard sort functions wouldn't understand the data, and the programmer would have to write a class that stored his data and then write the logic into the class for comparing the data. Sometimes using bubble sort is sufficiently fast, and less error prone, and at those times it's the right solution. Just like the rule of never using GoTos, it's not something you must absolutely do. Sometimes adding a single GoTo can greatly improve how readable the code is, while doing everything you can to avoid a goto can make code quite unreadable.

    Remind me never to hire you. Gotos NEVER make code more readable--it's just the opposite (unless you're talking some old legacy code where GOTO is the only way you can code it), and bubble sort is NEVER the best choice for sort.

    Read Linus Torwalds rant about GOTOs and remind me never to be hired by you ...

  • Michael (unregistered) in reply to bstorer

    A 52-card deck on the ninth pass? Liar.

  • lantastik (unregistered) in reply to O(Rubik)
    O(Rubik):
    I coded an n cubed sort. I forgot what language I did it in. Though whatever language it was, it didn't have a built-in sort. I was in first year university. Fortunately it wasn't needed for a class, so I could sort of forget about it and dump it.
    I'm sorry, but the formatting of this reply is a WTF.

    Misunderstanding of the whole Haiku concept? ...or did you pass a list of random words through the article's sort routine to generate this? In that case, take back my original statement, it's brilliant.

  • Beau "Porpus" Wilkinson (unregistered)

    The official MS.NET way to do this is obnoxious in its own right. If I remember correctly, you have to make an instantiable class that implements an interface, then pass an instance to a Sort method of the collection.

    In fact, I think one must make a custom instantiable class just to sort strings in descending order. Pretty obnoxious... it makes this WTF just a tiny bit more forgivable.

  • (cs)

    That code looks oddly familiar. I think I wrote something similar a few years ago. Go me.

  • (cs) in reply to It's a Feature
    It's a Feature:
    Remind me never to hire you. Gotos NEVER make code more readable--it's just the opposite (unless you're talking some old legacy code where GOTO is the only way you can code it), and bubble sort is NEVER the best choice for sort. Bubblesort serves no purpose other than as an academic experiment.

    GOTO is a tool. Like any tool it works when used properly. GOTOs can mkae code more readable. While any code can be written without GOTOs, sometimes it turns out being more complicated and less maintainable. YES there are times when a large function just can't be broken down, without turning it into a morass of funtion calls.

    For SMALL values of N, bubble sort makes perfect sense. (where N is generally less than 20) Bubble sort is EASY to write, and EASY to understand. Sometimes it is just easier to implement a quick bubble sort, than to write a comparator and use a built in sort.

    If you had three elements, and ONLY three elements. Lets say they aren't in a list... HOW do you sort them?

  • (cs) in reply to chrismcb
    chrismcb:
    GOTO is a tool. Like any tool it works when used properly. GOTOs can mkae code more readable. While any code can be written without GOTOs, sometimes it turns out being more complicated and less maintainable. YES there are times when a large function just can't be broken down, without turning it into a morass of funtion calls.

    For SMALL values of N, bubble sort makes perfect sense. (where N is generally less than 20) Bubble sort is EASY to write, and EASY to understand. Sometimes it is just easier to implement a quick bubble sort, than to write a comparator and use a built in sort.

    If you had three elements, and ONLY three elements. Lets say they aren't in a list... HOW do you sort them?

    Ok, I admit. I spent far too long working on this last night.

    Couldn't manage to do it with JUST min and max though.

    #include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) <= (b) ? (a) : (b))

void dotest (int *i)
{
  int o[3];

  o[0] = max(i[0], max(i[1], i[2]));
  o[2] = min(i[0], min(i[1], i[2]));

  if ((i[0] < o[0]) && (i[0] > o[2])) o[1] = i[0];
  if ((i[1] < o[0]) && (i[1] > o[2])) o[1] = i[1];
  if ((i[2] < o[0]) && (i[2] > o[2])) o[1] = i[2];

  printf("%d %d %d:", i[0], i[1], i[2]);
  printf("%d %d %d\n", o[0], o[1], o[2]);
}


int main()
{
  int i[3];

  i[0] = 10; i[1] = 20; i[2] = 30;
  dotest(i);

  i[0] = 30; i[1] = 20; i[2] = 10;
  dotest(i);
  
  i[0] = 20; i[1] = 10; i[2] = 30;
  dotest(i);
}

    (mmm... double-spaced code. Wonder how THAT is happening.)

  • Mosephus (unregistered) in reply to James

    Yay for reparsing both dates for every comparison, which is hugely more expensive than the comparison itself.

  • (cs) in reply to Beau "Porpus" Wilkinson

    No, the official way is to implement IComparable and add a compare function. The way you listed is for cases where you need multiple sorts.

    I'm pretty sure the string class implements IComparable.

  • sorted (unregistered)

    Compare every value to every other value even if its already in order, thats not how I do a bubble sort.

    Regarding Gotos, how would you get out of a double loop without convoluting your code with an extra procedure, variable or confusing condition.

    for(..) { for(..) { ... code ... if (condition) goto exitbothloops

    } }

    exitbothloops:

    ...

  • foo (unregistered) in reply to eelmonger

    Err...worst case for QuickSort is O(n^2). Best case and average case are O(n*log(n)).

    captcha: smile...cheese!

  • (cs) in reply to flukus
    flukus:
    No, the official way is to implement IComparable and add a compare function. The way you listed is for cases where you need multiple sorts.

    I'm pretty sure the string class implements IComparable.

    Surely not. I'm all in favour of incomparable strings.

    I also like blinking, me.

  • nano (unregistered)

    That second function deserves a good seeing to as well...

    private void Swap(int first) { arrTotal[first][0] %= (arrTotal[first + 1][0] % arrTotal[first][0]); arrTotal[first][1] %= (arrTotal[first + 1][1] % arrTotal[first][1]); arrTotal[first][2] %= (arrTotal[first + 1][2] % arrTotal[first][2]); arrTotal[first][3] %= (arrTotal[first + 1][3] % arrTotal[first][3]); }

    Pidgeot: Almost 50 comments, and no one has noticed that this wouldn't work anyway - BubbleSort operates on its parameter, while Swap operates on the instance variable - which is never set to the value of the parameter.
    Obviously you only ever call this function with the private member. Works fine like that.
  • Robin Wilton (unregistered)

    I heard they developed a similar routine for the Space Telescope. They called it the Hubble Bubble Sort Algorithm. Only trouble was, they couldn't work out whether to run it or smoke it.

  • Duncan (unregistered) in reply to It's a Feature
    It's a Feature:
    Remind me never to hire you. Gotos NEVER make code more readable--it's just the opposite (unless you're talking some old legacy code where GOTO is the only way you can code it)...

    If a language lacks a labeled break goto is often the clearest way to write some things. Knuth gives a good example somewhere, though I've forgotten exactly where. Goto can also be useful when building certain types of abstractions using a small set of primitives. For instance a lot of the iteration macros (dotimes, dolist, etc...) in Common Lisp are usually implemented in a subset of CL, and those implementations often use gotos.

  • JB (unregistered) in reply to sorted

    In a decent language like PHP, you just need to "break 2;".

  • anonymouse (unregistered)

    I keep hearing of this stupid bubble sort that everyone hates. I had no clue what the hell it was till I read this article.

    Why are people so damn stupid and lazy. Uh, lets not look up on the net the right way to do this. Lets use some F up code to make my life even harder cause I'm a tard.

  • anonymouse (unregistered) in reply to JB

    In a decent language like php! HAHAHAHAH

    try a generic list in C#, so easy, so far less to code, so safe.

    php sucks balls and is beyond its time.

  • Hognoxious (unregistered) in reply to too_many_usernames
    too_many_usernames:
    don't think we have any fun historical figures to correlate with clandestine copying and redistribution of information.
    Not really information, but how about Prometheus? And then there's King Midas' barber.
  • feizhuliu (unregistered)

Leave a comment on “Trouble Sort”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article