I have been staring at this problem for an hour havent figured it out. Any help would be appreciated

Write a script to compare the respective times tq(n) and tb(n) that it takes to sort a random vector of length n as a function of n for n ranging from 1 to numbers as large as 100000 or more. Prepare a well labelled plot of the ratio of tb(n)/tq(n) versus n, where tb is time for the bubble sort and tq is the time for the quicksort employed by MATLAB. On the same plot, plot the ratio of the averages mean(tb(:))/mean(tq(:)) versus n.

Answer 1

[Star Strider]

Assuming you already know what the bubble sort algorithm is and have programmed it, and can use the MATLAB sort function, all you need then are the tic and toc functions (the timeit function is also a possibility) to do the timing.

For the vectors, use any of the random number functions: rand, randi, randn, or any of the others for your vector of numbers to be sorted. Obviously, use the same random number vector for both algorithms to do the comparison. I would use a loop to generate a new random number vector each time, do the timing of the two algorithms, and store the results, but there may be other methods.

[Seth]

How would you use the tic and toc functions to do the timing? I am still kind of confused

[Image Analyst]

startTime = tic
bubbleResults = BubbleFunction()
elapsedTimeBubble = toc(startTime)

startTime = tic
quickResults = QuickFunction()
elapsedTimeQuick = toc(startTime)

[Star Strider]

Thank you, IA. (I had a glitch and forced reboot a few minutes ago.)

Answer 2

[Seth]

Could you further elaborate on how to write a loop that generates a new random vector and then relating it to the timing functions? I am lost

[Star Strider]

I’ve been there myself.

There are probably a number of ways to do this.

This is one:

L = 250;                            % Length Of Random Vector
N = 100;                            % # Iterations
for k1 = 1:N
    rv = randi(100,1,L);
    tic                             % Start Timer
    qks = sort(rv);
    qst(k1) = toc;                  % Stop Timer, Record Quicksort Time
    tic
    bls = sin(log(rv));             % Insert Bubble Sort Call Here
    bst(k1) = toc;                  % Stop Timer, Record Bubblesort Time
end

I used a made-up function (that does no sorting) for the bubblesort call, to be certain the code works.

You may need to change the code to do your assignment, since your instructor may have specific requirements. Nevertheless, this should get you started.

[Seth]

Thank you so much

[Star Strider]

My pleasure!