Improving the bubblesort.

[her209]

Originally posted by: Matthias99
I already posted pseudocode for getting around this problem above. Maintain a sorted list rather than an array, so that if the new element is larger than everything already in the sorted list, it's O(1) to add it.

The best you can do with the added extra check is still 2n compares.

 

[her209]

Originally posted by: sao123
Improved BubbleSort Theory

The problem I have with this algorithm is in Case 2. It assumes that all numbers with index > X+1 are less than the smallest mth number. Here's an example where the algorithm would fail:

Given list: 12,34,44,134,456,23,122,313

It would see 456 on the first pass. But on the second pass, it would find 134 and not 313.

Unless I'm missing something?

 

[her209]

Originally posted by: her209
I think I may have found an even faster algorithm. I'm working on the pseudocode and will post it later.

Okay, the algorithm I got is picks m numbers from a list of n elements in

n + (m-1)(ceiling(log(base2) n)-1)

 

[sao123]

Originally posted by: her209

Originally posted by: sao123
Improved BubbleSort Theory

The problem I have with this algorithm is in Case 2. It assumes that all numbers with index > X+1 are less than the smallest mth number. Here's an example where the algorithm would fail:

Given list: 12,34,44,134,456,23,122,313

It would see 456 on the first pass. But on the second pass, it would find 134 and not 313.

Unless I'm missing something?

After the first pass... of course it would find the 456 first.
but the 313 is now guaranteed to be right next to where the 456 was... becasue it would bubble down to that spot until it finds the 456.
Therefore.... (most generic case) if the Next Largest number is anywhere in the array greater than index [x], after the first pass its index is guaranteed to be [x+1].

456,12,34,44,134,313,23,122
Thus on pass 2, I have saved you at least 2 compare and swaps. And will immediately find the 313 at x+1.

 

[sao123]

Havn't tried your code, but I took a look at it and it would require me to re-write it in the language that I'm using, and I'm too lazy to do that .

With the improved sort (shown above), my 1 million element array pops out the 10 largest elements in ~0.7s, and only makes 1 pass through the entire array.

Can you provide me with the array, and I will test it?

 

[Matthias99]

Originally posted by: her209

Originally posted by: Matthias99
I already posted pseudocode for getting around this problem above. Maintain a sorted list rather than an array, so that if the new element is larger than everything already in the sorted list, it's O(1) to add it.

The best you can do with the added extra check is still 2n compares.

