Register to reply 
Bubble sort algorithm analysis 
Share this thread: 
#1
Dec1312, 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 


#2
Dec1312, 03:25 PM

P: 2,777

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. 


#3
Dec1312, 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:len1 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 = t0t1; 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:len1 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 = t0t1; 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:len1 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 = t0t1; function [S] = bubblesort(X) % Bubble sort implementation len = length(X); S=X; % t0=tic; sorted = false; while (~sorted) sorted = true; for i=1:len1 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 = t0t1; 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. 


#4
Dec1312, 04:50 PM

P: 2,777

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



#5
Dec1312, 04:56 PM

P: 2,777

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. 


#6
Dec1312, 05:29 PM

P: 166

Sounds like someone wants you to basically calculate the O() (bigO) notation for your sort. We will take a look at the last one, the straight bubble sort.
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  
Bubblesort 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 