Maximum number of comparisons required for a list of 6 numbers

[Joystar77]

The question asks me as follows: "What is the maximum number of comparisons required for a list of 6 numbers?

Is the correct answer as follows: The maximum number of comparisons required for a list of 6 numbers is 5 comparisons. If this is not right, then can somebody please help and explain this to me?

 

[Evgeny.Makarov]

The question asks me as follows: "What is the maximum number of comparisons required for a list of 6 numbers?

Required to do what with a list of 6 numbers? Please write the complete question. Is it about sorting? If so, then is it about some concrete algorithm or the minimum over all algorithms (of maxima over all 6-number lists)? Finally, it would be nice if you provided a reason for your answer so that it can be checked.

 

[Joystar77]

Hello Evgeny.Makarov! The complete question is as follows:

Use Bubble Sort to sort the list 7, 12, 5, 22, 13, and 32. What is the maximum number of comparisons required for a list of 6 numbers?

Is the maximum number of comparisons required for a list of 6 numbers 5 comparisons? If this is not correct, then can somebody please explain this to me?

 

[Evgeny.Makarov]

Use Bubble Sort to sort the list 7, 12, 5, 22, 13, and 32. What is the maximum number of comparisons required for a list of 6 numbers?

Is the maximum number of comparisons required for a list of 6 numbers 5 comparisons? If this is not correct, then can somebody please explain this to me?

One requires 5 comparisons only for one pass. I suggest you sort the list 6, 5, 4, 3, 2, 1 in ascending order and note how many comparisons you used.

 

[Joystar77]

Evgeny.Makarov- Let me understand this correctly each time there is a pass then one of the numbers requires 5 comparisons. Is this true or false? Each step is called a pass through the algorithm. The steps are repeated until no swaps take place in a pass. If there are n numbers in the original list, then n-1 comparisons are needed in the 1st pass, n-2 comparisons are needed on the 2nd pass, n-3 comparisons are needed on the 3rd pass, n-4 comparisons are needed on the 4th pass, n-5 comparisons are needed on the 5th pass, and n-6 comparisons are needed on the 6th pass. If the maximum number of passes is needed, the total number of comparisons will be:

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = 1/2 (n-1)n

Another question is this true or false:

The maximum number of swaps required is also 1/2 (n-1)n. This maximum number of swaps takes place if the original list of numbers were written in reverse order. The maximum number of swaps/comparisons is a quadratic function. Is it correct to say that the algorithm has quadratic order?

When you say ascending order do you mean to switch around the numbers or just put them in order from smallest to largest or largest to smallest. For example:

1, 2, 3, 4, 5, 6

6, 5, 4, 3, 2, 1

1 3 2 4 5 6

2 1 3 4 5 6

3 2 1 4 5 6

I am still trying to get the hang of this. Please let me know whether or not I am on the right track.
Joystar1977

One requires 5 comparisons only for one pass. I suggest you sort the list 6, 5, 4, 3, 2, 1 in ascending order and note how many comparisons you used.

 

[Evgeny.Makarov]

First of all, you need to determine which version of bubble sort you are using. The best thing would be if you just posted your version between the [code]...[/code] tags.

In another thread, there was a question how the algorithm knows when the array is finally sorted and when it is time to stop. You answered that it takes a whole pass without swaps to determine that the array is sorted. This is true for the unoptimized version of the algorithm, which goes to the end of the array and makes the same number of comparisons during every pass. In contrast, an optimized algorithm uses the fact that after the first pass, the last number is in its correct place, after the second pass the last two numbers are in their correct places and so on. So, the optimized algorithm does not go to the end of the array in subsequent passes and makes fewer and fewer comparisons with each new pass. This algorithm recognizes the time to stop when it has to make an empty pass. You can see the code for the two version in Wikipedia. Below I assume that you have an optimized algorithm.

each time there is a pass then one of the numbers requires 5 comparisons. Is this true or false?

False. Your claim implies that there is a single number that is compared 5 times. In fact, the algorithm compares adjacent pairs of array elements: first and second, second and third, and so on. Due to swapping, one of the numbers in each pair comes from the previous pair, so it may indeed happen that one of the numbers in every pair is the same. However, the algorithm may also compare new numbers, not encountered before during that pass.

If an array has 6 elements, then the first pass makes 5 comparisons since there are 5 adjacent pairs: from first and second to fifth and sixth.

Each step is called a pass through the algorithm.

I am not sure if this is your definition of the word "step", a definition of the word "pass", or a claim that uses existing meanings of these words. No, I would not say that a pass is a step. The algorithm makes one pass as it goes through the whole array from the beginning to the end. We can define the word "step" in different ways, but I would say that a step is smaller: it is a comparison or swapping of two numbers, an increase of the counter and so on. Thus, one pass consists of many steps.

The steps are repeated until no swaps take place in a pass.

This depends on the details of the algorithm. Here you agree that a pass consists of several steps.

If there are n numbers in the original list, then n-1 comparisons are needed in the 1st pass, n-2 comparisons are needed on the 2nd pass, n-3 comparisons are needed on the 3rd pass, n-4 comparisons are needed on the 4th pass, n-5 comparisons are needed on the 5th pass, and n-6 comparisons are needed on the 6th pass. If the maximum number of passes is needed, the total number of comparisons will be:

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 = 1/2 (n-1)n

I agree with regard to the optimized algorithm.

Another question is this true or false:

The maximum number of swaps required is also 1/2 (n-1)n. This maximum number of swaps takes place if the original list of numbers were written in reverse order.

Yes.

The maximum number of swaps/comparisons is a quadratic function. Is it correct to say that the algorithm has quadratic order?

Quadratic complexity.

When you say ascending order do you mean to switch around the numbers or just put them in order from smallest to largest or largest to smallest. For example:

1, 2, 3, 4, 5, 6

6, 5, 4, 3, 2, 1

1 3 2 4 5 6

2 1 3 4 5 6

3 2 1 4 5 6

An array is sorted in ascending order when the numbers go from smallest to largest.

 

[Joystar77]

If I put the numbers in ascending order as you mentioned earlier:

6, 5, 4, 3, 2, 1

In Ascending Order (smallest to largest) would be as follows:

1 2 3 4 5 6

So if I have the following numbers:

7, 12, 5, 22, 13, 32

In Ascending Order (smallest to largest) would be as follows:

5 7 12 13 22 32

Would I have to go through and do a second pass and third pass? I am going off an example that I found on Wikipedia. It says after the second pass before starting up on the third pass as follows: "now the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Is this true or correct?

 

[Evgeny.Makarov]

This is true for the unoptimized algorithm.

 

[Joystar77]

Thanks Evgeny.Makarov!