In this section, we consider the application of the brute-force approach to the problem of sorting: given a list of n orderable items (e.g., numbers, characters from some alphabet, character strings), rearrange them in nondecreasing order.

**Selection
Sort and Bubble Sort**

In this
section, we consider the application of the brute-force approach to the problem
of sorting: given a list of ** n**
orderable items (e.g., numbers, characters from some alphabet, character
strings), rearrange them in nondecreasing order. As we mentioned in Section
1.3, dozens of algorithms have been developed for solving this very important
problem. You might have learned several of them in the past. If you have, try
to forget them for the time being and look at the problem afresh.

Now,
after your mind is unburdened of previous knowledge of sorting algorithms, ask
yourself a question: “What would be the most straightforward method for solving
the sorting problem?” Reasonable people may disagree on the answer to this
question. The two algorithms discussed here—selection sort and bubble sort—seem
to be the two prime candidates.

We start
selection sort by scanning the entire given list to find its smallest element
and exchange it with the first element, putting the smallest element in its
final position in the sorted list. Then we scan the list, starting with the
second element, to find the smallest among the last ** n** − 1 elements and exchange it with
the second element, putting the second smallest element in its final position.
Generally, on the

After ** n** − 1
passes, the list is sorted.

Here is
pseudocode of this algorithm, which, for simplicity, assumes that the list is
implemented as an array:

**ALGORITHM** *SelectionSort*** (A**[0

//Sorts a
given array by selection sort

//Input:
An array ** A**[0..

*min *←* **i*

**for ***j*** **←** ***i*** **+** **1** to ***n*** **−** **1** do**

**if **** A**[

As an
example, the action of the algorithm on the list 89** ,** 45

The
analysis of selection sort is straightforward. The input size is given by the
number of elements ** n**; the
basic operation is the key comparison

**FIGURE 3.1
**Example of sorting with selection sort. Each
line corresponds to one** **iteration of
the algorithm, i.e., a pass through the list’s tail to the right of the
vertical bar; an element in bold indicates the smallest element found. Elements
to the left of the vertical bar are in their final positions and are not
considered in this and subsequent iterations.

Since we
have already encountered the last sum in analyzing the algorithm of Example 2 in
Section 2.3, you should be able to compute it now on your own. Whether you
compute this sum by distributing the summation symbol or by immediately getting
the sum of decreasing integers, the answer, of course, must be the same:

Thus,
selection sort is a * (n*^{2}** )** algorithm on all inputs. Note,
however, that the number of key swaps is only

**Bubble
Sort**

Another
brute-force application to the sorting problem is to compare adjacent elements
of the list and exchange them if they are out of order. By doing it repeatedly,
we end up “bubbling up” the largest element to the last position on the list.
The next pass bubbles up the second largest element, and so on, until after ** n** − 1 passes
the list is sorted. Pass

Here is
pseudocode of this algorithm.

**ALGORITHM** *BubbleSort*** (A**[0

//Sorts a
given array by bubble sort

//Input:
An array ** A**[0..

**for ***j*** **←** **0** to ***n*** **−** **2** **−** ***i*** do**

**if **** A**[

The
action of the algorithm on the list 89** ,** 45

The
number of key comparisons for the bubble-sort version given above is the same
for all arrays of size ** n**; it is
obtained by a sum that is almost identical to the sum for selection sort:

**FIGURE 3.2
**First two passes of bubble sort on the list** **89*,*** **45*,*** **68*,*** **90*,*** **29*,*** **34*,*** **17. A new** **line is shown after a
swap of two elements is done. The elements to the right of the vertical bar are
in their final positions and are not considered in subsequent iterations of the
algorithm.

The
number of key swaps, however, depends on the input. In the worst case of
decreasing arrays, it is the same as the number of key comparisons:

As is
often the case with an application of the brute-force strategy, the first
version of an algorithm obtained can often be improved upon with a modest
amount of effort. Specifically, we can improve the crude version of bubble sort
given above by exploiting the following observation: if a pass through the list
makes no exchanges, the list has been sorted and we can stop the algorithm
(Problem 12a in this section’s exercises). Though the new version runs faster
on some inputs, it is still in * (n*^{2}** )** in the worst and average cases.
In fact, even among elementary sorting methods, bubble sort is an inferior
choice, and if it were not for its catchy name, you would probably have never
heard of it. However, the general lesson you just learned is important and
worth repeating:

A first
application of the brute-force approach often results in an algorithm that can
be improved with a modest amount of effort.

1. **a. **Give an example of an algorithm
that should not be considered an appli-cation of the brute-force approach.

** **b. Give an example of a problem that cannot be solved
by a brute-force algorithm.

** **2. **a. **What is
the time efficiency of the brute-force algorithm for computing** **** a^{n}
**as a
function of

** **b. If you are to compute ** a^{n}** mod

** **3. For each of the algorithms in Problems 4, 5, and 6
of Exercises 2.3, tell whether or not the algorithm is based on the brute-force
approach.

**
****a. **Design a brute-force algorithm
for computing the value of a polynomial

at a
given point *x*_{0} and
determine its worst-case efficiency class.

** **b. **
**If the algorithm you designed is in * (n*^{2}** ),** design a linear algorithm for
this problem.

** **c. Is it possible to design an algorithm with a
better-than-linear efficiency for this problem?

5. A network
topology specifies how computers, printers, and other devices are connected
over a network. The figure below illustrates three common topologies of networks:
the ring, the star, and the fully connected mesh.

You are
given a boolean matrix ** A**[0

6. *Tetromino tilings *Tetrominoes
are tiles made of four 1* *×* *1
squares. There* *are five types of
tetrominoes shown below:

** **7. *A stack
of fake coins *There are* **n** *stacks of* **n** *identical-looking coins. All of* *the coins in one of these stacks are
counterfeit, while all the coins in the other stacks are genuine. Every genuine
coin weighs 10 grams; every fake weighs 11 grams. You have an analytical scale
that can determine the exact weight of any number of coins.

**
**Devise a brute-force algorithm to identify the
stack with the fake coins and determine its worst-case efficiency class.

**
**What is the minimum number of weighings needed to
identify the stack with the fake coins?

** **8. Sort the list ** E,
X, A, M, P , L, E** in alphabetical order by selection sort.

** **9. Is selection sort stable? (The definition of a
stable sorting algorithm was given in Section 1.3.)

** **10. Is it possible to implement selection sort for
linked lists with the same * (n*^{2}** )** efficiency as the array version?

** **11. Sort the list ** E,
X, A, M, P , L, E** in alphabetical order by bubble sort.

** **12. **a. **Prove
that if bubble sort makes no exchanges on its pass through a list, the** **list is sorted and the algorithm can
be stopped.

** **b. Write pseudocode of the method that incorporates
this improvement.

** **c. Prove that the worst-case efficiency of the
improved version is quadratic.

** **13. Is bubble sort stable?

** **14 . *Alternating
disks *You have a row of 2*n** *disks of two colors,* **n** *dark and* **n** *light.* *They alternate: dark, light, dark,
light, and so on. You want to get all the dark disks to the right-hand end, and
all the light disks to the left-hand end. The only moves you are allowed to make
are those that interchange the positions of two neighboring disks.

Design an
algorithm for solving this puzzle and determine the number of moves it takes.
[Gar99] Brute Force and Exhaustive Search

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Brute Force and Exhaustive Search : Selection Sort and Bubble Sort |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.