Register to reply

Bubble sort algorithm analysis

by kadaj6
Tags: algorithm, analysis, bubble, sort
Share this thread:
kadaj6
#1
Dec13-12, 02:47 PM
P: 31
Hello,

I need to analyze some bubble sort algorithm and calculate the probability of each conditional statements(if,for,while,ect...) be successful. I can post the algorithms if you need to see them.

Thanks in advance
Phys.Org News Partner Science news on Phys.org
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
jedishrfu
#2
Dec13-12, 03:25 PM
P: 2,930
We can't do this work for you but we could suggest how you might get the answers you need.

So show the algorithm and show how far you've gotten and what programming language you are using.
kadaj6
#3
Dec13-12, 04:10 PM
P: 31
function [S] = bubblesortWMemSe(X)
% Bubble sort implementation with memory and Stop Early
len = length(X);
S=X;
% t0=tic;
sorted = false;
last=1;
while (~sorted)
sorted = true;

for i=last:len-1
if S(i) > S(i+1)
tmp = S(i);
S(i) = S(i+1);
S(i+1) = tmp;
sorted = false;
last=i;
break
end
end
end
% t1=toc;
% runtime = t0-t1;





function [S] = bubblesortWMem(X)
% Bubble sort implementation with memory
len = length(X);
S=X;
% t0=tic;
sorted = false;
last=1;
while (~sorted)
sorted = true;

for i=last:len-1
if S(i) > S(i+1)
tmp = S(i);
S(i) = S(i+1);
S(i+1) = tmp;
sorted = false;
last=i;
end
end
end
% t1=toc;
% runtime = t0-t1;




function [S] = bubblesortSE(X)
% Bubble sort implementation with Stop Early
len = length(X);
S=X;
% t0=tic;
sorted = false;
while (~sorted)
sorted = true;
for i=1:len-1
if S(i) > S(i+1)
tmp = S(i);
S(i) = S(i+1);
S(i+1) = tmp;
sorted = false;
break
end
end
end
% t1=toc;
% runtime = t0-t1;



function [S] = bubblesort(X)
% Bubble sort implementation
len = length(X);
S=X;
% t0=tic;
sorted = false;
while (~sorted)
sorted = true;
for i=1:len-1
if S(i) > S(i+1)
tmp = S(i);
S(i) = S(i+1);
S(i+1) = tmp;
sorted = false;
end
end
end
% t1=toc;
% runtime = t0-t1;





i made a table with the amount of comparison ans assignments for each one, now i need the probability of each while,if, and for to be successful. I do not know how to do it.

jedishrfu
#4
Dec13-12, 04:50 PM
P: 2,930
Bubble sort algorithm analysis

reformatting for readability using [ CODE ] [ /CODE ] tags (Mod: omit extra spaces)

Quote Quote by kadaj6 View Post
function [S] = bubblesortWMemSe(X)
% Bubble sort implementation with memory and Stop Early
len = length(X);
S=X;
% t0=tic;
sorted = false;
last=1;
while (~sorted)
    sorted = true;
    
    for i=last:len-1
        if S(i) > S(i+1)
            tmp = S(i);
            S(i) = S(i+1);
            S(i+1) = tmp;
            sorted = false;
            last=i;
            break
        end
    end
end
% t1=toc;
% runtime = t0-t1;





function [S] = bubblesortWMem(X)
% Bubble sort implementation with memory
len = length(X);
S=X;
% t0=tic;
sorted = false;
last=1;
while (~sorted)
    sorted = true;
    
    for i=last:len-1
        if S(i) > S(i+1)
            tmp = S(i);
            S(i) = S(i+1);
            S(i+1) = tmp;
            sorted = false;
            last=i;
        end
    end
end
% t1=toc;
% runtime = t0-t1;




function [S] = bubblesortSE(X)
% Bubble sort implementation with Stop Early
len = length(X);
S=X;
% t0=tic;
sorted = false;
while (~sorted)
    sorted = true;
    for i=1:len-1
        if S(i) > S(i+1)
            tmp = S(i);
            S(i) = S(i+1);
            S(i+1) = tmp;
            sorted = false;
            break
        end
    end
end
% t1=toc;
% runtime = t0-t1;



function [S] = bubblesort(X)
% Bubble sort implementation
len = length(X);
S=X;
% t0=tic;
sorted = false;
while (~sorted)
    sorted = true;
    for i=1:len-1
        if S(i) > S(i+1)
            tmp = S(i);
            S(i) = S(i+1);
            S(i+1) = tmp;
            sorted = false;
        end
    end
end
% t1=toc;
% runtime = t0-t1;



i made a table with the amount of comparison ans assignments for each one, now i need the probability of each while,if, and for to be successful. I do not know how to do it.
jedishrfu
#5
Dec13-12, 04:56 PM
P: 2,930
Im not sure how to do this but I'd probably look at the if and think about my data

say Im sorting numbers 1 thru 5 but the are listed 5 thru 1

then your if will fire every time on the first pass on the second pass it depends.

now say I'm sorting 1 thru 5 but they are in order

then your if will never fire

Do you have some fixed data?

Another approach would be to insert counters in your code for each time the IF fired and for how many passes you make until the end is reached then print out the two numbers during each pass and at the end.
justsomeguy
#6
Dec13-12, 05:29 PM
P: 166
Sounds like someone wants you to basically calculate the O() (big-O) notation for your sort. We will take a look at the last one, the straight bubble sort.

function [S] = bubblesort(X)
% Bubble sort implementation
len = length(X);
S=X;
% t0=tic;
sorted = false;
while (~sorted)
  sorted = true;
  for i=1:len-1
    if S(i) > S(i+1)
      tmp = S(i);
      S(i) = S(i+1);
      S(i+1) = tmp;
      sorted = false;
    end
  end
end
% t1=toc;
% runtime = t0-t1;
You're going to have two answers, though generally we're only ever interested in the worst case.

In the best case, X is given to the function presorted. If this is the case, then your if statement is never going to be true. How many times then will it be executed? Wil sorted ever be set back to false after you set it to true?

In the worst case, X is given in reverse order. When that happens, how many items need to be moved, and how many places do they need to be moved? After 1 iteration how many items will be in the right location? After 2? After n?

A third answer is the average case, or random case, which for functions like bubblesort, is much closer to the worst case than the best case.


Register to reply

Related Discussions
Bubble-sort algorithm Engineering, Comp Sci, & Technology Homework 3
C Bubble sort help Engineering, Comp Sci, & Technology Homework 8
Analysis of the Binary Insertion Sort algorithm Engineering, Comp Sci, & Technology Homework 0
Bubble Sort Math & Science Software 5
Urgent help need Bubble sort Programming & Computer Science 3