How many comparisons does this algorithm make?

Question

0.00/5 (No votes)

See more:

I've come across an examination question with the algorithm below in pseudo code. The questions asks: "How many comparisons are made if n is equal 10?"

Algorithm sort
Declare A(1 to n)
n = length(A)
for i = 1 to n
    for j = 1 to n-1 inclusive do
        if A[i-1] > A[i] then
swap( A[i-1], A[i] )
        end if
    next j
next i

What I have tried:

Quote:
The marking scheme says it's 100 but I think this is wrong and think it's 90. What are people's opinions?

Posted 8-Nov-18 1:01am

Member 14048071

Updated 8-Nov-18 1:28am

Add a Solution

Comments

CPallini 8-Nov-18 8:23am

Are you aware that A[i-1] is an out-of-bounds access when i = 1 ?

Member 14048071 8-Nov-18 10:55am

Would it be out of bounds? I think it would be 0? Therefore accessing the first element of the array.

CPallini 8-Nov-18 16:37pm

The first element of the array is A[1], because of Declare A(1 to n).

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2018-11-08T01:13:00

Solution 1

You are right, it does 90 comparisons if n is 10.
(assuming 'inclusive' applies to both the loops).

Posted 8-Nov-18 1:13am

CPallini

OriginalGriff · Answer 2 · 2018-11-08T01:29:00

Solution 2

Depends, you could get 72, 80, 81, or 90. But probably not 100.
Simple way to find out: try it!

C#

int n = 10;
int count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 72
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 80
count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 81
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 90

Myself? Given that one of your loops is specific about "inclusive" and the other isn't I'd go with 81 ...

Posted 8-Nov-18 1:29am

OriginalGriff

Comments

Rob Philpott 8-Nov-18 8:33am

Yeah, the inclusive bit is weird isn't it. One assumes it means the higher bound of the array, but it could refer to the lower of both. And starting at 1 sounds like the sort of thing a 'VB Person' would do. Oh dear.

OriginalGriff 8-Nov-18 8:47am

I always think that loops start at an inclusive lower bound (or else, why specify "i = 1" or "j = 1"?)
But the inclusion of "inclusive" on one loop does sort of exclude the other ... badly designed. Could well be VB :laugh:

Member 14048071 8-Nov-18 9:11am

I think that's what's throwing me. I think it was written by a VB programmer.

Member 14048071 8-Nov-18 10:58am

Also this is meant to be a bubble sort and I think i and j are mixed up. With the inner loop you'd be checking the same values over and over.

OriginalGriff 8-Nov-18 11:03am

It's all a bit crap, really ... :laugh:

Member 14048071 8-Nov-18 11:04am

This is official documentation from an examining board.

OriginalGriff 8-Nov-18 11:08am

Doesn;t stop it being a bit crap though, does it? :)