Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
BUBBLE SORT OPTIMIZATION

Subject: BUBBLE SORT OPTIMIZATION

From: adehkordi@gmail.com

Date: 5 Dec, 2008 15:03:19

Message: 1 of 5

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.

Subject: BUBBLE SORT OPTIMIZATION

From: Brian Cody

Date: 5 Dec, 2008 15:42:03

Message: 2 of 5

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.

Subject: BUBBLE SORT OPTIMIZATION

From: Tomasz Piech

Date: 5 Dec, 2008 16:13:02

Message: 3 of 5

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

Subject: BUBBLE SORT OPTIMIZATION

From: Walter Roberson

Date: 5 Dec, 2008 16:15:46

Message: 4 of 5

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)?

Subject: BUBBLE SORT OPTIMIZATION

From: Joerg Buchholz

Date: 5 Dec, 2008 16:51:02

Message: 5 of 5

"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!"

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us