MHB When Bubble Sort to sort a list of numbers 7, 12, 5, 22, 13, 32

[Joystar77]

Can somebody tell me which example is right when a question that is given to me says to bubble sort a list of numbers 7, 12, 5, 22, 13, 32? I found two examples and one was with a graph that included Original List, Pass 1, Pass 2, Pass 3, Pass 4, Pass, 5, and Pass 6, the numbers with 7 on one line, 12 on another line, 5 on another line, 22 on another line, 13 on another line, and 32 on another line which includes Comparisons, and Swaps. The second example was to do the following:

First Pass:

(7, 12, 5, 22, 13, 32)- Here, algorithm compares the first two elements, and swaps since 7 <12.
(7, 12, 5, 22, 13, 32)- Swap since 12 > 5.
(7, 12, 5, 22, 13, 32)- Swap since 5 < 22.
(7, 12, 5, 22, 13, 32)- Swap since 22 > 13.
(7, 12, 5, 22, 13, 32)- Now, since these elements are already in order (32 > 13), algorithm does not swap them.

Second Pass and Third Pass is done the same way.

Can someone please tell me which example is correct when bubble sorting the list of numbers?

 

[Joystar77]

Discrete Mathematics (Bubble Sort to sort the list)

Is it true that the number 32 is definitely in its correct position at the end of the first pass when it comes to the following numbers: 7, 12, 5, 22, 13, 32?

 

[Joystar77]

Discrete Mathematics Numbers 7, 12, 5, 22, 13, 32

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

 

[Evgeny.Makarov]

Re: Discrete Mathematics Numbers 7, 12, 5, 22, 13, 32

Can somebody tell me which example is right when a question that is given to me says to bubble sort a list of numbers 7, 12, 5, 22, 13, 32? I found two examples and one was with a graph that included Original List, Pass 1, Pass 2, Pass 3, Pass 4, Pass, 5, and Pass 6, the numbers with 7 on one line, 12 on another line, 5 on another line, 22 on another line, 13 on another line, and 32 on another line which includes Comparisons, and Swaps. The second example was to do the following:

First Pass:

(7, 12, 5, 22, 13, 32)- Here, algorithm compares the first two elements, and swaps since 7 <12.
(7, 12, 5, 22, 13, 32)- Swap since 12 > 5.
(7, 12, 5, 22, 13, 32)- Swap since 5 < 22.
(7, 12, 5, 22, 13, 32)- Swap since 22 > 13.
(7, 12, 5, 22, 13, 32)- Now, since these elements are already in order (32 > 13), algorithm does not swap them.

Second Pass and Third Pass is done the same way.

Can someone please tell me which example is correct when bubble sorting the list of numbers?

I did not understand the description of the graph very well. The second example is incorrect. First, the swaps are not shown: all lines are the same. Second, if the sorting is done in increasing order, then there is no reason to swap 7 and 12: they are already ordered correctly.

The list during the first pass should change as follows. (Compared elements are underlined.)

\begin{array}{rrrrrr} \underline{7} &\underline{12}& 5& 22& 13& 32\\ 7& \underline{12}& \underline{5}& 22& 13& 32\\ 7& 5& \underline{12}& \underline{22}& 13& 32\\ 7& 5& 12& \underline{22}& \underline{13}& 32\\ 7& 5& 12& 13& \underline{22}& \underline{32}\\ 7& 5& 12& 13& 22& 32\end{array}

Is it true that the number 32 is definitely in its correct position at the end of the first pass when it comes to the following numbers: 7, 12, 5, 22, 13, 32?

Yes, if the sorting is done in increasing order.

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

In the unoptimized bubble sort, the number of comparisons is the same for all passes. In the optimized sort, the number decreases by 1 from one pass to the next because numbers at the end of the array are in their correct positions. Thus, for an array of $n$ numbers the first pass requires $n-1$ comparisons, the second $n-2$ comparisons, and so on.

 

[Joystar77]

Thank you Evgeny.Makarov! I seen two different examples of Bubble Sorting and was trying to see which is done correctly. I wanted to just clarify which one I am supposed to use when Bubble Sorting. Am I correct then that its easier to see things on a graph for Bubble Sorting such as having the Original List of numbers with 7 on one line, 12 on another line, 5 on another line, 22 on another line, 13 on another line, and 32on another line, Pass 1, Pass, 2, Pass 3, Pass 4, Pass 5, Pass 6, Comparisons, and Swaps? Just trying to get a thorough understanding of this.

 

[Evgeny.Makarov]

Am I correct then that its easier to see things on a graph for Bubble Sorting such as having the Original List of numbers with 7 on one line, 12 on another line, 5 on another line, 22 on another line, 13 on another line, and 32on another line, Pass 1, Pass, 2, Pass 3, Pass 4, Pass 5, Pass 6, Comparisons, and Swaps? Just trying to get a thorough understanding of this.

I am having trouble understanding this description of a graph, so I can't say whether it makes sense. Execution of Bubble sort can be illustrated in many ways. The most natural, I think, is to show the array after each comparison and potential swap. I showed the first pass in this way in my previous post. For another illustration, see Wikipedia. Note that while there are many ways to illustrate the execution of the Bubble sort, the algorithm itself works in a unique, fixed way. It is this way of working that is important, not whether it is illustrated as a graph or as a sequence of lines.

 

[Joystar77]

Thanks for the explanation Evgeny.Makarov!