Summary Fundamentals of Data Structures (210242)

󾠰
Unit 3
Searching Techniques
Characteristics
Sequential or Linear Search
Advantages
Disadvantage
Binary Search
Advantages
Disadvantage
Fibonacci Search
Indexed Sequential Search
Applications of Sorting
Types
Internal Sorting
External Sorting
Sorting concepts
Sort Order
Sort Stability
Efficiency and Passes
Sorting Techniques
Bubble Sort
Insertion Sort
Advantages
Selection Sort
Quick Sort
Shell Sort
Radix Sort
Counting Sort
Bucket Sort



Searching Techniques

Unit 3 1

, Characteristics
1. Efficient

2. Less number of conversions

3. Space must be less

e.g. Sequential or linear search, indexed sequential search, binary search


Sequential or Linear Search
Time Complexity - O(1) → O(n)

Advantages
1. Simple

2. Does not require specific ordering before applying

Disadvantage
1. Less efficient


Binary Search
Time Complexity - O(1) → O(log n)

Advantages
1. Efficient

Disadvantage
1. Requires specific ordering

2. Complex


Fibonacci Search
Time Complexity - O(1) → O(log n)


Indexed Sequential Search


Unit 3 2