As a first example of applying the input-enhancement technique, we discuss its application to the sorting problem. One rather obvious idea is to count, for each element of a list to be sorted, the total number of elements smaller than this element and record the results in a table.

**Sorting by Counting**

As a first example of
applying the input-enhancement technique, we discuss its application to the
sorting problem. One rather obvious idea is to count, for each element of a
list to be sorted, the total number of elements smaller than this element and
record the results in a table. These numbers will indicate the positions of the
elements in the sorted list: e.g., if the count is 10 for some element, it
should be in the 11th position (with index 10, if we start counting with 0) in
the sorted array. Thus, we will be able to sort the list by simply copying its
elements to their appropriate positions in a new, sorted list. This algorithm
is called ** comparison-counting sort **(Figure 7.1).

**ALGORITHM** *ComparisonCountingSort*** (A**[0

//Sorts an array by
comparison counting

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

//Output: Array ** S**[0

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

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

**if **** A**[

** Count**[

**for ***i*** **←** **0** to ***n*** **−** **1** do **** S**[

What is the time efficiency
of this algorithm? It should be quadratic because the algorithm considers all
the different pairs of an ** n**-element array. More
formally, the number of times its basic operation, the comparison

Thus, the algorithm makes the
same number of key comparisons as selection sort and in addition uses a linear
amount of extra space. On the positive side, the algorithm makes the minimum
number of key moves possible, placing each of them directly in their final
position in a sorted array.

The counting idea does work
productively in a situation in which elements to be sorted belong to a known
small set of values. Assume, for example, that we have to sort a list whose
values can be either 1 or 2. Rather than applying a general sorting algorithm,
we should be able to take advantage of this additional information about values
to be sorted. Indeed, we can scan the list to compute the number of 1’s and the
number of 2’s in it and then, on the second pass, simply make the appropriate
number of the first elements equal to 1 and the remaining elements equal to 2.
More generally, if element values are integers between some lower bound ** l** and upper bound

Let us consider a more
realistic situation of sorting a list of items with some other information
associated with their keys so that we cannot overwrite the list’s elements.
Then we can copy elements into a new array ** S**[0

**EXAMPLE** Consider sorting the array

whose values are known to
come from the set {11** ,** 12

Note that the distribution
values indicate the proper positions for the last occur-rences of their
elements in the final sorted array. If we index array positions from 0 to ** n** − 1

It is more convenient to
process the input array right to left. For the example, the last element is 12,
and, since its distribution value is 4, we place this 12 in position 4 − 1 = 3 of the array ** S** that will hold the sorted list. Then we
decrease the 12’s distribution value by 1 and proceed to the next (from the
right) element in the given array. The entire processing of this example is
depicted in Figure 7.2.

Here is pseudocode of this
algorithm.

**ALGORITHM** *DistributionCountingSort*** (A**[0

//Sorts an array of integers
from a limited range by distribution counting //Input: An array ** A**[0

**for ***j*** **←** **1** to ***u*** **−** ***l*** do **** D**[

**for ***i*** **←** ***n*** **−** **1** downto **0** do**

** j **←

** S**[

** D**[

**return ***S*

Assuming that the range of
array values is fixed, this is obviously a linear algorithm because it makes
just two consecutive passes through its input array ** A**. This is a better time-efficiency class than
that of the most efficient sorting

**
**Is it possible to exchange numeric values of two variables, say, ** u** and

**
**Will the comparison-counting algorithm work correctly for arrays
with equal values?

Assuming that the set of possible
list values is {*a, b, c, d*}, sort the
following list in alphabetical order by the distribution-counting algorithm:

**
**Is the distribution-counting algorithm stable?

**
**Design a one-line algorithm for sorting any array of size ** n** whose values are

**
**The ** ancestry problem** asks to determine whether a vertex

**
**The following technique, known as ** virtual initialization**,
provides a time-efficient way to initialize just some elements of a given array

**
**Sketch the state of arrays ** A**[0

**
**In general, how can we check with this scheme whether ** A**[

**
***Least distance sorting *There are 10 Egyptian stone
statues standing in a row* *in an art
gallery hall. A new curator wants to move them so that the statues are ordered
by their height. How should this be done to minimize the total distance that
the statues are moved? You may assume for simplicity that all the statues have
different heights. [Azi10]

**
****a. **Write a program for
multiplying two sparse matrices, a** ***p*** **×** ***q*** **matrix** ***A*** **and** **a ** q** ×

b. Write a program for multiplying two sparse polynomials ** p(x)** and

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

Introduction to the Design and Analysis of Algorithms : Space and Time Trade-Offs : Sorting by Counting |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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