Presorting is an old idea in computer science. In fact, interest in sorting algorithms is due, to a significant degree, to the fact that many questions about a list are easier to answer if the list is sorted.

**Presorting**

Presorting is an old idea in computer science.
In fact, interest in sorting algorithms is due, to a significant degree, to the
fact that many questions about a list are easier to answer if the list is
sorted. Obviously, the time efficiency of algorithms that involve sorting may
depend on the efficiency of the sorting algorithm being used. For the sake of
simplicity, we assume throughout this section that lists are implemented as
arrays, because some sorting algorithms are easier to implement for the array
representation.

So far, we have discussed three elementary
sorting algorithms—selection sort, bubble sort, and insertion sort—that are
quadratic in the worst and average cases, and two advanced
algorithms—mergesort, which is always in ** (n** log

Following are three examples that illustrate
the idea of presorting. More examples can be found in this section’s exercises.

**EXAMPLE 1 ***Checking
element uniqueness in an array*** **If this element unique-ness problem looks familiar to you, it
should; we considered a brute-force algo-rithm for the problem in Section 2.3
(see Example 2). The brute-force algorithm compared pairs of the array’s
elements until either two equal elements were found or no more pairs were left.
Its worst-case efficiency was in * (n*^{2}** )**.

Alternatively, we can sort the array first and
then check only its consecutive elements: if the array has equal elements, a
pair of them must be next to each other, and vice versa.

**ALGORITHM** *PresortElementUniqueness*** (A**[0

//Solves the element uniqueness problem by
sorting the array first //Input: An array ** A**[0..

//Output: Returns “true” if ** A** has no equal elements, “false” otherwise sort the array

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

**if **** A**[

The running time of this algorithm is the sum
of the time spent on sorting and the time spent on checking consecutive
elements. Since the former requires at least ** n** log

**EXAMPLE 2 ***Computing
a mode*** **A** ***mode*** **is a value that occurs most often in a** **given list of numbers. For example, for 5, 1, 5, 7, 6, 5, 7, the
mode is 5. (If several different values occur most often, any of them can be
considered a mode.) The brute-force approach to computing a mode would scan the
list and compute the frequencies of all its distinct values, then find the
value with the largest frequency.

In order to implement this idea, we can store
the values already encountered, along with their frequencies, in a separate
list. On each iteration, the ** i**th element of the original list is compared
with the values already encountered by traversing this auxiliary list. If a
matching value is found, its frequency is incremented; otherwise, the current
element is added to the list of distinct values seen so far with a frequency of
1.

It is not difficult to see that the worst-case
input for this algorithm is a list with no equal elements. For such a list, its
** i**th element is compared with

The additional ** n** − 1 comparisons needed to find the largest
frequency in the aux-iliary list do not change the quadratic worst-case
efficiency class of the algorithm.

As an alternative, let us first sort the input.
Then all equal values will be adjacent to each other. To compute the mode, all
we need to do is to find the longest run of adjacent equal values in the sorted
array.

**ALGORITHM** *PresortMode*** (A**[0

//Computes the mode of an array by sorting it
first //Input: An array ** A**[0

sort the array *A*** i **←

** modef requency **←

** runlengt h **←

**while ***i*** **+** ***runlengt h*** **≤** ***n*** **−** **1** and **** A**[

**if ***runlengt h > modef requency*

** modefrequency **←

**return ***modevalue*

The analysis here is similar to the analysis of
Example 1: the running time of the algorithm will be dominated by the time
spent on sorting since the remainder of the algorithm takes linear time (why?).
Consequently, with an ** n** log

**EXAMPLE 3 ***Searching
problem*** **Consider the problem of searching for a given** **value ** v** in a given array of

which is inferior to sequential search. The
same will also be true for the average-case efficiency. Of course, if we are to
search in the same list more than once, the time spent on sorting might well be
justified. (Problem 4 in this section’s exercises asks to estimate the minimum
number of searches needed to justify presorting.)

Before we finish our discussion of presorting,
we should mention that many, if not most, geometric algorithms dealing with
sets of points use presorting in one way or another. Points can be sorted by
one of their coordinates, or by their distance from a particular line, or by
some angle, and so on. For example, presorting was used in the
divide-and-conquer algorithms for the closest-pair problem and for the
convex-hull problem, which were discussed in Section 5.5.

Further, some problems for directed acyclic
graphs can be solved more easily after topologically sorting the digraph in
question. The problems of finding the longest and shortest paths in such
digraphs (see the exercises for Sections 8.1 and 9.3) illustrate this point.

Finally, most algorithms based on the greedy
technique, which is the subject of Chapter 9, require presorting of their
inputs as an intrinsic part of their operations.

**
**Consider
the problem of finding the distance between the two closest numbers in an array
of ** n** numbers. (The distance between two numbers

**
**Design a
presorting-based algorithm for solving this problem and deter-mine its efficiency
class.

**
**Compare
the efficiency of this algorithm with that of the brute-force algo-rithm (see
Problem 9 in Exercises 1.2).

**
**Let ** A** = {

**
**Design a
brute-force algorithm for solving this problem and determine its efficiency
class.

Design a presorting-based algorithm for solving
this problem and deter-mine its efficiency class.

**
**Consider
the problem of finding the smallest and largest elements in an array of ** n** numbers.

**
**Design a
presorting-based algorithm for solving this problem and deter-mine its
efficiency class.

**
**Compare
the efficiency of the three algorithms: (i) the brute-force algo-rithm, (ii)
this presorting-based algorithm, and (iii) the divide-and-conquer algorithm
(see Problem 2 in Exercises 5.1).

**
**Estimate
how many searches will be needed to justify time spent on presorting an array
of 10^{3} elements if sorting is done by mergesort and searching is
done by binary search. (You may assume that all searches are for elements known
to be in the array.) What about an array of 10^{6} elements?

**
**To sort
or not to sort? Design a reasonably efficient algorithm for solving each of the
following problems and determine its efficiency class.

**
**You are
given ** n** telephone bills and

**
**You have
a file of ** n** student records indicating each student’s number, name, home
address, and date of birth. Find out the number of students from each of the 50
U.S. states.

Given a set of ** n** ≥ 3 points in the Cartesian plane, connect them
in a simple polygon, i.e., a closed path through all the points so that its
line segments (the polygon’s edges) do not intersect (except for neighboring
edges at their common vertex). For example,

**
**Does the
problem always have a solution? Does it always have a unique solution?

**
**Design a
reasonably efficient algorithm for solving this problem and indi-cate its
efficiency class.

You have an array of ** n** real numbers and another integer

**
**You have
a list of ** n** open intervals

*Number
placement *Given a list of* **n** *distinct integers and a sequence of* **n** *boxes with pre-set inequality signs inserted
between them, design an algo-rithm that places the numbers into the boxes to
satisfy those inequalities. For example, the numbers 4, 6, 3, 1, 8 can be
placed in the five boxes as shown below:

**
***Maxima search*

A point ** (x_{i},
y_{i})** in the
Cartesian plane is said to be dominated by point

Design an efficient algorithm for finding all
the maximum points of a given set of ** n** points in the Cartesian plane. What is the
time efficiency class of your algorithm?

**b. **Give a few real-world applications of this
algorithm.

**11. ***Anagram
detection*

**
**

**
**Design
an efficient algorithm for finding all sets of anagrams in a large file such as
a dictionary of English words [Ben00]. For example, *eat, ate,* and *tea *belong
to one such set.

**
**Write a
program implementing the algorithm.

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

Introduction to the Design and Analysis of Algorithms : Transform and Conquer : Presorting |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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