1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bubble sort algorithm analysis

  1. Dec 13, 2012 #1
    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. jcsd
  3. Dec 13, 2012 #2

    jedishrfu

    Staff: Mentor

    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.
     
  4. Dec 13, 2012 #3
    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.
     
  5. Dec 13, 2012 #4

    jedishrfu

    Staff: Mentor

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

     
    Last edited by a moderator: Dec 13, 2012
  6. Dec 13, 2012 #5

    jedishrfu

    Staff: Mentor

    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.
     
  7. Dec 13, 2012 #6
    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 (Text):

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Bubble sort algorithm analysis
  1. C Bubble sort help (Replies: 8)

  2. Bubble-sort algorithm (Replies: 3)

Loading...