Suggested languages for you:

Americas

Europe

Q8RE

Expert-verifiedFound in: Page 233

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**a.) Describe the bubble sort algorithm.**

** **

**b.) Use bubble sort algorithm to sort the list 2, 5, 1, 4, 3.**

** **

**c.) Give a big-** O** estimate for the number of comparisons used by the bubble sort.**

**a.) Bubble sort** interchanges consecutive integers if they are in the wrong order.

** **

B) 1, 2, 3, 4, 5

** **

c.) $O\left({n}^{2}\right)$

**a) Bubble sort interchanges consecutive integers if they are in wrong order.**

The sorting algorithm always moves from the left to the right through the list until the list is entirely sorted.

Note: On iteration of the algorithm, we know that the last i-1 elements are in the correct order.

b.) Given list: 5, 2, 4, 1, 3.

**First iteration** We compare the first two elements. The 5 needs to occur after the 2, thus the 5 needs to be inserted after the 2.

** **2, 5, 4, 1, 3

We compare the second and third elements. They are in the wrong order, thus they need to be interchanged.

2, 4, 5, 1, 3

We compare the third and fourth elements. They are in the wrong order, thus they need to be interchanged.

2, 4, 1, 5, 3

We compare the fourth and fifth elements. They are in wrong order, thus they need to be interchanged.

2, 4, 1, 3, 5

Note: Blue colored values are known to be in the correct position and thus no longer to be checked.

**Second iteration** We compare the first two elements. They are in the correct order, thus they do not need to be interchanged.

2, 4, 1, 3, 5

We compare the second and third elements. They are in wrong order, thus they need to be interchanged.

2, 1, 4, 3, 5

We compare the third and fourth elements. They are in wrong order, thus they need to be interchanged.

2, 1, 3, 4, 5

**Third iteration** We compare the first two elements. They are in wrong order, thus they need to be interchanged.

1, 2, 3, 4, 5

We compare the second and third elements.They are in the correct order, thus they do need to be interchanged.

1, 2, 3, 4, 5

**Fourth iteration** We compare the first two elements. They are in the correct order, thus the do not need to be interchanged.

1, 2, 3, 4, 5

Now we are confident that all elements are in the correct order, thus the algorithm stops.

c.) In the first iteration, *n-1* comparisons are made (as there are *n-1* consecutive pairs of elements).

In the second iteration, n-2 comparisons are made (as we already know that the last element is in the correct location).

In the third iteration, *n-3* comparisons are made (as we already know that the last two elements are in the correct location).

Thus in the *k* th iteration, *n-k* comparisons are made.

Note: when there are *n* elements in the list, then there are *n-1* iterations.

Adding all counts of comparisons, we then obtain:

$(n-1)+(n-2)+(n-3)+\dots .+(n-k)+\dots .+1\phantom{\rule{0ex}{0ex}}=\sum _{i=1}^{n-1}\u200a(n-i)\phantom{\rule{0ex}{0ex}}=\sum _{i=1}^{n-1}\u200an-\sum _{i=1}^{n-1}\u200ai$

** **

** **

Using $\sum _{k=1}^{n}\u200ak=\frac{n(n+1)}{2}$

**$=n\cdot \sum _{i=1}^{n-1}\u200a1-\frac{(n-1)n}{2}$ **

Using** ** $\sum _{k=1}^{n}\u200a1=n$

**$=n\cdot n-\frac{(n-1)n}{2}$ **

**$={n}^{2}-\frac{{n}^{2}-n}{2}\phantom{\rule{0ex}{0ex}}={n}^{2}-\frac{1}{2}{n}^{2}-\frac{1}{2}n\phantom{\rule{0ex}{0ex}}=\frac{1}{2}{n}^{2}-\frac{1}{2}n$ **

Then the number of comparisons is $=\frac{1}{2}{n}^{2}-\frac{1}{2}n$, which is $O\left({n}^{2}\right)$.

94% of StudySmarter users get better grades.

Sign up for free