How to Analyze Bubble Sort Algorithm Efficiency?

[kadaj6]

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

 

[jedishrfu]

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]

function = 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 = 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 = 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 = 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]

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

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]

Im not sure how to do this but I'd probably look at the if and think about my data

say I am 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]

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.