2.6 ORDER STATISTICS A problem closely related to sorting is that of selecting the kth smallest ele- ment in a sequence of n elements.† One obvious solution is to sort the sequence into nondecreasing order and then locate the kth element. As we have seen, this would require n log n comparisons. By a careful application of the divide-and-conquer strategy, we can find the kth smallest element in O(n) steps. An important special case occurs when k = [n/2], in which case we are finding the median of a sequence in linear time. Algorithm 3.6. Finding the kth smallest element. Input. A sequence S of n elements drawn from a linearly ordered set and an integer k, 1 ≤ k ≤ n. Output. The kth smallest element in S. Method. We use the recursive procedure SELECT in Fig. 3.10. ☐ Let us examine Algorithm 3.6 intuitively to see why it works. The basic idea is to partition the given sequence about some element m into three subsequences S₁, S., S₁ such that S, contains all elements less than m, S, all Strictly speaking, the kth smallest of a sequence a₁. da, is an element b in the sequence such that there are at most k - 1 values for i for which a,
2.6 ORDER STATISTICS A problem closely related to sorting is that of selecting the kth smallest ele- ment in a sequence of n elements.† One obvious solution is to sort the sequence into nondecreasing order and then locate the kth element. As we have seen, this would require n log n comparisons. By a careful application of the divide-and-conquer strategy, we can find the kth smallest element in O(n) steps. An important special case occurs when k = [n/2], in which case we are finding the median of a sequence in linear time. Algorithm 3.6. Finding the kth smallest element. Input. A sequence S of n elements drawn from a linearly ordered set and an integer k, 1 ≤ k ≤ n. Output. The kth smallest element in S. Method. We use the recursive procedure SELECT in Fig. 3.10. ☐ Let us examine Algorithm 3.6 intuitively to see why it works. The basic idea is to partition the given sequence about some element m into three subsequences S₁, S., S₁ such that S, contains all elements less than m, S, all Strictly speaking, the kth smallest of a sequence a₁. da, is an element b in the sequence such that there are at most k - 1 values for i for which a,
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter16: Searching, Sorting And Vector Type
Section: Chapter Questions
Problem 16SA
Related questions
Question
I am learning the
![2.6 ORDER STATISTICS
A problem closely related to sorting is that of selecting the kth smallest ele-
ment in a sequence of n elements.† One obvious solution is to sort the
sequence into nondecreasing order and then locate the kth element. As we
have seen, this would require n log n comparisons. By a careful application
of the divide-and-conquer strategy, we can find the kth smallest element in
O(n) steps. An important special case occurs when k = [n/2], in which case
we are finding the median of a sequence in linear time.
Algorithm 3.6. Finding the kth smallest element.
Input. A sequence S of n elements drawn from a linearly ordered set and an
integer k, 1 ≤ k ≤ n.
Output. The kth smallest element in S.
Method. We use the recursive procedure SELECT in Fig. 3.10. ☐
Let us examine Algorithm 3.6 intuitively to see why it works. The basic
idea is to partition the given sequence about some element m into three
subsequences S₁, S., S₁ such that S, contains all elements less than m, S, all
Strictly speaking, the kth smallest of a sequence a₁. da, is an element b in
the sequence such that there are at most k - 1 values for i for which a, <b and at least
k values of i for which a, ≤ b. For example. 4 is the second and third smallest ele-
ment of the sequence 7. 4. 2. 4.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F20f20d76-365f-4e43-a779-2a5ce112e22f%2F305aad44-c683-4892-8d72-97f48a97f088%2Fsgwb3zr_processed.jpeg&w=3840&q=75)
Transcribed Image Text:2.6 ORDER STATISTICS
A problem closely related to sorting is that of selecting the kth smallest ele-
ment in a sequence of n elements.† One obvious solution is to sort the
sequence into nondecreasing order and then locate the kth element. As we
have seen, this would require n log n comparisons. By a careful application
of the divide-and-conquer strategy, we can find the kth smallest element in
O(n) steps. An important special case occurs when k = [n/2], in which case
we are finding the median of a sequence in linear time.
Algorithm 3.6. Finding the kth smallest element.
Input. A sequence S of n elements drawn from a linearly ordered set and an
integer k, 1 ≤ k ≤ n.
Output. The kth smallest element in S.
Method. We use the recursive procedure SELECT in Fig. 3.10. ☐
Let us examine Algorithm 3.6 intuitively to see why it works. The basic
idea is to partition the given sequence about some element m into three
subsequences S₁, S., S₁ such that S, contains all elements less than m, S, all
Strictly speaking, the kth smallest of a sequence a₁. da, is an element b in
the sequence such that there are at most k - 1 values for i for which a, <b and at least
k values of i for which a, ≤ b. For example. 4 is the second and third smallest ele-
ment of the sequence 7. 4. 2. 4.
![1.
procedure SELECT(k, S):
if |S| <50 then
begin
sort S:
return kth smallest element in S
2.
3.
end
else
4.
5.
6.
7.
8.
9.
10.
11.
12.
begin
end
divide S into [|S|/5] sequences of 5 elements each
with up to four leftover elements;
sort each 5-element sequence;
let M be the sequence of medians of the 5-element sets;
- SELECT([|M|/21, M);
ጎን ←
let S1, S2, and S3 be the sequences of elements in S less
than, equal to, and greater than m, respectively;
if S₁then return SELECT(k, S₁)
else
if (SS₂ k) then return m
else return SELECT(k − |S₁| – |S2, S3)
Fig. 3.10. Algorithm to select kth smallest element.
0/5 sorted sequences
represented as
columns with smallest
element on top
•
m
Elements known to
be less than
- or equal to m
Elements known to
be greater than
or equal to m
Fig. 3.11 Partitioning of S by Algorithm 3.6.
Sequence M shown
in sorted order](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F20f20d76-365f-4e43-a779-2a5ce112e22f%2F305aad44-c683-4892-8d72-97f48a97f088%2Fa75lx8_processed.jpeg&w=3840&q=75)
Transcribed Image Text:1.
procedure SELECT(k, S):
if |S| <50 then
begin
sort S:
return kth smallest element in S
2.
3.
end
else
4.
5.
6.
7.
8.
9.
10.
11.
12.
begin
end
divide S into [|S|/5] sequences of 5 elements each
with up to four leftover elements;
sort each 5-element sequence;
let M be the sequence of medians of the 5-element sets;
- SELECT([|M|/21, M);
ጎን ←
let S1, S2, and S3 be the sequences of elements in S less
than, equal to, and greater than m, respectively;
if S₁then return SELECT(k, S₁)
else
if (SS₂ k) then return m
else return SELECT(k − |S₁| – |S2, S3)
Fig. 3.10. Algorithm to select kth smallest element.
0/5 sorted sequences
represented as
columns with smallest
element on top
•
m
Elements known to
be less than
- or equal to m
Elements known to
be greater than
or equal to m
Fig. 3.11 Partitioning of S by Algorithm 3.6.
Sequence M shown
in sorted order
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
EBK JAVA PROGRAMMING
Computer Science
ISBN:
9781337671385
Author:
FARRELL
Publisher:
CENGAGE LEARNING - CONSIGNMENT
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:
9780357392676
Author:
FREUND, Steven
Publisher:
CENGAGE L