Comment On Trouble Sort

I find it appropriate that the Multi Array Bubble Sort acronym, MABS, sounds similar to the expletive that the Coneheads are always shouting....

Very appropriate for production code...

Captcha: dubya ... my hero...

guitaristx:

I find it appropriate that the Multi Array Bubble Sort acronym, MABS, sounds similar to the expletive that the Coneheads are always shouting....

Next thing you know he'll invent the Table Bubble Sorting system.

And no, I don't understand what I'm saying.

Nothing wrong with this. In the next release they can replace it with some sane built-in sort algorithm and claim 470% (or similar) performance improvement.

Imagine if he tried to use something more complicated than a bubble sort! *shudders*

qoou ʇsǝıqoou ǝɥʇ:

Next thing you know he'll invent the Table Bubble Sorting system.

And no, I don't understand what I'm saying.

Well, I do. Here are the steps:
1) program prints out values on cards;
2) program notifies operator;
3) operator puts cards on table, a wooden table of course;
4) operator sorts the cards in the right order;
5) operator takes a picture of the sorted cards with a digital camera and uploads it to the computer; (note the huge performance improvement here, compared to about 10 years ago, because the operator doesn't have to go to the photo shop, and scan the returned photographs)
6) program reads the values from the picture with an OCR program;
7) program can proceed with what it is doing.

That Code almost blinded me when i saw it. If i If i woud try to understand swap, my sight woud be gobe.

CAPTCHA: quake (FOREVER)

aaaah!! my eyes my eyes!!!

You had me at:

private string[][] arrTotal;

public void BubbleSort(string[][] arrTotal)

Simply brilliant... maybe he won a prize for improving the performance in the next version... ;)

Setting the thread culture is a nice touch! It just wouldn't feel like an authentic bubble sort without some weird side effects.

private string[][] arrTotal;

Ye'll be usin' built-in sort routines or ye'll be walkin' the plank!

Ninjas would have stolen some code off the internet.

Call me back when he implements a Multi Array Merge Sort. That might have enough square brackets in it to kill us all!

I believe there's nothing multidimensional about the sort, only that the array is containing an array with the rss stuff and the date/time stored in separate cells.

The question I have why there is a local field "arrTotal" which isn't used in the function.

In my opinion it's just a regular bubble sort. The only thing is that the array that is sorted contains elements of type array containing the rss stuff and the date/time in separate cells.

Manuel:

I believe there's nothing multidimensional about the sort, only that the array is containing an array with the rss stuff and the date/time stored in separate cells.

The question I have why there is a local field "arrTotal" which isn't used in the function.

It is used in the Swap function, so I guess you have to pass the field arrTotal as argument to the BubbleSort function for this to work (if it works at all, my eyes hurt too when I try to read this stuff).

Here's a sort I use in my project somewhere. edi gets an array of pointers to stuff and esi gets an array of integers, one per pointer. Both arrays get sorted according to the esi array...

.sort:;(edi = Types, esi = Levels, eax = Low, ebx = High)

	cmp eax, ebx

	jl .nontrivial

	ret

.nontrivial:

	push eax

	push ebx

	mov ecx, [esi + 4 * eax + 4]

	push dword [edi + 4 * eax]

	mov edx, [esi + 4 * ebx + 4]

	push dword [edi + 4 * ebx]

.sortloop:

	cmp edx, ecx

	jae .above

.below:

	pop dword [edi + 4 * eax]

	mov [esi + 4 * eax + 4], edx

	inc eax

	cmp eax, ebx

	je .finish

	push dword [edi + 4 * eax]

	mov edx, [esi + 4 * eax + 4]

	jmp .sortloop

.above:

	pop dword [edi + 4 * ebx]

	mov [esi + 4 * ebx + 4], edx

	dec ebx

	cmp eax, ebx

	je .finish

	push dword [edi + 4 * ebx]

	mov edx, [esi + 4 * ebx + 4]

	jmp .sortloop

.finish

	pop dword [edi + 4 * ebx]

	mov [esi + 4 * ebx + 4], ecx

	pop ebx

	push eax

	inc eax

	call .sort

	pop ebx

	sub ebx, byte 2

	pop eax

	jmp .sort

