Thread Subject: BUBBLE SORT OPTIMIZATION

Hello guys, I am having a problem with bubble sort codes, and I would
appreciate it if you could help me with that.

The problem is that If we consider the bubble sort code bellow, we can
observe that if, for any k, no swops are performed by the inner for
loop, then the vector x is sorted. I know that we can use this
observation to code an improved algorithm, but I don't really know how
to do it in Matlab.

The reason why I need it in Matlab is to test it for computational
speed against the actual code for randomly chosen x. So it has to be
faster than the following code:

function y = bubble(x)

n = length(x);

for k = 1:n-1
  for j = 1:n-k
   if(x(j)> x(j+1))
    temp = x(j);
    x(j) = x(j+1);
    x(j+1) = temp;
   end % if
  end % for
end % for

y = x;

I would highly and greatly appreciate it if you could answer this
question.

Thanking you in advance and I am looking forward to hearing from you
soon.

Hi,

If you are purely interested in improving the performance of your sorting, I
would abandon bubble sort altogether in favor of a more sophisticated sort
algorithm. Bubble sort is very slow as far as sorting algorithms are
concerned: the time it takes to sort an array grows quadratically with the
size of the array you're trying to sort. Any incremental improvements you
make to your implementation will be trumped by the overall quadratic order
of the algorithm.

Instead, consider these two algorithms:
http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Mergesort
The improvement you see will be immediately noticable, especially for large
arrays.

Good luck,
Brian Cody
Senior Software Engineer
The MathWorks, Inc.

<adehkordi@gmail.com> wrote in message
news:d66fd73b-1221-42a4-9921-90584af15b3e@g38g2000yqd.googlegroups.com...
> Hello guys, I am having a problem with bubble sort codes, and I would
> appreciate it if you could help me with that.
>
> The problem is that If we consider the bubble sort code bellow, we can
> observe that if, for any k, no swops are performed by the inner for
> loop, then the vector x is sorted. I know that we can use this
> observation to code an improved algorithm, but I don't really know how
> to do it in Matlab.
>
> The reason why I need it in Matlab is to test it for computational
> speed against the actual code for randomly chosen x. So it has to be
> faster than the following code:
>
> function y = bubble(x)
>
> n = length(x);
>
> for k = 1:n-1
> for j = 1:n-k
> if(x(j)> x(j+1))
> temp = x(j);
> x(j) = x(j+1);
> x(j+1) = temp;
> end % if
> end % for
> end % for
>
> y = x;
>
> I would highly and greatly appreciate it if you could answer this
> question.
>
> Thanking you in advance and I am looking forward to hearing from you
> soon.

adehkordi@gmail.com wrote in message <d66fd73b-1221-42a4-9921-90584af15b3e@g38g2000yqd.googlegroups.com>...
> Hello guys, I am having a problem with bubble sort codes, and I would
> appreciate it if you could help me with that.
>
> The problem is that If we consider the bubble sort code bellow, we can
> observe that if, for any k, no swops are performed by the inner for
> loop, then the vector x is sorted. I know that we can use this
> observation to code an improved algorithm, but I don't really know how
> to do it in Matlab.
>
> The reason why I need it in Matlab is to test it for computational
> speed against the actual code for randomly chosen x. So it has to be
> faster than the following code:
>
> function y = bubble(x)
>
> n = length(x);
>
> for k = 1:n-1
> for j = 1:n-k
> if(x(j)> x(j+1))
> temp = x(j);
> x(j) = x(j+1);
> x(j+1) = temp;
> end % if
> end % for
> end % for
>
> y = x;
>
> I would highly and greatly appreciate it if you could answer this
> question.
>
> Thanking you in advance and I am looking forward to hearing from you
> soon.

Wrapper of: http://www.mathworks.com/matlabcentral/newsreader/view_thread/240506

adehkordi@gmail.com wrote:
> Hello guys, I am having a problem with bubble sort codes, and I would
> appreciate it if you could help me with that.

Your previous postings make it clear to any observant reader that the questions
you post now are homework questions -- phrased more politely, but still homework
questions. By failing to mention that here, you are misleading people as to your
goals in asking these questions.

If you have hopes of receiving a *useful* and *correct* reply, you had best
post a summary of what you have already done to solve these tasks.

> but I don't really know how to do it in Matlab.

But you do know how you would do it in some other computer language? Is Matlab
that much different from (say) C or Basic that you couldn't solve the
problem in a language you are more familiar with and then translate the
solution into Matlab? Or are you really saying that you really don't know
how to do this -period-, regardless of the computer language?

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

"Brian Cody" <bcody@mathworks.com> wrote in message <ghbi4b$m23$1@fred.mathworks.com>...
> Hi,
>
> If you are purely interested in improving the performance of your sorting, I
> would abandon bubble sort altogether in favor of a more sophisticated sort
> algorithm. Bubble sort is very slow as far as sorting algorithms are
> concerned: the time it takes to sort an array grows quadratically with the
> size of the array you're trying to sort. Any incremental improvements you

<snip>

I love the way Numerical Recipes (http://www.nrbook.com/a/bookcpdf/c8-0.pdf) expressed it:

"If you know what bubble sort is, wipe it from your mind; if you don't know, make a point of never finding out!"