GATE 2014 [Set-2]
January 20, 2025HCU PHD CS JUNE 2021
January 20, 2025HCU PHD CS JUNE 2021
Question 5 |
Answer the questions Q. 5 to Q. 8 by reading the passage given below.
The problem of sorting a mass of items, occupying consecutive locations in the
store of a computer, may be reduced to that of sorting two lesser segments of data,
provided that it is known that the keys of each of the items held in locations lower
than a certain dividing line are less than the keys of all the items held ill locations
above the dividing line. In this case the two segments may be sorted separately,
and as a result the whole mass of data will be sorted.
In practice, the existence of such a dividing line will be rare, but even if it did exist,
and its position would be unknown. It is, however, quite easy to rearrange the
items in such a way that a dividing line is brought into existence, and its position
is known. The method of doing this h&<; been given the name partition.
The first step of the partition process is to choose a particular key value which is
known to be within the range of keys of the items in the segment which is to be
sorted. A simple method of ensuring this is to choose the actual key value of one of
the items in the segment. The chosen key value will be called the bound. The aim
is now to produce a situation in which the keys of all the items above the dividing
line are equal to or greater than the bound. Fortunately, we do not need to know
the position of the dividing line in advance; its position is determined only at the
end of the partition process.
What sorting algorithm is described in the passage above?
The problem of sorting a mass of items, occupying consecutive locations in the
store of a computer, may be reduced to that of sorting two lesser segments of data,
provided that it is known that the keys of each of the items held in locations lower
than a certain dividing line are less than the keys of all the items held ill locations
above the dividing line. In this case the two segments may be sorted separately,
and as a result the whole mass of data will be sorted.
In practice, the existence of such a dividing line will be rare, but even if it did exist,
and its position would be unknown. It is, however, quite easy to rearrange the
items in such a way that a dividing line is brought into existence, and its position
is known. The method of doing this h&<; been given the name partition.
The first step of the partition process is to choose a particular key value which is
known to be within the range of keys of the items in the segment which is to be
sorted. A simple method of ensuring this is to choose the actual key value of one of
the items in the segment. The chosen key value will be called the bound. The aim
is now to produce a situation in which the keys of all the items above the dividing
line are equal to or greater than the bound. Fortunately, we do not need to know
the position of the dividing line in advance; its position is determined only at the
end of the partition process.
What sorting algorithm is described in the passage above?
insertion sort | |
Quicksort | |
Merge sort | |
Heap sort |
Correct Answer: B
Subscribe
Login
0 Comments