and no, I didn't remove the comments on purpose, there never was any.

The declarations are so naively generic and the implementation so full of assumptions, it is hard to say who took the first wrong step: the architect or the programmer?

Most likely they both share the same brain.

Manuel:

In my opinion it's just a regular bubble sort. The only thing is that the array that is sorted contains elements of type array containing the rss stuff and the date/time in separate cells.

Forgive if I'm missing the sarcasm, I haven't finished my morning coffee yet. But ... "just a regular bubble sort ..."?

I don't know C#, but I'm guessing it has some kind of semi-efficient sorting built in. If you're going to reinvent something, don't use the most inefficient method (eg. bubble sort for sorting) of doing so.

The gem for me is how he's clearly aware of potential localization problems, but instead of using the culture's IFormatProvider, which would have taken one extra line, he forces the entire thread's culture to en-US, potentially causing all kinds of mayhem down the road.

Yes, I know the sorting algorithm is far worse, but that part was just depressing. The localization nonsense was funny.

guitaristx:

I find it appropriate that the Multi Array Bubble Sort acronym, MABS, sounds similar to the expletive that the Coneheads are always shouting....

It also sounds like the sometimes-evil Queen Mab, which seems appropriate.

bobday:

Setting the thread culture is a nice touch! It just wouldn't feel like an authentic bubble sort without some weird side effects.

I bet he did that so Convert.ToDateTime() returns a string in the format he wants--much easier than simply calling DateTime.Parse() and specifying the desired culture/format.

Manuel:

In my opinion it's just a regular bubble sort. The only thing is that the array that is sorted contains elements of type array containing the rss stuff and the date/time in separate cells.

Hmm ... just that it always does length*length passes, even if the array is already sorted.
As for the Swap() function: :x

You're assuming there was an architect involved, and it wasn't the "programmer" reinventing the wheel!

Evil Overlord's:

private string[][] arrTotal;

Ye'll be usin' built-in sort routines or ye'll be walkin' the plank!

Ninjas would have stolen some code off the internet.

Wait, stealing off the internet is clearly piracy, not ninjitsu.

Paul:

I don't know C#, but I'm guessing it has some kind of semi-efficient sorting built in. If you're going to reinvent something, don't use the most inefficient method (eg. bubble sort for sorting) of doing so.

They probably couldn't work out how to sort a multidimensional array of items by the 3rd item in each 'row'

I don't know C# that well either, but in something like C++ it would need the next level of ability up to be able to use sort(..., predicate) as opposed to just sort(...). So, they may well have known the built-in sort function, just not how to apply to their slightly harder problem.

But, I suppose, even if you don't know that, there are more efficient tricks (eg create a single dimensional array of strings which are '<ISO-dates>:<arrayindex>', sort those using the built-in sort, and then build a new array using the array index parts of the strings).

AT:

bobday:

Setting the thread culture is a nice touch! It just wouldn't feel like an authentic bubble sort without some weird side effects.

I bet he did that so Convert.ToDateTime() returns a string in the format he wants--much easier than simply calling DateTime.Parse() and specifying the desired culture/format.

Yes, it's pretty clear why he did it.

I really hope to God you're being sarcastic when you call it "much easier," but the sinking feeling in the pit of my stomach suggests otherwise.

bstorer:

Evil Overlord's:

private string[][] arrTotal;

Ye'll be usin' built-in sort routines or ye'll be walkin' the plank!

Ninjas would have stolen some code off the internet.

Wait, stealing off the internet is clearly piracy, not ninjitsu.

I don't think it's piracy, actually; Pirates generally did not make copies for redistribution. They just took things intended for one party and used them for their own gain.

I don't think we have any fun historical figures to correlate with clandestine copying and redistribution of information. The closest thing I can think of it monks, because for a while they were the only people who made copies of anything. But somehow 'software and music monks' doesn't have the same flair to it as 'pirates'.

(Software and modern music 'piracy' is an interesting side effect of the fact that the end product is also the instruction for duplicating the end product.)

pscs:

Paul:

