2 views (last 30 days)

Show older comments

For a school project, I have to estimate the average number of swaps required to sort a random list of numbers. I have to do this for X equals 100 to 1000 in steps of 100. The problem is that all of my averages equal the same thing because I am not saving the average in Y. I also have to store those averages in Y before the code loops back through. I have been trying to get past this point for several days and just cannot figure out how to get average to be the average for X=100,200,300, and so forth and so on. Any guidance would be greatly appreciated.

THIS IS A SCHOOL ASSIGNMENT, SO PLEASE NO COMPLETE ANSWERS TO THIS. THANK YOU.

Here is my code so far:

count=0;

for X=[100:100:1000]

num_of_trials=[];

for num_trials=100;

x=randi([1,999],101,1);

N=length(x)

for i=1:N-1

for j=1:N-i

if x(j)>x(j+1)

temp=x(j);

x(j+1)=x(i);

x(j+1)=temp;

count=count+1

end

end

average=count/100;

end

end

end

Y=[average1 average2 average3 average4 average5 average6 average7 average8 average9 average10];

Steven Lord
on 27 Jan 2020

Adam Danz
on 27 Jan 2020

Edited: Adam Danz
on 27 Jan 2020

Advice & hints

- Smart-indent your code for better readability (I already applied correct indentation to the code in your question). Select all of the code (ctrl+a) and smart indent (ctrl+i).
- The num_trials-loop only has 1 iteration. Is that intentional?
- N=length(x): you already know the length of x; you defined it on the previous line.
- count=count+1 : suppress output with semicolon.
- average=count/100; This is where you should store the values. However, your nested loops are complex and you need a way to know which total iteration you're on. One way of doing that is to create another variable like your count variable that merely counts the total number of iterations that pass through this line (by the way, there are 1000 of them). This method is generally sloppy and a sign of inefficiency but there are too many other changes that I'd need to suggest in order to implement a better way to count the total number of iterations.

There are other inefficiencies in the code but this short list are my advice with minimal change to your logic.

per isakson
on 27 Jan 2020

Edited: per isakson
on 27 Jan 2020

I like to present a different approach, which includes

- divide the projects into steps
- use Code Sections
- use functions
- use descriptive names

There are many ways to divide the project. I think the two function, bubble_sort_() and average_number_of_swaps_() make good sense. The latter calls the former. I get the following steps:

- create a script with four sections
- write a test for bubble_sort_()
- implement bubble_sort_() and test
- write a test for average_number_of_swaps_(). That's more difficult than I thought. (Time to rethink average_number_of_swaps_ ? Not this time.)
- implement average_number_of_swaps_() and test
- implement the School Project main and run it

My script with four sections

A peek into my script

%% Test bubble_sort_()

random_vector = randperm(6); % easy to inspect and small enough to fit in a tooltip

[ sorted_vector, ~ ] = bubble_sort_( random_vector );

assert( issorted( sorted_vector ), 'The vector returned by bubble_sort_ isn''t sorted' )

%

test_vector = [ 12, 1:11 ];

[ ~, number_of_swaps ] = bubble_sort_( test_vector );

assert( number_of_swaps==11,'The number_of_swaps returned by bubble_sort_ isn''t correct')

%% Test average_number_of_swaps_()

average = average_number_of_swaps_( 100 );

% Not so easy to assert anything meaningful

assert( average>=0 && not(isnan(average)) ...

, 'average_number_of_swaps_() returns illegal number' )

%% School project main

vector_length_list = 100:100:1000;

...

plot( average_list, 'd' );

%% Local functions

function average = average_number_of_swaps_( vector_length )

...

end

function [ num_vector, number_of_swaps ] = bubble_sort_( num_vector )

...

end

My result

Looks reasonable. Wiki says: Average performance O(n^2) swaps

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!