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.
Joystar1977 said:
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.
Joystar1977 said:
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.
Joystar1977 said:
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.
Joystar1977 said:
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.
Joystar1977 said:
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.
Joystar1977 said:
The maximum number of swaps/comparisons is a quadratic function. Is it correct to say that the algorithm has quadratic order?
Quadratic complexity.
Joystar1977 said:
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.
