Module 7: Searching & Sorting
By the end of this module, students will be able to:
- Understand fundamental searching algorithms and their applications
- Implement linear and binary search algorithms
- Understand various sorting algorithms and their characteristics
- Analyze time and space complexity of searching and sorting algorithms
- Compare different algorithms and choose appropriate ones for specific problems
- Implement sorting algorithms in C
- Optimize searching and sorting operations
- Apply searching and sorting to solve real-world problems
- 1. Introduction to Searching
- 2. Linear Search
- 3. Binary Search
- 4. Introduction to Sorting
- 5. Simple Sorting Algorithms
- 6. Efficient Sorting Algorithms
- 7. Comparison of Sorting Algorithms
- 8. Practical Applications
1. Introduction to Searching
1.1 What is Searching?
Searching is the process of finding a particular element or checking if an element exists in a data structure (array, linked list, tree, etc.).
Real-World Analogies:
- Finding a book in a library
- Searching for a contact in your phone
- Looking up a word in a dictionary
- Finding a file on your computer
Types of Searching:
- Linear Search - Sequential search through elements
- Binary Search - Divide and conquer approach (requires sorted data)
- Jump Search - Jumping ahead by fixed steps
- Interpolation Search - Improved binary search for uniformly distributed data
- Exponential Search - Finding range then binary search
Note: There's actually a lot more searching algorithms, but we'll focus on the most common ones.
1.2 Why Study Searching Algorithms?
Importance:
- One of the most common operations in programming
- Critical for database queries
- Essential for data retrieval systems
- Foundation for more complex algorithms
- Performance impact on large datasets
Performance Metrics:
- Best Case: Minimum number of comparisons
- Average Case: Expected number of comparisons
- Worst Case: Maximum number of comparisons
- Space Complexity: Extra memory required
2. Linear Search
2.1 Concept
Linear Search (also called Sequential Search) checks every element in the array sequentially until the target is found or the end is reached.
How it works:
- Start from the first element
- Compare each element with the target
- If match found, return the position
- If end reached without match, return -1
Visual Representation:
Array: [10, 25, 30, 15, 40, 35]
Target: 15
Step 1: Check 10 ≠ 15
Step 2: Check 25 ≠ 15
Step 3: Check 30 ≠ 15
Step 4: Check 15 = 15 ✓ Found at index 3!
2.2 Implementation
Basic Linear Search
#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
int main() {
int arr[] = {10, 25, 30, 15, 40, 35};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 15;
int result = linearSearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found\n", target);
}
return 0;
}
Linear Search with Count
int linearSearchCount(int arr[], int n, int target, int *comparisons) {
*comparisons = 0;
for (int i = 0; i < n; i++) {
(*comparisons)++;
if (arr[i] == target) {
return i;
}
}
return -1;
}
// Usage
int main() {
int arr[] = {10, 25, 30, 15, 40, 35};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 15;
int comparisons = 0;
int result = linearSearchCount(arr, n, target, &comparisons);
printf("Result: %d\n", result);
printf("Comparisons made: %d\n", comparisons);
return 0;
}
Find All Occurrences
void linearSearchAll(int arr[], int n, int target) {
int found = 0;
printf("Element %d found at indices: ", target);
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
printf("%d ", i);
found = 1;
}
}
if (!found) {
printf("Not found");
}
printf("\n");
}
int main() {
int arr[] = {10, 25, 30, 25, 40, 25};
int n = sizeof(arr) / sizeof(arr[0]);
linearSearchAll(arr, n, 25);
// Output: Element 25 found at indices: 1 3 5
return 0;
}
2.3 Complexity Analysis
| Case | Time Complexity | Description |
|---|---|---|
| Best Case | O(1) | Element found at first position |
| Average Case | O(n) | Element found in middle |
| Worst Case | O(n) | Element at last position or not found |
| Space Complexity | O(1) | No extra space needed |
Visualization:
Best Case (1 comparison):
[15, 25, 30, ...] → Found immediately!
Average Case (n/2 comparisons):
[10, 25, 30, 15, ...] → Found in middle
Worst Case (n comparisons):
[10, 25, 30, 40, 35, 15] → Found at end
or
[10, 25, 30, 40, 35, 20] → Not found (checked all)
2.4 Advantages and Disadvantages
Advantages:
- Simple to implement
- Works on unsorted arrays
- No preprocessing required
- Works well for small datasets
- No extra memory needed
Disadvantages:
- Slow for large datasets
- Inefficient compared to other algorithms
- Time complexity increases linearly
When to Use:
- Small datasets (n < 100)
- Unsorted data
- When simplicity is priority
- When data changes frequently
3. Binary Search
3.1 Concept
Binary Search is a fast search algorithm that works on sorted arrays by repeatedly dividing the search interval in half.
Prerequisites:
- Array must be sorted
- Random access to elements (arrays work well)
How it works:
- Compare target with middle element
- If match found, return position
- If target is smaller, search left half
- If target is larger, search right half
- Repeat until found or search space is empty
Visual Representation:
Sorted Array: [10, 15, 25, 30, 35, 40, 50]
Target: 35
Step 1: Check middle (30)
[10, 15, 25, 30, | 35, 40, 50]
^
35 > 30, search right half
Step 2: Check middle of right half (40)
[35, 40, 50]
^
35 < 40, search left half
Step 3: Check middle of remaining (35)
[35]
^
35 = 35, Found at index 4!
3.2 Implementation
Iterative Binary Search
#include <stdio.h>
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
// Check if target is at mid
if (arr[mid] == target) {
return mid;
}
// If target is greater, ignore left half
if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
return -1; // Element not found
}
int main() {
int arr[] = {10, 15, 25, 30, 35, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 35;
int result = binarySearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found\n", target);
}
return 0;
}
Why mid = left + (right - left) / 2?
// This can overflow for large values:
int mid = (left + right) / 2;
// This is safer:
int mid = left + (right - left) / 2;
// Example of overflow:
// left = 2^30, right = 2^30
// (left + right) = 2^31 → overflow in 32-bit int
// left + (right - left) / 2 = no overflow
Recursive Binary Search
int binarySearchRecursive(int arr[], int left, int right, int target) {
// Base case: element not found
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
// Element found at mid
if (arr[mid] == target) {
return mid;
}
// Search in left half
if (arr[mid] > target) {
return binarySearchRecursive(arr, left, mid - 1, target);
}
// Search in right half
return binarySearchRecursive(arr, mid + 1, right, target);
}
// Wrapper function
int binarySearch(int arr[], int n, int target) {
return binarySearchRecursive(arr, 0, n - 1, target);
}
Binary Search with Comparison Count
int binarySearchCount(int arr[], int n, int target, int *comparisons) {
int left = 0;
int right = n - 1;
*comparisons = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
(*comparisons)++;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {10, 15, 25, 30, 35, 40, 50, 60, 70, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 35;
int comparisons = 0;
int result = binarySearchCount(arr, n, target, &comparisons);
printf("Result: %d\n", result);
printf("Comparisons: %d\n", comparisons);
printf("Linear search would need: %d comparisons\n", result + 1);
return 0;
}
3.3 Complexity Analysis
| Case | Time Complexity | Description |
|---|---|---|
| Best Case | O(1) | Element found at middle |
| Average Case | O(log n) | Typical search |
| Worst Case | O(log n) | Element at edge or not found |
| Space Complexity | O(1) iterative, O(log n) recursive | Stack space for recursion |
Comparison with Linear Search:
Array size: 1,000,000 elements
Linear Search:
- Average: 500,000 comparisons
- Worst: 1,000,000 comparisons
Binary Search:
- Average: 20 comparisons
- Worst: 20 comparisons
Speed improvement: ~50,000x faster!
Growth Comparison:
n Linear Search Binary Search
10 10 4
100 100 7
1,000 1,000 10
10,000 10,000 14
100,000 100,000 17
3.4 Binary Search Variations
Find First Occurrence
int findFirstOccurrence(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
right = mid - 1; // Continue searching in left half
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return result;
}
Visual Example:
Array: [10, 20, 20, 20, 30, 40]
Target: 20
Regular binary search might return index 1, 2, or 3
First occurrence will always return index 1
Find Last Occurrence
int findLastOccurrence(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
result = mid;
left = mid + 1; // Continue searching in right half
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return result;
}
Count Occurrences
int countOccurrences(int arr[], int n, int target) {
int first = findFirstOccurrence(arr, n, target);
if (first == -1) {
return 0; // Element not found
}
int last = findLastOccurrence(arr, n, target);
return last - first + 1;
}
int main() {
int arr[] = {10, 20, 20, 20, 30, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int count = countOccurrences(arr, n, 20);
printf("20 occurs %d times\n", count);
// Output: 20 occurs 3 times
return 0;
}
Find Insert Position
int searchInsertPosition(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left; // Position where target should be inserted
}
int main() {
int arr[] = {10, 20, 30, 50, 60};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Insert 25 at position: %d\n", searchInsertPosition(arr, n, 25));
printf("Insert 35 at position: %d\n", searchInsertPosition(arr, n, 35));
printf("Insert 70 at position: %d\n", searchInsertPosition(arr, n, 70));
return 0;
}
3.5 When to Use Binary Search
Use Binary Search when:
- Data is sorted
- Need fast searching (large datasets)
- Data doesn't change frequently
- Random access is available (arrays)
Don't use Binary Search when:
- Data is unsorted (sorting overhead)
- Small datasets (linear search is simpler)
- Data changes frequently
- Sequential access only (linked lists)
4. Introduction to Sorting
4.1 What is Sorting?
Sorting is the process of arranging elements in a specific order (ascending or descending).
Why Sort?
- Faster Searching: Enables binary search
- Data Organization: Makes data easier to understand
- Algorithm Requirements: Many algorithms require sorted input
- Data Presentation: Better user experience
- Finding Duplicates: Easier with sorted data
Real-World Examples:
- Sorting contacts alphabetically
- Arranging files by date
- Organizing products by price
- Ranking search results
- Leaderboards in games
4.2 Sorting Algorithm Categories
1. By Complexity:
- Simple: Bubble, Selection, Insertion Sort - O(n²)
- Efficient: Merge, Quick, Heap Sort - O(n log n)
- Special: Counting, Radix, Bucket Sort - O(n)
2. By Method:
- Comparison-based: Compare elements to sort
- Non-comparison: Use element properties
3. By Stability:
- Stable: Preserves relative order of equal elements
- Unstable: May change relative order
4. By Memory:
- In-place: O(1) extra space
- Out-of-place: O(n) extra space
4.3 Sorting Algorithm Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable | Method |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Exchange |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Selection |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Insertion |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide & Conquer |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide & Conquer |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Selection |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Non-comparison |
| Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes | Non-comparison |
5. Simple Sorting Algorithms
5.1 Bubble Sort
Concept
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order.
How it works:
- Compare adjacent elements
- Swap if in wrong order
- Repeat for all elements
- After each pass, largest element "bubbles" to the end
Visual Example:
Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1:
[34, 64, 25, 12, 22, 11, 90] → 64 > 34, swap
[34, 25, 64, 12, 22, 11, 90] → 64 > 25, swap
[34, 25, 12, 64, 22, 11, 90] → 64 > 12, swap
[34, 25, 12, 22, 64, 11, 90] → 64 > 22, swap
[34, 25, 12, 22, 11, 64, 90] → 64 > 11, swap
[34, 25, 12, 22, 11, 64, 90] → 64 < 90, no swap
→ 90 is in correct position!
Pass 2:
[25, 34, 12, 22, 11, 64, 90]
...continues until sorted...
Final: [11, 12, 22, 25, 34, 64, 90]
Implementation
Basic Bubble Sort:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (int j = 0; j < n - i - 1; j++) {
// Swap if element is greater than next
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Optimized Bubble Sort (with flag):
void bubbleSortOptimized(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; // Flag to detect if any swap happened
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
// If no swaps, array is sorted
if (swapped == 0) {
break;
}
}
}
Why Optimization Helps:
Nearly sorted array: [11, 12, 22, 25, 34, 64, 63]
Without optimization: 6 passes (always)
With optimization: 2 passes (stops when no swaps)
For already sorted array: [11, 12, 22, 25, 34, 64, 90]
Without: O(n²)
With: O(n) - only 1 pass!
Bubble Sort with Visualization:
void bubbleSortVisualize(int arr[], int n) {
printf("\n=== Bubble Sort Visualization ===\n");
for (int i = 0; i < n - 1; i++) {
printf("\nPass %d:\n", i + 1);
int swapped = 0;
for (int j = 0; j < n - i - 1; j++) {
printf(" Compare %d and %d: ", arr[j], arr[j + 1]);
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
printf("Swap → ");
swapped = 1;
} else {
printf("No swap → ");
}
printArray(arr, n);
}
if (swapped == 0) {
printf(" Array is sorted!\n");
break;
}
}
}
Complexity Analysis
Time Complexity:
- Best Case: O(n) - already sorted (with optimization)
- Average Case: O(n²)
- Worst Case: O(n²) - reverse sorted
Space Complexity: O(1) - in-place sorting
Comparisons and Swaps:
For array of size n:
- Comparisons: n(n-1)/2
- Swaps (worst case): n(n-1)/2
Example with n=5:
- Comparisons: 5×4/2 = 10
- Maximum swaps: 10
When to Use
Use Bubble Sort when:
- Educational purposes
- Very small datasets (n < 10)
- Nearly sorted data (with optimization)
- Simplicity is priority
Don't use when:
- Large datasets
- Performance is critical
- Production code
5.2 Selection Sort
Concept
Selection Sort divides the array into sorted and unsorted parts, repeatedly selects the minimum element from unsorted part and places it at the beginning.
How it works:
- Find minimum element in unsorted part
- Swap with first element of unsorted part
- Move boundary of sorted part
- Repeat until array is sorted
Visual Example:
Initial: [64, 25, 12, 22, 11]
↑ unsorted part
Pass 1: Find minimum (11)
[64, 25, 12, 22, 11]
↑ minimum
[11, 25, 12, 22, 64] → swap 11 and 64
↑ ↑ unsorted part
sorted
Pass 2: Find minimum (12)
[11, 25, 12, 22, 64]
↑ minimum
[11, 12, 25, 22, 64] → swap 12 and 25
↑ ↑ ↑ unsorted
sorted
Pass 3: Find minimum (22)
[11, 12, 25, 22, 64]
↑ minimum
[11, 12, 22, 25, 64] → swap 22 and 25
Pass 4: Find minimum (25)
[11, 12, 22, 25, 64]
↑ already minimum
No swap needed
Final: [11, 12, 22, 25, 64]
Implementation
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Find minimum element in unsorted part
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap minimum with first element of unsorted part
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Selection Sort with Visualization:
void selectionSortVisualize(int arr[], int n) {
printf("\n=== Selection Sort Visualization ===\n");
for (int i = 0; i < n - 1; i++) {
printf("\nPass %d: ", i + 1);
// Print sorted part
printf("Sorted[");
for (int k = 0; k < i; k++) {
printf("%d", arr[k]);
if (k < i - 1) printf(", ");
}
printf("] ");
int minIndex = i;
printf("Finding minimum in unsorted part...\n");
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
printf(" Minimum: %d at index %d\n", arr[minIndex], minIndex);
if (minIndex != i) {
printf(" Swapping %d and %d\n", arr[i], arr[minIndex]);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
} else {
printf(" Already in correct position\n");
}
printf(" Result: ");
printArray(arr, n);
}
}
Finding Maximum (Descending Order):
void selectionSortDescending(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Find maximum element in unsorted part
int maxIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIndex]) { // Changed to >
maxIndex = j;
}
}
// Swap
if (maxIndex != i) {
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
}
Complexity Analysis
Time Complexity:
- Best Case: O(n²)
- Average Case: O(n²)
- Worst Case: O(n²)
- Always O(n²) regardless of input!
Space Complexity: O(1) - in-place sorting
Comparisons and Swaps:
For array of size n:
- Comparisons: n(n-1)/2 (always)
- Swaps: O(n) - maximum n-1 swaps
Advantage: Minimum number of swaps!
Comparison with Bubble Sort:
Array: [5, 4, 3, 2, 1]
Bubble Sort:
- Comparisons: 10
- Swaps: 10
Selection Sort:
- Comparisons: 10
- Swaps: 2 (only swap 5↔1, then 4↔2)
→ Selection Sort better when swaps are expensive!
Stability Issue
Selection Sort is NOT stable:
Input: [4a, 3, 4b, 2]
Output: [2, 3, 4b, 4a] ← Order of 4a and 4b changed!
Why? When we swap 4a with 2, 4b comes before 4a
When to Use
Use Selection Sort when:
- Swaps are expensive (writing to flash memory)
- Small datasets
- Memory writes must be minimized
- Simplicity needed
Don't use when:
- Stability required
- Large datasets
- Performance critical
5.3 Insertion Sort
Concept
Insertion Sort builds the final sorted array one item at a time by inserting each element into its correct position.
Analogy: Like sorting playing cards in your hand:
- Pick one card at a time
- Insert it into correct position among sorted cards
- Shift other cards to make space
How it works:
- Start with second element
- Compare with elements in sorted part (left side)
- Shift larger elements to the right
- Insert element in correct position
- Repeat for all elements
Visual Example:
Initial: [12, 11, 13, 5, 6]
Pass 1: Insert 11
[12, 11, 13, 5, 6]
↑ ↑
sorted | to insert
12 > 11, shift 12 right
[11, 12, 13, 5, 6]
↑ ↑
sorted
Pass 2: Insert 13
[11, 12, 13, 5, 6]
↑ ↑ ↑
sorted | to insert
13 > 12, already in position
[11, 12, 13, 5, 6]
↑ ↑ ↑
sorted
Pass 3: Insert 5
[11, 12, 13, 5, 6]
↑ ↑ ↑ ↑
sorted | to insert
13 > 5, shift right → [11, 12, 13, 13, 6]
12 > 5, shift right → [11, 12, 12, 13, 6]
11 > 5, shift right → [11, 11, 12, 13, 6]
Insert 5 at position 0 → [5, 11, 12, 13, 6]
Pass 4: Insert 6
[5, 11, 12, 13, 6]
↑ ↑ ↑ ↑ ↑
sorted | to insert
13 > 6, shift right → [5, 11, 12, 13, 13]
12 > 6, shift right → [5, 11, 12, 12, 13]
11 > 6, shift right → [5, 11, 11, 12, 13]
5 < 6, insert at position 1 → [5, 6, 11, 12, 13]
Final: [5, 6, 11, 12, 13]
Implementation
Basic Insertion Sort:
#include <stdio.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // Element to be inserted
int j = i - 1;
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key at correct position
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
insertionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Insertion Sort with Visualization:
void insertionSortVisualize(int arr[], int n) {
printf("\n=== Insertion Sort Visualization ===\n");
printf("Initial: ");
printArray(arr, n);
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
printf("\nPass %d: Insert %d\n", i, key);
printf(" Sorted part: [");
for (int k = 0; k < i; k++) {
printf("%d", arr[k]);
if (k < i - 1) printf(", ");
}
printf("]\n");
int shifts = 0;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
shifts++;
}
arr[j + 1] = key;
printf(" Shifts: %d\n", shifts);
printf(" Result: ");
printArray(arr, n);
}
}
Descending Order:
void insertionSortDescending(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Change condition to arr[j] < key
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Binary Insertion Sort (Optimization):
// Find position using binary search
int binarySearch(int arr[], int item, int low, int high) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == item) {
return mid + 1;
}
else if (arr[mid] < item) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return low;
}
void binaryInsertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
// Find position using binary search
int pos = binarySearch(arr, key, 0, i - 1);
// Shift elements
for (int j = i - 1; j >= pos; j--) {
arr[j + 1] = arr[j];
}
// Insert key
arr[pos] = key;
}
}
Insertion Sort for Linked List:
struct Node {
int data;
struct Node *next;
};
void sortedInsert(struct Node **head, struct Node *newNode) {
// If list is empty or new node should be first
if (*head == NULL || (*head)->data >= newNode->data) {
newNode->next = *head;
*head = newNode;
return;
}
// Find position to insert
struct Node *current = *head;
while (current->next != NULL && current->next->data < newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
void insertionSortList(struct Node **head) {
struct Node *sorted = NULL;
struct Node *current = *head;
while (current != NULL) {
struct Node *next = current->next;
sortedInsert(&sorted, current);
current = next;
}
*head = sorted;
}
Complexity Analysis
Time Complexity:
- Best Case: O(n) - already sorted
- Average Case: O(n²)
- Worst Case: O(n²) - reverse sorted
Space Complexity: O(1) - in-place sorting
Detailed Analysis:
Best Case (sorted): [1, 2, 3, 4, 5]
- Comparisons: n-1 (each element compared once)
- Shifts: 0
- Time: O(n)
Worst Case (reverse sorted): [5, 4, 3, 2, 1]
- Comparisons: 1+2+3+...+(n-1) = n(n-1)/2
- Shifts: Same as comparisons
- Time: O(n²)
Average Case (random):
- Comparisons: ~n²/4
- Shifts: ~n²/4
- Time: O(n²)
Performance on Different Inputs:
void testInsertionSort() {
// Already sorted
int sorted[] = {1, 2, 3, 4, 5};
printf("Sorted array: Fast! O(n)\n");
// Reverse sorted
int reverse[] = {5, 4, 3, 2, 1};
printf("Reverse array: Slow! O(n²)\n");
// Nearly sorted
int nearlySorted[] = {1, 2, 4, 3, 5};
printf("Nearly sorted: Fast! O(n)\n");
// Few elements out of place
int fewMoves[] = {2, 1, 3, 4, 5};
printf("Few out of place: Fast!\n");
}
Advantages
- Simple implementation
- Stable - preserves relative order
- In-place - O(1) extra space
- Adaptive - O(n) for nearly sorted data
- Online - can sort as data arrives
Stability Example:
Input: [4a, 3, 4b, 2]
Output: [2, 3, 4a, 4b] ← Order preserved!
When to Use
Use Insertion Sort when:
- Small datasets (n < 50)
- Nearly sorted data
- Stability required
- Online sorting (data arriving in real-time)
- Linked lists (no shifting overhead)
Don't use when:
- Large datasets
- Random data
- Performance critical
Real-World Applications:
- Sorting small files
- Hybrid sorting (used in TimSort)
- Online algorithms
- Sorting linked lists
6. Efficient Sorting Algorithms
6.1 Merge Sort
Concept
Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.
Divide and Conquer Strategy:
- Divide: Split array into two halves
- Conquer: Recursively sort each half
- Combine: Merge the two sorted halves
Visual Example:
Initial Array: [38, 27, 43, 3, 9, 82, 10]
DIVIDE Phase:
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10]
MERGE Phase:
[38] [27] [43] [3] [9] [82] [10]
\ / \ / \ / |
[27, 38] [3, 43] [9, 82] [10]
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]
Implementation
Merge Sort Algorithm:
#include <stdio.h>
#include <stdlib.h>
// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays
int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));
// Copy data to temporary arrays
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays back
int i = 0; // Initial index of left subarray
int j = 0; // Initial index of right subarray
int k = left; // Initial index of merged array
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
// Main merge sort function
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first half
mergeSort(arr, left, mid);
// Sort second half
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Merge Sort with Visualization:
void mergeSortVisualize(int arr[], int left, int right, int depth) {
if (left < right) {
// Print indentation based on recursion depth
for (int i = 0; i < depth; i++) printf(" ");
printf("Divide: [");
for (int i = left; i <= right; i++) {
printf("%d", arr[i]);
if (i < right) printf(", ");
}
printf("]\n");
int mid = left + (right - left) / 2;
mergeSortVisualize(arr, left, mid, depth + 1);
mergeSortVisualize(arr, mid + 1, right, depth + 1);
merge(arr, left, mid, right);
// Print result after merge
for (int i = 0; i < depth; i++) printf(" ");
printf("Merge: [");
for (int i = left; i <= right; i++) {
printf("%d", arr[i]);
if (i < right) printf(", ");
}
printf("]\n");
}
}
Iterative Merge Sort:
void mergeSortIterative(int arr[], int n) {
// Start with merge subarrays of size 1, then 2, 4, 8, ...
for (int currSize = 1; currSize < n; currSize *= 2) {
// Pick starting index of left sub array
for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
// Find ending point of left subarray
int mid = leftStart + currSize - 1;
// Find ending point of right subarray
int rightEnd = (leftStart + 2 * currSize - 1 < n - 1) ?
leftStart + 2 * currSize - 1 : n - 1;
// Merge subarrays
if (mid < rightEnd) {
merge(arr, leftStart, mid, rightEnd);
}
}
}
}
Complexity Analysis
Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
- Always O(n log n)!
Space Complexity: O(n) - requires temporary arrays
Why O(n log n)?
Tree height: log₂(n) levels
Work at each level: n comparisons/copies
Total work = height × work per level
= log₂(n) × n
= O(n log n)
Example with n=8:
Level 0: [8 elements] → n operations
Level 1: [4,4] → n operations (4+4)
Level 2: [2,2,2,2] → n operations (2+2+2+2)
Level 3: [1,1,1,1,1,1,1,1] → n operations
Total levels = log₂(8) = 3
Total operations = 3n = O(n log n)
Comparison with Simple Sorts:
n=1,000:
- Insertion Sort: ~500,000 operations
- Merge Sort: ~10,000 operations
→ 50x faster!
n=1,000,000:
- Insertion Sort: ~500 billion operations
- Merge Sort: ~20 million operations
→ 25,000x faster!
Advantages and Disadvantages
Advantages:
- Guaranteed O(n log n) - always efficient
- Stable - preserves relative order
- Predictable - no worst-case scenarios
- Good for linked lists - O(1) space possible
- Parallelizable - can sort halves independently
Disadvantages:
- O(n) space - requires temporary storage
- Not in-place - not memory efficient
- Overhead - slower than Quick Sort in practice
- Not adaptive - doesn't benefit from sorted data
When to Use
Use Merge Sort when:
- Guaranteed O(n log n) required
- Stability is important
- Working with linked lists
- External sorting (large files)
- Parallel processing available
Don't use when:
- Memory is limited
- In-place sorting required
- Small datasets (overhead not worth it)
6.2 Quick Sort
Concept
Quick Sort is a divide-and-conquer algorithm that picks a pivot element and partitions the array around it, then recursively sorts the subarrays.
How it works:
- Choose Pivot: Select an element as pivot
- Partition: Rearrange so elements < pivot are left, elements > pivot are right
- Recursively sort: Sort left and right subarrays
Visual Example:
Initial: [10, 80, 30, 90, 40, 50, 70]
Pick pivot = 70 (last element)
Partition:
[10, 30, 40, 50] 70 [80, 90]
← less than 70 greater than 70 →
Recursively sort left: [10, 30, 40, 50]
Pick pivot = 50
[10, 30, 40] 50 []
Recursively sort right: [80, 90]
Pick pivot = 90
[80] 90 []
Final: [10, 30, 40, 50, 70, 80, 90]
Partitioning Process:
Array: [10, 80, 30, 90, 40, 50, 70]
Pivot: 70 (last element)
i = -1 (tracks position of smaller elements)
j = 0 (scans through array)
j=0: arr[0]=10 < 70 → swap arr[++i] with arr[j]
[10, 80, 30, 90, 40, 50, 70]
i
j=1: arr[1]=80 > 70 → no swap
[10, 80, 30, 90, 40, 50, 70]
i
j=2: arr[2]=30 < 70 → swap arr[++i] with arr[j]
[10, 30, 80, 90, 40, 50, 70]
i
j=3: arr[3]=90 > 70 → no swap
j=4: arr[4]=40 < 70 → swap arr[++i] with arr[j]
[10, 30, 40, 90, 80, 50, 70]
i
j=5: arr[5]=50 < 70 → swap arr[++i] with arr[j]
[10, 30, 40, 50, 80, 90, 70]
i
Finally: Place pivot at i+1
[10, 30, 40, 50, 70, 90, 80]
↑
pivot in place
Implementation
Quick Sort with Last Element as Pivot:
#include <stdio.h>
// Swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than pivot
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
// Place pivot in correct position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// Quick sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
// Partition index
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Quick Sort with Middle Element as Pivot:
int partitionMiddle(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
int pivot = arr[mid];
// Move pivot to end
swap(&arr[mid], &arr[high]);
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
Quick Sort with Random Pivot:
#include <stdlib.h>
#include <time.h>
int partitionRandom(int arr[], int low, int high) {
// Generate random pivot index
srand(time(NULL));
int randomIndex = low + rand() % (high - low + 1);
// Move pivot to end
swap(&arr[randomIndex], &arr[high]);
return partition(arr, low, high);
}
void quickSortRandom(int arr[], int low, int high) {
if (low < high) {
int pi = partitionRandom(arr, low, high);
quickSortRandom(arr, low, pi - 1);
quickSortRandom(arr, pi + 1, high);
}
}
Quick Sort with Visualization:
void quickSortVisualize(int arr[], int low, int high, int depth) {
if (low < high) {
// Print indentation
for (int i = 0; i < depth; i++) printf(" ");
printf("Sorting: [");
for (int i = low; i <= high; i++) {
printf("%d", arr[i]);
if (i < high) printf(", ");
}
printf("] Pivot=%d\n", arr[high]);
int pi = partition(arr, low, high);
// Print result
for (int i = 0; i < depth; i++) printf(" ");
printf("Result: [");
for (int i = low; i <= high; i++) {
if (i == pi) printf("*");
printf("%d", arr[i]);
if (i == pi) printf("*");
if (i < high) printf(", ");
}
printf("]\n");
quickSortVisualize(arr, low, pi - 1, depth + 1);
quickSortVisualize(arr, pi + 1, high, depth + 1);
}
}
Three-Way Partitioning (for duplicates):
void quickSort3Way(int arr[], int low, int high) {
if (low >= high) return;
int pivot = arr[high];
int i = low;
int lt = low; // Elements < pivot
int gt = high; // Elements > pivot
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[lt++], &arr[i++]);
}
else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt--]);
}
else {
i++;
}
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
Complexity Analysis
Time Complexity:
- Best Case: O(n log n) - balanced partitions
- Average Case: O(n log n)
- Worst Case: O(n²) - unbalanced partitions
Space Complexity: O(log n) - recursion stack
Best Case (Balanced Partition):
Each partition divides array in half
[8 elements]
/ \
[4] [4]
/ \ / \
[2] [2] [2] [2]
/ \ / \ / \ / \
[1][1][1][1] [1][1][1][1]
Height = log₂(n)
Work per level = n
Total = O(n log n)
Worst Case (Unbalanced Partition):
Sorted or reverse sorted with bad pivot choice
[5, 4, 3, 2, 1] pivot = 1
↓
[1] [5, 4, 3, 2] pivot = 2
↓
[2] [5, 4, 3] pivot = 3
↓
[3] [5, 4]
↓
[4] [5]
Height = n
Work = n + (n-1) + (n-2) + ... + 1
= n(n+1)/2
= O(n²)
Avoiding Worst Case:
- Random Pivot: Makes worst case unlikely
- Median-of-Three: Use median of first, middle, last
- Three-Way Partition: Handle duplicates efficiently
Advantages and Disadvantages
Advantages:
- Fast in practice - usually faster than Merge Sort
- In-place - O(log n) space only
- Cache-friendly - good locality of reference
- Parallelizable - can sort partitions independently
Disadvantages:
- Unstable - doesn't preserve relative order
- O(n²) worst case - rare but possible
- Not adaptive - doesn't benefit from sorted data
- Recursive - stack overflow for deep recursion
Pivot Selection Strategies
1. Last Element (Simple):
int pivot = arr[high];
- Simple but vulnerable to sorted input
2. First Element:
int pivot = arr[low];
- Same issue as last element
3. Middle Element:
int mid = low + (high - low) / 2;
int pivot = arr[mid];
- Better for sorted input
4. Random Element:
int randomIndex = low + rand() % (high - low + 1);
int pivot = arr[randomIndex];
- Probabilistically avoids worst case
5. Median-of-Three:
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid])
swap(&arr[low], &arr[mid]);
if (arr[low] > arr[high])
swap(&arr[low], &arr[high]);
if (arr[mid] > arr[high])
swap(&arr[mid], &arr[high]);
return mid;
}
- Best practical choice
When to Use
Use Quick Sort when:
- Average case performance matters
- Memory is limited (in-place)
- Cache performance important
- Large datasets
- Stability not required
Don't use when:
- Worst case must be avoided
- Stability required
- Small datasets
- Stack space is limited
Comparison with Merge Sort:
Quick Sort Merge Sort
Time (avg): O(n log n) O(n log n)
Time (worst): O(n²) O(n log n)
Space: O(log n) O(n)
Stable: No Yes
In-place: Yes No
Cache: Better Worse
Practice: Faster Slower
7. Comparison of Sorting Algorithms
7.1 Performance Summary
// Test all sorting algorithms
#include <time.h>
void testSortingAlgorithms() {
int sizes[] = {100, 1000, 10000};
for (int s = 0; s < 3; s++) {
int n = sizes[s];
printf("\n=== Array Size: %d ===\n", n);
// Test each algorithm
int *arr = generateRandomArray(n);
clock_t start = clock();
bubbleSort(arr, n);
clock_t end = clock();
printf("Bubble Sort: %.4f seconds\n",
(double)(end - start) / CLOCKS_PER_SEC);
// Repeat for other algorithms...
free(arr);
}
}
7.2 When to Use Which Algorithm
Decision Tree:
Is n < 50?
├─ Yes → Use Insertion Sort (simple, fast for small n)
└─ No → Is stability required?
├─ Yes → Use Merge Sort
└─ No → Is memory limited?
├─ Yes → Use Quick Sort (in-place)
└─ No → Use Merge Sort (guaranteed O(n log n))
By Data Characteristics:
Nearly sorted →Insertion Sort (O(n))
Reverse sorted → Any O(n log n) algorithm
Random data → Quick Sort (fastest in practice)
Many duplicates → Quick Sort 3-way
Small data → Insertion Sort
Large data → Merge Sort or Quick Sort
Linked list → Merge Sort (O(1) space)
Stability needed → Merge Sort or Insertion Sort
Memory limited → Quick Sort or Heap Sort
7.3 Hybrid Sorting Approaches
IntroSort (Introspective Sort):
void introSort(int arr[], int low, int high, int depthLimit) {
int n = high - low + 1;
// Use Insertion Sort for small arrays
if (n < 16) {
insertionSort(arr + low, n);
return;
}
// Switch to Heap Sort if recursion too deep
if (depthLimit == 0) {
heapSort(arr + low, n);
return;
}
// Use Quick Sort
int pi = partition(arr, low, high);
introSort(arr, low, pi - 1, depthLimit - 1);
introSort(arr, pi + 1, high, depthLimit - 1);
}
// Wrapper function
void sort(int arr[], int n) {
int depthLimit = 2 * log2(n);
introSort(arr, 0, n - 1, depthLimit);
}
TimSort (Python's default sort):
- Combination of Merge Sort and Insertion Sort
- Identifies natural runs in data
- Uses Insertion Sort for small runs
- Merges runs using Merge Sort
8. Practical Applications
8.1 Search and Sort Combined
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Student structure
typedef struct {
int id;
char name[50];
float gpa;
} Student;
// Compare functions for sorting
int compareByID(const void *a, const void *b) {
return ((Student*)a)->id - ((Student*)b)->id;
}
int compareByGPA(const void *a, const void *b) {
float diff = ((Student*)b)->gpa - ((Student*)a)->gpa;
return (diff > 0) ? 1 : (diff < 0) ? -1 : 0;
}
int compareByName(const void *a, const void *b) {
return strcmp(((Student*)a)->name, ((Student*)b)->name);
}
// Binary search by ID
int searchByID(Student students[], int n, int targetID) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (students[mid].id == targetID) {
return mid;
}
else if (students[mid].id < targetID) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
// Linear search by name
int searchByName(Student students[], int n, const char *name) {
for (int i = 0; i < n; i++) {
if (strcmp(students[i].name, name) == 0) {
return i;
}
}
return -1;
}
// Print students
void printStudents(Student students[], int n) {
printf("\n%-10s %-20s %-8s\n", "ID", "Name", "GPA");
printf("----------------------------------------\n");
for (int i = 0; i < n; i++) {
printf("%-10d %-20s %.2f\n",
students[i].id, students[i].name, students[i].gpa);
}
}
int main() {
Student students[] = {
{1003, "Alice Johnson", 3.8},
{1001, "Bob Smith", 3.5},
{1005, "Charlie Brown", 3.9},
{1002, "Diana Prince", 3.7},
{1004, "Eve Wilson", 3.6}
};
int n = sizeof(students) / sizeof(students[0]);
printf("=== Student Database ===\n");
printf("\nOriginal Data:");
printStudents(students, n);
// Sort by ID
qsort(students, n, sizeof(Student), compareByID);
printf("\nSorted by ID:");
printStudents(students, n);
// Search by ID
int targetID = 1003;
int index = searchByID(students, n, targetID);
if (index != -1) {
printf("\nStudent with ID %d: %s (GPA: %.2f)\n",
targetID, students[index].name, students[index].gpa);
}
// Sort by GPA (descending)
qsort(students, n, sizeof(Student), compareByGPA);
printf("\nSorted by GPA (highest first):");
printStudents(students, n);
// Sort by Name
qsort(students, n, sizeof(Student), compareByName);
printf("\nSorted by Name:");
printStudents(students, n);
return 0;
}
8.2 Finding Kth Largest Element
// Partition function (same as Quick Sort)
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Quick Select algorithm - O(n) average time
int findKthLargest(int arr[], int low, int high, int k) {
if (low == high) {
return arr[low];
}
int pi = partition(arr, low, high);
int length = high - pi + 1;
if (length == k) {
return arr[pi];
}
else if (length > k) {
return findKthLargest(arr, pi + 1, high, k);
}
else {
return findKthLargest(arr, low, pi - 1, k - length);
}
}
int main() {
int arr[] = {3, 2, 1, 5, 6, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
int result = findKthLargest(arr, 0, n - 1, k);
printf("%dth largest element: %d\n", k, result);
// Output: 2nd largest element: 5
return 0;
}
8.3 Merge Two Sorted Arrays
#include <stdio.h>
#include <stdlib.h>
int* mergeSortedArrays(int arr1[], int n1, int arr2[], int n2) {
int *result = (int*)malloc((n1 + n2) * sizeof(int));
int i = 0, j = 0, k = 0;
// Merge while both arrays have elements
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// Copy remaining elements from arr1
while (i < n1) {
result[k++] = arr1[i++];
}
// Copy remaining elements from arr2
while (j < n2) {
result[k++] = arr2[j++];
}
return result;
}
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int *merged = mergeSortedArrays(arr1, n1, arr2, n2);
printf("Merged array: ");
for (int i = 0; i < n1 + n2; i++) {
printf("%d ", merged[i]);
}
printf("\n");
free(merged);
return 0;
}
8.4 Finding Median
// Find median of unsorted array
double findMedian(int arr[], int n) {
// Sort the array first
quickSort(arr, 0, n - 1);
// Find median
if (n % 2 == 0) {
// Even number of elements - average of two middle
return (arr[n/2 - 1] + arr[n/2]) / 2.0;
} else {
// Odd number of elements - middle element
return arr[n/2];
}
}
int main() {
int arr1[] = {3, 1, 4, 1, 5, 9, 2};
int arr2[] = {6, 5, 3, 5, 8, 9};
printf("Median of arr1: %.1f\n", findMedian(arr1, 7));
printf("Median of arr2: %.1f\n", findMedian(arr2, 6));
return 0;
}
8.5 Removing Duplicates from Sorted Array
int removeDuplicates(int arr[], int n) {
if (n == 0 || n == 1) {
return n;
}
int j = 0; // Index for unique elements
for (int i = 0; i < n - 1; i++) {
if (arr[i] != arr[i + 1]) {
arr[j++] = arr[i];
}
}
arr[j++] = arr[n - 1]; // Add last element
return j; // New length
}
int main() {
int arr[] = {1, 1, 2, 2, 2, 3, 4, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int newLength = removeDuplicates(arr, n);
printf("After removing duplicates: ");
for (int i = 0; i < newLength; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
8.6 Finding Intersection of Two Arrays
void findIntersection(int arr1[], int n1, int arr2[], int n2) {
// Sort both arrays first
quickSort(arr1, 0, n1 - 1);
quickSort(arr2, 0, n2 - 1);
printf("Intersection: ");
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
i++;
}
else if (arr1[i] > arr2[j]) {
j++;
}
else {
// Elements are equal
printf("%d ", arr1[i]);
i++;
j++;
}
}
printf("\n");
}
int main() {
int arr1[] = {1, 3, 4, 5, 7};
int arr2[] = {2, 3, 5, 6};
findIntersection(arr1, 5, arr2, 4);
// Output: Intersection: 3 5
return 0;
}
8.7 Sorting Strings
#include <stdio.h>
#include <string.h>
void sortStrings(char *arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (strcmp(arr[j], arr[j + 1]) > 0) {
// Swap pointers
char *temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
char *fruits[] = {"Banana", "Apple", "Orange", "Mango", "Grape"};
int n = 5;
printf("Original: ");
for (int i = 0; i < n; i++) {
printf("%s ", fruits[i]);
}
printf("\n");
sortStrings(fruits, n);
printf("Sorted: ");
for (int i = 0; i < n; i++) {
printf("%s ", fruits[i]);
}
printf("\n");
return 0;
}