Skip to main content

Data Structure Unit 4 | serching | AKTU Free Notes Online.

 Concept of Searching:

  • Searching is the process of finding a particular item or element within a collection of items.
  • It involves examining each element in the collection until the desired item is found.

Sequential Search:

  • Also known as linear search.
  • Involves checking each element in a list or array one by one from the beginning until the target element is found or the end of the list is reached.
  • Simplest form of searching.
  • Works well for small lists or unsorted data.
  • Time complexity is O(n) where n is the number of elements in the list.

Index Sequential Search:

  • Enhances the efficiency of sequential search by using an index.
  • The index is a data structure containing pointers or references to the elements in the main data structure (e.g., array).
  • The index allows for quicker access to elements, reducing the number of comparisons needed.
  • The search first checks the index to locate the block where the target element might be, then performs a sequential search within that block.
  • Suitable for large datasets where the overhead of creating and maintaining an index is outweighed by the efficiency gained during searches.
  • Time complexity depends on the size and structure of the index but generally improves search performance compared to a pure sequential search.

  • Binary Search:

    Binary search is an efficient algorithm for finding a target value within a sorted array. Here's a step-by-step explanation of the binary search algorithm along with a C program:

    Binary Search Algorithm:

    1. Initialize: Define the range of the search as the entire array.
    2. Find the middle element: Calculate the middle index of the array.
    3. Compare with the target:
      • If the middle element is equal to the target, return the index of the middle element.
      • If the middle element is greater than the target, update the range to the lower half of the array.
      • If the middle element is less than the target, update the range to the upper half of the array.
    4. Repeat: Continue steps 2-3 until the target is found or the search range becomes empty.

    Binary Search C Program:

  • #include <stdio.h> #include <conio.h>

  • int binarySearch(int arr[], int low, int high, int target) { while (low <= high) { int mid = low + (high - low) / 2; // Calculate mid to avoid overflow if (arr[mid] == target) { return mid; // Element found, return index } else if (arr[mid] < target) { low = mid + 1; // Discard left half } else { high = mid - 1; // Discard right half } } return -1; // Element not found } // Main function int main() { int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; int n = sizeof(arr) / sizeof(arr[0]); int target; scanf("%d", &target); int index = binarySearch(arr, 0, n - 1, target); if (index != -1) { printf("Element %d found at index %d\n", target, index); } else { printf("Element %d not found in the array\n", target); } return 0; }




Hashing ---> https://www.geeksforgeeks.org/introduction-to-hashing-data-structure-and-algorithm-tutorials/?ref=ghm

Sorting:


Sorting is the process of arranging items in a specific order, typically ascending or descending, according to some criteria. There are various sorting algorithms, each with its own characteristics in terms of efficiency, simplicity, and space complexity. Let's delve into the details of some commonly used sorting algorithms:


Selection Sort:


  • Selection Sort works by repeatedly finding the minimum element from the unsorted portion and swapping it with the first unsorted element.
  • It divides the array into two parts: sorted and unsorted.
  • It has a time complexity of O(n^2) but is simple and has a space complexity of O(1).


for more--->  https://www.geeksforgeeks.org/selection-sort/

Bubble Sort:


  • Bubble Sort compares adjacent elements and swaps them if they are in the wrong order.
  • It repeatedly passes through the array until no swaps are needed, indicating that the array is sorted.
  • It is not efficient for large datasets due to its time complexity of O(n^2) but is simple to implement.

for more--> https://www.geeksforgeeks.org/bubble-sort/


Insertion Sort:


  • Insertion Sort works by iteratively building a sorted Sublist from the unsorted portion of the array.
  • It selects an element from the unsorted portion and inserts it into its correct position in the sorted sublist.
  • It repeats this process until all elements are in the sorted order.
  • It is efficient for small datasets or nearly sorted datasets.

for more--> https://www.geeksforgeeks.org/insertion-sort/

Merge Sort:



  • Merge Sort also utilizes the divide-and-conquer strategy. It divides the array into two halves, sorts each half, and then merges them.
  • It recursively sorts the sub-arrays until each sub-array has only one element.
  • It has a time complexity of O(n log n) and is stable but requires additional space for merging.




Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.


for more--> https://www.geeksforgeeks.org/merge-sort/

Quick Sort:


  • Quick Sort employs the divide-and-conquer strategy. It selects a pivot element and partitions the array into two sub-arrays such that elements less than the pivot are on its left and elements greater than the pivot are on its right.
  • It recursively sorts the sub-arrays.
  • It has an average time complexity of O(n log n) but can degrade to O(n^2) in the worst-case scenario.

for more--> https://www.geeksforgeeks.org/quick-sort/

Heap Sort:


Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.

Heap Sort Algorithm

To solve the problem follow the below idea:

First convert the array into heap data structure using heapify, then one by one delete the root node of the Max-heap and replace it with the last node in the heap and then heapify the root of the heap. Repeat this process until size of heap is greater than 1.

  • Build a heap from the given input array.
  • Repeat the following steps until the heap contains only one element:
    • Swap the root element of the heap (which is the largest element) with the last element of the heap.
    • Remove the last element of the heap (which is now in the correct position).
    • Heapify the remaining elements of the heap.
  • The sorted array is obtained by reversing the order of the elements in the input array.

 for more--> https://www.geeksforgeeks.org/heap-sort/


Radix Sort:  


for more--> https://www.geeksforgeeks.org/radix-sort/


Comments

Popular posts from this blog

linkedlist

  Linked Lists: An Overview Definition: A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains data and a reference (or pointer) to the next node in the sequence. Properties: Dynamic Size : Linked lists can grow or shrink in size dynamically as elements are added or removed. Flexibility : They allow for efficient insertion and deletion operations at any position in the list. Non-Contiguous Memory Allocation : Unlike arrays, linked list nodes can be scattered in memory, connected only by pointers. Types of Linked Lists: Singly Linked List: In a singly linked list, each node contains data and a pointer to the next node in the sequence. Doubly Linked List: In a doubly linked list, each node contains data and pointers to both the next and previous nodes, allowing bidirectional traversal. Circular Linked List: In a circular linked list, the last node points back to the first node, forming a circular structure. Advantages of Linked ...

Queue | Unit-2 | DSA

 https://www.programiz.com/dsa/queue Array Implementaion of queue: #include <stdio.h> #define MAX_SIZE 100 // Maximum size of the queue int queue[MAX_SIZE]; // Array to store the queue elements int front = -1;      // Front of the queue int rear = -1;       // Rear of the queue // Function to check if the queue is empty int is_empty() {     return (front == -1 && rear == -1); } // Function to check if the queue is full int is_full() {     return (rear == MAX_SIZE - 1); } // Function to insert an element into the queue void enqueue(int value) {     if (is_full()) {         printf("Queue Overflow\n");         return;     }     if (is_empty()) {         front = rear = 0; // If the queue is empty, initialize front and rear to 0     } else {         rear++; // Move rear to the next position   ...

Tools and Methods Used In Cyber Crimes | Proxy Servers and Anonymizers | AKTU B.Tech 2nd year Cyber Security Unit 3 Notes

  Introduction to Tools and Methods in Cybercrime Cybercrime Landscape: The cyber landscape is evolving rapidly, and so are the tools and methods employed by malicious actors. Understanding these elements is essential for defending against cyber threats. Here, we'll delve into three prominent areas of concern. Proxy Servers Proxy Server Basics: Definition: An intermediate server between a user's device and the internet. Manages requests and responses between the user and websites. Functionality: User's request ➔ Proxy server ➔ Website. Website's response ➔ Proxy server ➔ User's device. Benefits of Proxy Servers: Anonymity: Conceals user's identity by presenting the proxy's IP address to websites. Security: Acts as a buffer against malware, viruses, and online attacks. Access Control: Configurable to block or allow specific types of traffic, enhancing control. Types of Proxy Servers: Forward Proxy: Sits between client and internet. Forwards client's requ...