UNIT-V: SEARCHING AND SORTING

Study Notes

Searching

Searching identifies a specific data item or record in a list, distinguished as successful (item exists) or unsuccessful (item doesn’t exist).
Can be categorized as:
- External searching: Records stored on disk.
- Internal searching: Records stored in main memory.
Common searching algorithms include:
- Linear (Sequential) Search:
  - Simplest method; does not require sorted lists.
  - Compares the search key against each element sequentially.
  - Terminates if a match is found or end of list is reached (indicating failure).
  - Complexity: Worst and average case is O(n), where n is total elements.
  - Advantages:
    - Simple implementation.
    - Works with unsorted data.
  - Disadvantages:
    - Slow for large datasets.
    - Time-consuming with increasing data size.
- Binary Search:
  - Requires sorted data in ascending or descending order.
  - Compares the search key with the middle element.
  - Narrows the search area by half based on comparison results.
  - Complexity: Worst case time complexity is O(log2n + 1).
  - Advantages:
    - Much faster than linear search for large lists.
  - Disadvantages:
    - Requires sorted input, failing otherwise.

Sorting

Sorting organizes elements in a specific order (ascending or descending).
Key properties of sorting algorithms include:
- Stable: Maintains relative order of equal elements.
- In place: Requires minimal extra memory, aside from input array.
Types of sorting methods:
- Internal Sorting: Sorting data completely in main memory.
- External Sorting: Deals with large datasets partially in main memory and auxiliary memory.
Insertion Sort:
- A simple, in-place sorting algorithm that builds a sorted array incrementally.
- Involves inserting one element at a time into the correct position within the sorted subset.

Description

This quiz focuses on the concepts of searching and sorting in data structures. It covers various techniques for finding specific data items within lists and discusses the differences between external and internal searching methods. Test your understanding of these essential algorithms and their applications.