Data Structure using in C++ 4th unit
📘 UNIT – IV: Searching, Sorting & Heaps
-🇩🇦🇹🇦 --https://sites.super.myninja.ai/ff8bd05b-902a-4f34-a35f-b1a676681394/425664e6/unit1/fundamental-concepts.html
🔍 1. Searching
a. Linear Search
Check each element one by one.
Time complexity: O(n)
int linearSearch(int arr[], int n, int key) {
for(int i = 0; i < n; i++) {
if(arr[i] == key) return i;
}
return -1;
}
b. Binary Search
Requires sorted array.
Divide and conquer approach.
Time complexity: O(log n)
int binarySearch(int arr[], int left, int right, int key) {
while(left <= right) {
int mid = (left + right)/2;
if(arr[mid] == key) return mid;
else if(arr[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}
🖼️ Binary Search Visual
---
🔃 2. Sorting Algorithms
a. Bubble Sort
Repeatedly swap adjacent elements.
Time complexity: O(n²)
void bubbleSort(int arr[], int n) {
for(int i = 0; i < n-1; i++)
for(int j = 0; j < n-i-1; j++)
if(arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
b. Insertion Sort
Build sorted list one element at a time.
Time complexity: O(n²)
void insertionSort(int arr[], int n) {
for(int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while(j >= 0 && arr[j] > key)
arr[j+1] = arr[j--];
arr[j+1] = key;
}
}
c. Selection Sort
Find min and place it at correct position.
Time complexity: O(n²)
void selectionSort(int arr[], int n) {
for(int i = 0; i < n-1; i++) {
int min_idx = i;
for(int j = i+1; j < n; j++)
if(arr[j] < arr[min_idx])
min_idx = j;
swap(arr[i], arr[min_idx]);
}
}
d. Quick Sort
Divide array by pivot, sort parts recursively.
Time complexity: Average O(n log n)
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for(int j = low; j < high; j++) {
if(arr[j] < pivot)
swap(arr[++i], arr[j]);
}
swap(arr[i+1], arr[high]);
return i+1;
}
void quickSort(int arr[], int low, int high) {
if(low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
e. Merge Sort
Divide array, sort, and merge.
Time complexity: O(n log n)
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
for(int i=0; i<n1; i++) L[i]=arr[l+i];
for(int j=0; j<n2; j++) R[j]=arr[m+1+j];
int i=0, j=0, k=l;
while(i<n1 && j<n2) {
if(L[i]<=R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while(i<n1) arr[k++] = L[i++];
while(j<n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = (l + r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
📊 Sorting Comparison Chart
Algorithm Best Case Average Case Worst Case Space Complexity
Bubble Sort O(n) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)
🖼️ Sorting Visual
---
🗂️ 3. Heaps
a. Heap Concept
Binary Tree with Heap Property
Max Heap: Parent ≥ children
Min Heap: Parent ≤ children
b. Heap Operations
Insert: O(log n)
Delete Max/Min: O(log n)
c. Heap Sort
Build heap → Repeatedly remove root → Re-heapify
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1, r = 2*i + 2;
if(l < n && arr[l] > arr[largest]) largest = l;
if(r < n && arr[r] > arr[largest]) largest = r;
if(largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for(int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
for(int i = n-1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
🖼️ Heap Tree Example
---
✅ Summary
Topic Key Points
Searching Linear: simple; Binary: fast but sorted array
Sorting Bubble/Insertion/Selection: Simple but slow; Merge/Quick: Efficient
Heaps Tree-based structure for priority operations; used in Heap Sort
Comments
Post a Comment