## bubble sort algorithm analysis

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.

 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.
 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.

## bubble sort algorithm analysis

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

 Quote by kadaj6 Code: 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.
 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.
 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. Code: 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.