I don't know C#, but I'm guessing it has some kind of semi-efficient sorting built in. If you're going to reinvent something, don't use the most inefficient method (eg. bubble sort for sorting) of doing so.

They probably couldn't work out how to sort a multidimensional array of items by the 3rd item in each 'row'

I don't know C# that well either, but in something like C++ it would need the next level of ability up to be able to use sort(..., predicate) as opposed to just sort(...). So, they may well have known the built-in sort function, just not how to apply to their slightly harder problem.

But, I suppose, even if you don't know that, there are more efficient tricks (eg create a single dimensional array of strings which are '<ISO-dates>:<arrayindex>', sort those using the built-in sort, and then build a new array using the array index parts of the strings).

C# has quicksort built in to most collection classes, and really easy methods of heap-sorting.

All built-in sorting methods will default to the IComparable interface of the class being sorted. However, they also have overloads that take a separate IComparer-compliant class as a parameter (this takes the place of the predicate).

Paul:

I don't know C#, but I'm guessing it has some kind of semi-efficient sorting built in. If you're going to reinvent something, don't use the most inefficient method (eg. bubble sort for sorting) of doing so.

Bubble sorts can be quite fast, if not efficient, for small values of N. I've used them occasionally in the past, before .NET and built in sorting, for quick and simple sorts. I never had to do anything lengthy enough to really get to know the O of bubbles sorts.

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.

Perhaps this guy is actually doing something intelligent by using bubble sort. Bubble sort can approach O(n) runtime if the list is already sorted, and depending on how and when the RSS feeds are being collected and sorted, there's a chance that they are pretty close to being in the right order anyways. If you used the built in stuff (which is quicksort based) on data that's mostly sorted you'd approach the worst case of O(n lg n) for quicksort.

Of course it's easier just to say "Bubble sort, no!!!!!"

too_many_usernames:

bstorer:

Evil Overlord's:

private string[][] arrTotal;

Ye'll be usin' built-in sort routines or ye'll be walkin' the plank!

Ninjas would have stolen some code off the internet.

Wait, stealing off the internet is clearly piracy, not ninjitsu.

I don't think it's piracy, actually; Pirates generally did not make copies for redistribution. They just took things intended for one party and used them for their own gain.

I don't think we have any fun historical figures to correlate with clandestine copying and redistribution of information. The closest thing I can think of it monks, because for a while they were the only people who made copies of anything. But somehow 'software and music monks' doesn't have the same flair to it as 'pirates'.

(Software and modern music 'piracy' is an interesting side effect of the fact that the end product is also the instruction for duplicating the end product.)

Way to overanalyze a throwaway joke.

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.

Brady Kelly:

Paul:

I don't know C#, but I'm guessing it has some kind of semi-efficient sorting built in. If you're going to reinvent something, don't use the most inefficient method (eg. bubble sort for sorting) of doing so.

Bubble sorts can be quite fast, if not efficient, for small values of N. I've used them occasionally in the past, before .NET and built in sorting, for quick and simple sorts. I never had to do anything lengthy enough to really get to know the O of bubbles sorts.

The value of N for which bubblesort is faster than (say) quicksort is probably around <=15, but it is easier to write.
The real problem is the "not invented here" syndrome, the efficiency of the code probably doesn't matter.

Without more information on the context this method was used in, it is impossible to determine if it is actually a WTF.

time0ut:

Without more information on the context this method was used in, it is impossible to determine if it is actually a WTF.

Apply that recursively (context of the context of the context...), and suddenly nothing can be a WTF for sure!

Nothing can be a WTF
No thing can be a WTF
pzzzz

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. Bubblesort serves no purpose other than as an academic experiment.

And, by the way, this code has high potential of not doing anything but eat CPU. The test for moving data is done with the local array, but the global array, of the same name, is where the data is changed. The only way this would work is if the global array is passed into the call--so what's the point of making it a parameter on the call?

It's a Feature:

Remind me never to hire you. Gotos NEVER make code more readable--it's just the opposite

Depends on what you're doing. I can't imagine writing a lot of kernel or driver code without using goto.

