Page 268 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

96 Notes
22
53

83
04
8. Consider an unsorted array A[n] of integer elements that may have many elements present
more than once. It is required to store only the distinct elements of the array A in a separate
array B. The information about the number of times each element is replicated is maintained
in a third array C. For example, C[0] would indicate the number of times the element B[0]
occurs in array A. Write a C program to generate the arrays B and C, given an array A.
9. Write a C program that finds the largest and the second largest elements in an unsorted

array A. The program should make just a single scan of the array.
10. Distinguish between internal and external method of sorting.

Answers: Self Assessment

1. (b) 2. (b) 3. (a) 4. (d)
5. sorting 6. O(nlog D) 7. O(n log(n)) + O(n)
8. O(nlog (n)) 9. False 10. False 11. False
2
12. True

12.14 Further Readings

Books Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, Prentice
Hall, 1988.

Burkhard Monien, Data Structures and Effi cient Algorithms, Thomas Ottmann,
Springer.
Kruse, Data Structure & Program Design, Prentice Hall of India, New Delhi.
Mark Allen Weles, Data Structure & Algorithm Analysis in C, Second Ed., Addison-
Wesley Publishing.
RG Dromey, How to Solve it by Computer, Cambridge University Press.
Shi-Kuo Chang, Data Structures and Algorithms, World Scientifi c.
Shi-kuo Chang, Data Structures and Algorithms, World Scientifi c.
Sorenson and Tremblay, An Introduction to Data Structure with Algorithms.
Thomas H. Cormen, Charles E, Leiserson & Ronald L., Rivest: Introduction to
Algorithms. Prentice-Hall of India Pvt. Limited, New Delhi.
Timothy A. Budd, Classic Data Structures in C++, Addison Wesley.

Online links www.en.wikipedia.org
www.web-source.net
www.webopedia.com

LOVELY PROFESSIONAL UNIVERSITY 263