Discrete Mathematics Vcomparisons

[Joystar1977]

How many vcomparisons did you actually need?

 

[Evgeny.Makarov]

How many vcomparisons did you actually need?

n.

Do you seriously believe one can answer this question without knowing the context, in particular, what v-comparisons are? This is not a universally accepted term in discrete mathematics, as far as I know.

 

[Joystar1977]

I will rephrase the question Evgeny. Makarov. When having the following numbers: 7, 12, 5, 22, 13, and 32 how many vcomparisons did I actually need?

Is it true that 12 vcomparisons is what I would actually need. If this is not correct, then can you explain this to me? I have a learning disability and so its hard for me to grasp the concepts and understand the material at times.

Another question I have when having the following numbers: 7, 12, 5, 22, 13, and 32 what is the maximum number of comparisons required for a list of 6 numbers?

The maximum number of comparisons required for a list of 6 numbers would be 5 comparisons. If this is not correct, then can you please explain this to me?

 

[Evgeny.Makarov]

I will rephrase the question Evgeny. Makarov. When having the following numbers: 7, 12, 5, 22, 13, and 32 how many vcomparisons did I actually need?

Do you need to sort this sequence? You still have not said what v-comparisons are.

As a general advice, you should ask questions in such a way that individual threads are self-contained. One thread should not require a context from a different thread. If you do rely on another thread, you should post a link there. Even if two threads were asked at the same time, after several replies they may be separated by other threads in the list of recent posts, so it is is no longer obvious that they may be related. Also, different threads may be read by different people. I believe this is a rule not just on this forum.

Another question I have when having the following numbers: 7, 12, 5, 22, 13, and 32 what is the maximum number of comparisons required for a list of 6 numbers?

The maximum number of comparisons required for a list of 6 numbers would be 5 comparisons. If this is not correct, then can you please explain this to me?

I believe this question is being discussed in this thread.

 

[Joystar1977]

Oh, I did not understand you Evgeny.Makarov. I was just rephrasing the question because this is a term that my instructor apparently uses in Discrete Mathematics. You said that it wasn't an appropriate term used in Discrete Mathematics. There are 5 questions listed under my assignment for Question 1 and it goes through like this as follows:

Use Bubble Sort to sort the list: 7, 12, 5, 22, 13, 32

a. Which number is definitely in its correct position at the end of the first pass?

b. How does the number of comparisons required change as the pass number increases?

c. How does the algorithm know when the list is sorted?

d. What is the maximum number of comparisons required for a list of 6 numbers?

e. How many vcomparisons did I actually need?

I am trying to figure out what the vcomparisons are also.

Sincerely,

Joystar1977

Do you need to sort this sequence? You still have not said what v-comparisons are.

As a general advice, you should ask questions in such a way that individual threads are self-contained. One thread should not require a context from a different thread. If you do rely on another thread, you should post a link there. Even if two threads were asked at the same time, after several replies they may be separated by other threads in the list of recent posts, so it is is no longer obvious that they may be related. Also, different threads may be read by different people. I believe this is a rule not just on this forum.

I believe this question is being discussed in this thread.

 

[Evgeny.Makarov]

d. What is the maximum number of comparisons required for a list of 6 numbers?

e. How many vcomparisons did I actually need?

This may be a typo. The question may ask for the actual number of comparisons for this concrete list as opposed to the the maximum number of comparisons over all lists of 6 numbers.

First you need to figure out the details of the algorithm: whether the number of comparisons decreases from pass to pass or not. The fact is that after the first pass, the largest number is at the end of the array, and there is no use of comparing it. Therefore, the second pass may use $n-2$ comparisons instead of $n-1$ for the first pass, and the number of comparisons may decrease by 1 with each pass. However, there is no harm in making these extra comparisons.

Thus, in the unoptimized version of the algorithm, each pass makes $n-1$ comparisons for an array of $n$ numbers. In the optimized version, which you seem to have, there are $n-1$ comparisons for the first pass, $n-2$ for the second pass, and so on. Therefore, the maximum total number of comparosins is $(n-1)+(n-2)+\dots+1=n(n-1)/2$ (the sum of an arithmetic progression). For an actual list, the algorithm may discover sooner that the list is sorted, and the number of comparisons may be smaller.