Unit - II Searching and Sorting
Overview of Searching and Sorting
Methods
2.1 Searching
• • Searching is the process of finding an item in
a dataset.
• • Methods:
• - Linear Search: Sequentially checks each
element.
• - Binary Search: Divides the dataset and
searches in halves (requires sorted data).
Linear Search
• • Simple method: Check each element one by
one.
• • Best Case: Item found at first position (O(1)).
• • Worst Case: Item found at last position or
not present (O(n)).
Binary Search
• • Efficient method for sorted datasets.
• • Repeatedly divide the dataset in half.
• • Best Case: Middle element is the target
(O(1)).
• • Worst Case: O(log n).
2.2 Sorting
• • Sorting arranges data in a specific order
(ascending/descending).
• • Common Methods:
• - Bubble Sort
• - Selection Sort
• - Insertion Sort
• - Quick Sort
• - Merge Sort
Bubble Sort
• • Repeatedly swap adjacent elements if they
are in the wrong order.
• • Simple but inefficient for large datasets.
• • Time Complexity: O(n²).
Selection Sort
• • Select the smallest element and place it at
the beginning.
• • Repeat for all positions.
• • Time Complexity: O(n²).
Insertion Sort
• • Build the sorted array one element at a time.
• • Insert each new element into its correct
position.
• • Time Complexity: O(n²).
Quick Sort
• • Divide-and-Conquer method.
• • Choose a pivot, partition the array around it.
• • Recursively sort partitions.
• • Average Time Complexity: O(n log n).
Merge Sort
• • Divide-and-Conquer method.
• • Divide array into halves, sort and merge.
• • Stable and efficient.
• • Time Complexity: O(n log n).
