Write short notes on: i) Comparison of indexing and hashing ii) Radix sort iii) Insertion sort

i) Comparison of Indexing and Hashing

Feature	Indexing	Hashing
Data structure	Balanced search tree, Hash table	Hash table
Key space	Sorted	Unsorted
Lookup time	O(log n)	O(1)
Insert time	O(log n)	O(1)
Delete time	O(log n)	O(1)
Space overhead	O(n log n)	O(n)
Suitable applications	Range queries, Sorted data	Unsorted data, Key-value pairs

ii) Radix Sort

Radix sort is a non-comparative sorting algorithm that sorts data by grouping keys by the individual digits that make up the key. The algorithm proceeds from the least significant digit to the most significant digit, performing multiple passes through the list. In each pass, the algorithm places each element in a bucket corresponding to the value of the current digit, and then concatenates the elements from the buckets to reform the list. The process continues until all digits have been considered.

Radix sort is particularly efficient for sorting large numbers of integers, as it eliminates the need for comparisons between elements. The time complexity of radix sort is O(nk), where n is the number of elements and k is the number of digits in the largest element.

iii) Insertion Sort

Insertion sort is a simple sorting algorithm that builds the sorted list one element at a time. The algorithm starts by placing the first element in the sorted list. For each subsequent element, the algorithm finds the correct position for the element in the sorted list by inserting it between the two elements that surround its proper location.

Insertion sort is efficient for small lists and lists that are already partially sorted. The time complexity of insertion sort is O(n^2), where n is the number of elements. However, insertion sort can be improved to run in O(n log n) time by using a binary search tree to find the correct position for each element.