Welcome to our community

Be a part of something great, join today!

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

Joystar1977

Active member
Jul 24, 2013
119
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?
 

Joystar1977

Active member
Jul 24, 2013
119
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?
 

Joystar1977

Active member
Jul 24, 2013
119
Discrete Mathematics Numbers 7, 12, 5, 22, 13, 32

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

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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.
 

Joystar1977

Active member
Jul 24, 2013
119
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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.
 

Joystar1977

Active member
Jul 24, 2013
119
Thanks for the explanation Evgeny.Makarov!