Data Structures Unit 1: Searching & Sorting

Data Structures Overview

• Data is represented in binary form (0s and 1s), with the basic unit being a bit.
• Data structure organizes data efficiently for specific purposes.
• Main objectives include effective data storage and retrieval.
• A data structure can be defined mathematically as a triplet: D = (d, f, a), where:
  • d = set of data objects (variables)
  • f = set of functions
  • a = rules for function implementation

Classification of Data Structures

• Linear Data Structures: Elements form a sequence (e.g., Arrays, Linked Lists, Stacks, Queues).
• Non-Linear Data Structures: Elements are not in a sequence (e.g., Trees, Graphs).

Searching Techniques

Linear Search

• Searches each element one by one with O(n) time complexity.
• Starts comparison with the first element and continues until the element is found or the list is exhausted.
• Steps:
  • Read the search element from the user.
  • Compare it with the first element; if matched, display "Given element found!!!".
  • If not matched, proceed to the next element.
  • Repeat until either the element is found or the end of the list is reached, resulting in "Element not found!!!".

Binary Search

• More efficient compared to linear search, ideal for sorted arrays.
• Compares the target element with the middle element of the array, leading to three potential cases:
  • Case 01: If the middle element is the target, return its index.
  • Case 02: If the target is greater, search the right sub-array.
  • Case 03: If the target is smaller, search the left sub-array.
• This process iterates on sub-arrays until the element is found or the sub-array becomes empty.

Introduction to Sorting Techniques

• Sorting organizes data in a particular order and includes various algorithms. Key types are:
  • Insertion Sort: Builds a sorted array by repeatedly taking an element and inserting it into the correct position.
  • Selection Sort: Selects the smallest (or largest) element and moves it to the sorted portion of the array.
  • Bubble Sort: Repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order.
  • Merge Sort: Divides the array into halves, sorts them, and merges them back together.
  • Quick Sort: Selects a 'pivot' element and partitions the array into elements less than and greater than the pivot, applying the same strategy recursively.

This quiz covers the foundational concepts of data structures, focusing on searching and sorting techniques. You will explore various searching methods such as linear and binary search, alongside sorting algorithms including insertion, selection, bubble, merge, and quick sort. Test your understanding with this comprehensive assessment.