- Thread starter
- #1

#### Joystar1977

##### Active member

- Jul 24, 2013

- 119

How many vcomparisons did you actually need?

- Thread starter Joystar1977
- Start date

- Thread starter
- #1

- Jul 24, 2013

- 119

How many vcomparisons did you actually need?

- Jan 30, 2012

- 2,492

n.How many vcomparisons did you actually need?

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.

- Thread starter
- #3

- Jul 24, 2013

- 119

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?

- Jan 30, 2012

- 2,492

Do you need to sort this sequence? You still have not said what v-comparisons are.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?

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.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?

- Thread starter
- #5

- Jul 24, 2013

- 119

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.

- Jan 30, 2012

- 2,492

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.d. What is the maximum number of comparisons required for a list of 6 numbers?

e. How many vcomparisons did I actually need?

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.