UNIT-V: SEARCHING AND SORTING

Questions and Answers

What is searching?

The process of finding a specific data item or record in a list.

What are the two categories of searching?

External and internal searching.

Which of the following is a disadvantage of linear search?

It can be used on unsorted lists.

It is efficient for large data sets.

It is very time-consuming. (correct)

It is a simple technique.

What is the worst-case time complexity of linear search?

O(n) Signup and view all the answers

When is binary search used?

When the array is sorted in ascending or descending order. Signup and view all the answers

Binary search can be used on unsorted lists.

False Signup and view all the answers

What is the worst-case time complexity of binary search?

O(log2n + 1) Signup and view all the answers

What does sorting mean?

Arranging the elements in the list in a specific order. Signup and view all the answers

Which of the following properties makes a sorting algorithm 'stable'?

It preserves the relative order of equal elements. Signup and view all the answers

What is an 'in-place' sorting algorithm?

An algorithm that doesn’t require extra memory beyond the original array. Signup and view all the answers

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.