Page 267 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes (d) Bubble sort

4. Heap sort proceeds in
(a) Five phase
(b) Three phases
(c) One phase
(d) Two phase
Fill in the blanks:

5. Arranging objects in a specified order is called ..................... .
6. The average time complexity of the quick sort algorithm is ..................... .
7. The computing time of heapsort is ..................... .
8. The time complexity of the algorithm is ..................... both average and worst case.

State whether the following statements are true or false:
9. The order of linear search in worst case is O(n/2).

10. Linear search is more efficient than Binary search.
11. For Binary search, the array has to be sorted in ascending order only.
12. A fi le is a collection of records and a record is in turn a collection of fi elds.

12.13 Review Questions

1. What is sorting? Explain insertion sorting in details.
2. Distinguish between quick and heap sort.
3. Explain 2-way merge sort.
4. Distinguish between linear and binary search.

5. Explain the application of searching.
6. Consider the list given below whose elements are arranged in an ascending order. Assume
that a binary search technique is used. Find out the number of probes required to fi nd each
entry in the list.
16
22
48
53
55
71
80

7. Sort the list given below by applying the heapsort method.
81
52
53

262 LOVELY PROFESSIONAL UNIVERSITY