There are circumstances where an O(n^2) sort is likely to be faster than an O(n lg n) sort (as several folks have said, any n less than about 100 is probably a win), but there's virtually never a circumstance where that sort should be Bubble sort. Cache locality issues aside (and if you're using a quadratic sort then all your data may fit in one line anyway), insertion sort will literally always do less work than bubble sort, and it's not substantially more complicated to code either. Bubble sort comes with a clever built-in visualization that makes it good for teaching, but that's about it.

I like the random sort method. But I prefer lazy sort: check whether the first three values are already in order, and return successfully. Otherwise throw an exception.
When I call the method and the exception is thrown, I catch it but ignore it, just so things don't break apart.

It's a Feature:

bubble sort is NEVER the best choice for sort. Bubblesort serves no purpose other than as an academic experiment.

Maybe never with small letters, but not NEVER with big letters.
If the entropy of the incoming data is low enough, a bubble sort will be O(n).

It's not even an optimized bubble sort!

after each pass, the pass'th largest elements have "bubbled" to the top.

Still O(n^2) but with smaller constants.

for (int pass = 1; pass < arrTotal.Length; pass++ )
{
for (int i = 0; i < arrTotal.Length - pass; i++ ) <--FIX
{
if ( Convert.ToDateTime(arrTotal[i][2])
< Convert.ToDateTime(arrTotal[i + 1][2]) )
Swap(i);
}
}

Er . . . why is he using an array of arrays when it could simply be an array of objects, and be much, much shorter.

private rssData[] arrTotal;



public void BubbleSort(rssData[] arrTotal)

{

  for (int pass = 1; pass < arrTotal.Length; pass++ )

  {

    for (int i = 0; i < arrTotal.Length - 1; i++ )

    {

      if ( arrTotal[i].getDate()

	       < arrTotal[i + 1].getDate() )

        Swap(i);

    }

  }

}



private void Swap(int first)

{

  rssData hold = arrTotal[first];

  arrTotal[first] = arrTotal[first + 1]

  arrTotal[first + 1] = hold;

}

Another problem is that it always takes O(N^2) comparisons, even if the list is already sorted; it needs few break statements.

private rssData[] arrTotal;



public void BubbleSort(rssData[] arrTotal)

{

  int not_sorted = 1;

  for (int pass = 1; pass < arrTotal.Length && not_sorted == 1; pass++ )

  {

    not_sorted = 0;

    for (int i = 0; i < arrTotal.Length - 1; i++ )

    {

      if ( arrTotal[i].getDate()

	       < arrTotal[i + 1].getDate() )

      {

        Swap(i);

        not_sorted = 1;

      }

    }

  }

}



private void Swap(int first)

{

  hold = arrTotal[first];

  arrTotal[first] = arrTotal[first + 1]

  arrTotal[first + 1] = hold;

}

Aah! The goggles! They do nothing!

Bubble sort can approach O(n) runtime if the list is already sorted

Not in this implementation. He needs to, at least, add a bool testing whether any swap was detected on a pass, and early-out if none were. Or, perhaps more appropriately, call a system-defined Quicksort, Merge sort or Radix sort routine.

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.

AT:

I bet he did that so Convert.ToDateTime() returns a string in the format he wants--much easier than simply calling DateTime.Parse() and specifying the desired culture/format.

It was done for efficiency's sake.

I wonder what reheap would look like in a heap sort

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.

That's kind of funny, in hischool we were given a bonus assignment to make a magic square solver. The user had to specify how many columns there were, and then the application would output a valid magic square.
What I did was made it so it would generate a random matrix grid from 1 to n and then check to see if it was a magic square (making sure all columns, and rows equal to the same amount) if it wasn't, it would through away the grid and create a new one and compare again.

For small grids (3 or 4 columns) it was relatively quick, but for an experiment I let it run all weekend for a 9 column grid (I think, might have been more or less), I can't remember the exact result, but I believe it ran a couple hundred million times or so before finding a valid magic square
After that experiment I made the real application using the correct algorithm that would generate one instantly. Everyone else in the class was dumb with trying to figure out how to make it, only myself and 1 other finished the bonus assignment, because we were the only ones smart enough to look on the internet for the magic square algorithm.

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.