 Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q8RE

Expert-verified Found in: Page 233 ### Discrete Mathematics and its Applications

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)$

See the step by step solution

## Step 1: a.) Describe the bubble sort algorithm.

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.

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

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.

## Step 3

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

## Step 4

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

## Step 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.

## Step 6 c.) Give a big-  estimate for the number of comparisons used by the bubble sort.

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:

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

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

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

## Step 7

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

$=n\cdot n-\frac{\left(n-1\right)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)$. ### Want to see more solutions like these? 