MATLAB Answers

Problems with averages and storing values

1 view (last 30 days)
Kyle Donk
Kyle Donk on 26 Jan 2020
Edited: per isakson on 27 Jan 2020
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.
Here is my code so far:
for X=[100:100:1000]
for num_trials=100;
for i=1:N-1
for j=1:N-i
if x(j)>x(j+1)
Y=[average1 average2 average3 average4 average5 average6 average7 average8 average9 average10];
Adam Danz
Adam Danz on 27 Jan 2020
If this code were within a function, you wouldn't need this line
Function workspace is more controlled than scripts. See this page for more info on functions vs scripts.

Sign in to comment.

Accepted Answer

Steven Lord
Steven Lord on 27 Jan 2020
Preallocate your Y vector. Keep track of the next element of Y to be filled and fill in that element each iteration through the loop.

More Answers (2)

Adam Danz
Adam Danz on 27 Jan 2020
Edited: Adam Danz on 27 Jan 2020
Advice & hints
  1. 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).
  2. The num_trials-loop only has 1 iteration. Is that intentional?
  3. N=length(x): you already know the length of x; you defined it on the previous line.
  4. count=count+1 : suppress output with semicolon.
  5. 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
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:
  1. create a script with four sections
  2. write a test for bubble_sort_()
  3. implement bubble_sort_() and test
  4. 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.)
  5. implement average_number_of_swaps_() and test
  6. 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 )
function [ num_vector, number_of_swaps ] = bubble_sort_( num_vector )
My result
Looks reasonable. Wiki says: Average performance O(n^2) swaps

Community Treasure Hunt

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

Start Hunting!