If the array is in presorted order, it's only n compares (it will see that each item is either smaller than all items already seen, or larger than the largest item already seen, and both these cases are O(1) per item). In the general case, it is O(n*x), which I'm pretty sure is the best you can do on this problem (although maybe I'm missing some exotic data structure that would reduce this to O(n*logx) or something). You must look at each of the n numbers at least once if you use a comparison-based method, so the lower bound is at least O(n).

Okay, the algorithm I got is picks m numbers from a list of n elements in

n + (m-1)(ceiling(log(base2) n)-1)

You gonna tell us what it is, or do we have to guess?

Don't forget to count any data-structure-related overhead in your running time. You can't, for instance, insert a general item into a sorted array or list in O(1) time!

 

[SagaLore]

This algorith tracks the original position of the last moved item through a local variable.

By tracking - going through the extra routine, aren't you actually slowing down the algo?

I'm really really rusty on O notation and sorts so bear with me. What if you checked the leftmost bit to be true, and moved those into a new array. Then checked the next bit, and moved the true to another array. Do that until the last array has less than 10 numbers in it. Dump the last array and go back to the previous array, and then run your bubble sort and you've got your top ten.

 

[sao123]

Originally posted by: SagaLore

This algorith tracks the original position of the last moved item through a local variable.

By tracking - going through the extra routine, aren't you actually slowing down the algo?

I'm really really rusty on O notation and sorts so bear with me. What if you checked the leftmost bit to be true, and moved those into a new array. Then checked the next bit, and moved the true to another array. Do that until the last array has less than 10 numbers in it. Dump the last array and go back to the previous array, and then run your bubble sort and you've got your top ten.

Not sure what your getting at.
The O notation of an algorithm is used to describe the worst case run time of an algorithm. none of the optimizations I am proposing will do anything to change the O() of the bubblesort.
The reason that the bubblesort was picked for the task, was a 10 pass bubblesort should run in O(10n)->O(n) worst case.
What I am trying to accomplish is, see if there is anyway, the bubblesort could be improved to run faster (in nonWC scenerios), without changing fundamentally how it works.

By tracking - going through the extra routine, aren't you actually slowing down the algo?

There is a littleoverhead for determining if an optimization is present, but it is small compared to the potential yield gain. In an array of 1 million elements, I could eliminate Thousands or more of unnecessary compares. Which is where the speedup come from.
After all, its only a few lines of code, and 1 variable.

 

[Matthias99]

Originally posted by: SagaLore

This algorith tracks the original position of the last moved item through a local variable.

By tracking - going through the extra routine, aren't you actually slowing down the algo?

I'm really really rusty on O notation and sorts so bear with me. What if you checked the leftmost bit to be true, and moved those into a new array. Then checked the next bit, and moved the true to another array. Do that until the last array has less than 10 numbers in it. Dump the last array and go back to the previous array, and then run your bubble sort and you've got your top ten.

That's a variation on radix sort, a non-comparison-based method (although you still have a lot of operational overhead). This requires one (at most O(n)) pass for each comparable bit of the items (so if you are comparing 32-bit numbers, you need 32 passes, 64-bit numbers need 64 passes, etc.) If the values you are comparing are very small (for instance, they are only 8-bit numbers from 0-255), and the number of elements you need to sort is not ridiculously large, this can be very efficient. If you have to work on potentially very large values (or if you cannot easily map an integer to each element), this becomes infeasable.

Also, radix-sorting n k-bit integers requires at least O(2n) elements worth of storage in the worst cases. For a really, really large n, this gets difficult as well. At 10M elements you could probably do it, but at a few hundred times that size, you start having problems on normal computers.

Also, this approach generally fares badly on presorted or nearly-sorted lists, where comparison-based sorting (with a few optimizations) can get very close to O(n) runtime.

 

[blahblah99]

Originally posted by: her209

Originally posted by: blahblah99
The psuedocode goes something like this:

1. Create 10 element sorted array with initial values being 0.
2. Step through each element in the array.
3. If big array element[n] > last element in sorted array, replace last element in sorted array with element[n].
4. Re-sort 10 element array.
5. Repeat #2 until you go through all elements in the big array.

Actually for worst case scenario (the 1 million-element array is sorted in ascending order in this case), your algorithm would be very inefficient as every number would have to be added and sorted to 10-element array. I think I may have found an even faster algorith. I'm working on the pseudocode and will post it later.

While that may very well be true, for my application the elements in the array are guassian distributed... If it did appear as a sorted list in ascending order, the algorithm still does 1 pass through the entire array, with a million sorts on a 10 item array. Still a lot faster than a 10-iteration bubble sort on an array with 1 million elements. However, step #4 can be improved with a 1-iteration bubble sort on the 10 element array instead of running through 10 iterations, since that array will always be kept sorted.

I'll be interested to see your faster algorithm.

 

[complacent]

My question is, does everyone here really understand asymptotic notation? Remember, an algorithm that is O(n) simply means that given some constant, it is bounded above. You must always remember the constant, instead of just throwing out some notation and saying, "See, it grows slower than that one."

Second, your algorithm does something like the following:
1) Start sorting a list
2) At some point, there is a section that is sorted and does not need to be sorted or searched again

Doesn't this seem a lot like quicksort? Remember, quicksort picks a pivot element, puts it in place, and iteritvely does this until that section is sorted.

I'm sorry to tell you this folks, but there will never be a faster sort algorithm than n*lg(n) for two reasons: you must always look at every element in the list, and you must always search the list. It obviously takes n times to look at every element, and the fastest way to search a long list is by doing a binary search.