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:
- Initialize: Define the range of the search as the entire array.
- Find the middle element: Calculate the middle index of the array.
- 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.
- 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; }
Sorting:
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).
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.
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.
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.
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.
Heap Sort:
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
Post a Comment