Page 253 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes 13.8 Keywords

Bubble Sort: Bubble sort is a simple sorting algorithm, which compares repeatedly each pair of
adjacent items and swaps them if they are in the incorrect order.

Hash Function: A hash function helps in connecting a key to the index of the hash table.
Hashing: Hashing is the solution when we want to search an element from a large collection of
data.

Insertion Sort: The insertion sort maintains the two sub-arrays within the same array.
Key: The element that is to be retrieved from the hash table is known as a key.
Merge Sort: Merge sort is based on divide and conquer method which takes the list to be sorted
and divide it in half to create two unsorted lists.
Radix Sort: Radix sort is a non-comparative integer sorting algorithm that sorts data with
integer keys by grouping keys by the individual digits which share the same significant position
and value.
Selection Sort: Selection sort, also called naive (selection) sort, is an in-place comparison sort.

13.9 Review Questions

1. Explain the concept of insertion sort with example.

2. Discuss the advantages and disadvantages of selection sort.
3. Describe merge sort with example. Also illustrate its implementation in C.
4. Explain the working of radix sort with example.

5. Discuss the features of Hashing.
6. For storing an element in the hash table, we assign a key to each element that is inserted.
Comment.

7. Discuss the use of hash function.
8. Illustrate the working of hashing with example.
9. Make distinction between bubble sort and quick sort.
10. Describe the concept of heap sort with example.

Answers: Self Assessment

1. True 2. False

3. Selection sort 4. big-O notation
5. Divide and Conquer 6. Merge Sort
7. Radix sort 8. LSD
9. Hashing 10. load factor

11. hash function 12. Static
13. Bubble sort 14. Pivot
15. Heap sort

246 LOVELY PROFESSIONAL UNIVERSITY