What is Linear Search?
Linear search is a simple search algorithm that checks each element in the list one by one until
the desired element (called the key or target) is found or the list ends.
Linear Search Algorithm (Step-by-step)
1. Start from the first element of the array.
2. Compare the current element with the target value.
3. If they are equal, return the index (position).
4. If not, move to the next element.
5. Repeat steps 2–4 until the end of the array.
6. If the end is reached and the target is not found, return -1 (or say "not found").
C Program for Linear Search
#include <stdio.h>
int linearSearch(int arr[], int n, int key) {
for(int i = 0; i < n; i++) {
if(arr[i] == key) {
return i; // Key found at index i
return -1; // Key not found
int main() {
int arr[100], n, key, result;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
printf("Enter the element to search: ");
scanf("%d", &key);
result = linearSearch(arr, n, key);
if(result != -1)
printf("Element %d found at position %d\n", key, result + 1); // +1 for human-readable
index
else
printf("Element %d not found in the array\n", key);
return 0;
Example Problem
Problem:
You are given the array:
arr = [15, 30, 25, 10, 50]
Search for the element 25.
Solution (Step-by-step):
• Check index 0 → 15 ≠ 25
• Check index 1 → 30 ≠ 25
• Check index 2 → 25 == 25 → Found!
Output:
Element 25 found at position 3
Summary
• Time complexity: O(n)
• Best case: Element at the beginning (fast)
• Worst case: Element at the end or not present at all
What is Binary Search?
Binary Search is a fast searching algorithm that works only on sorted arrays. It repeatedly
divides the search interval in half until the element is found or the interval is empty.
Binary Search Algorithm (Step-by-step)
1. Set two pointers: low = 0 and high = n - 1.
2. Repeat until low is less than or equal to high:
o Find mid = (low + high) / 2
o If arr[mid] == key, return mid (element found).
o If arr[mid] < key, search in the right half (low = mid + 1)
o If arr[mid] > key, search in the left half (high = mid - 1)
3. If not found, return -1.
C Program for Binary Search
#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == key)
return mid; // Element found
else if(arr[mid] < key)
low = mid + 1; // Search right half
else
high = mid - 1; // Search left half
return -1; // Element not found
int main() {
int arr[100], n, key, result;
printf("Enter number of elements (sorted): ");
scanf("%d", &n);
printf("Enter %d sorted elements:\n", n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
printf("Enter the element to search: ");
scanf("%d", &key);
result = binarySearch(arr, n, key);
if(result != -1)
printf("Element %d found at position %d\n", key, result + 1);
else
printf("Element %d not found in the array\n", key);
return 0;
Example Problem (Step-by-step)
Given:
Sorted array: arr = [10, 20, 30, 40, 50, 60, 70]
Search key = 50
Step-by-step Binary Search Process:
Step low high mid = (low + high)/2 arr[mid] Comparison Action
1 0 6 (0+6)/2 = 3 40 50 > 40 Search right
2 4 6 (4+6)/2 = 5 60 50 < 60 Search left
3 4 4 (4+4)/2 = 4 50 Match! Return index 4
Output:
Element 50 found at position 5 (because index 4 + 1 = position 5)
Summary
• Binary Search is fast: Time complexity = O(log n)
• Requires a sorted array
• Divides the problem size in half every time
What is Selection Sort?
Selection Sort is a simple sorting algorithm. It repeatedly selects the smallest (or largest)
element from the unsorted part and puts it at the beginning.
Selection Sort Algorithm (Step-by-Step)
1. Start from the first element.
2. Find the smallest element in the unsorted portion.
3. Swap it with the first element of the unsorted portion.
4. Move to the next position and repeat until the array is sorted.
C Program for Selection Sort
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for(i = 0; i < n-1; i++) {
minIndex = i;
for(j = i+1; j < n; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
// Swap arr[i] and arr[minIndex]
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
int main() {
int arr[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
selectionSort(arr, n);
printf("Sorted array:\n");
for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
Example Problem
Given array:
arr = [64, 25, 12, 22, 11]
Let’s sort this using Selection Sort (Step-by-step):
Pass Unsorted Part Smallest Swap Result After Swap
1 [64, 25, 12, 22, 11] 11 Swap 64 and 11 [11, 25, 12, 22, 64]
2 [25, 12, 22, 64] 12 Swap 25 and 12 [11, 12, 25, 22, 64]
3 [25, 22, 64] 22 Swap 25 and 22 [11, 12, 22, 25, 64]
4 [25, 64] 25 Already in correct place [11, 12, 22, 25, 64]
5 [64] - Already sorted [11, 12, 22, 25, 64]
Summary
• Time complexity: O(n²)
• Simple but inefficient for large data
• Works well for small datasets or educational purposes
Here is a simple explanation, algorithm, C program, and a step-by-step example for
Quick Sort.
What is Quick Sort?
Quick Sort is a divide and conquer sorting algorithm.
It picks a pivot element, then partitions the array so that:
• All elements less than pivot come before it,
• All elements greater than pivot come after it.
It then recursively applies the same process to the left and right subarrays.
Quick Sort Algorithm (Step-by-Step)
1. Choose a pivot (e.g., first element).
2. Partition the array:
o Move elements smaller than pivot to the left.
o Move elements greater than pivot to the right.
3. Recursively apply quicksort to:
o Left subarray (elements before pivot)
o Right subarray (elements after pivot)
4. Repeat until the base case is reached (0 or 1 element).
C Program for Quick Sort
#include <stdio.h>
void quickSort(int arr[], int low, int high) {
if (low < high) {
int i = low, j = high;
int pivot = arr[low]; // Choosing first element as pivot
int temp;
while (i < j) {
while (arr[i] <= pivot && i < high) i++;
while (arr[j] > pivot) j--;
if (i < j) {
// Swap arr[i] and arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Swap pivot with arr[j]
temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
// Recursively sort left and right parts
quickSort(arr, low, j - 1);
quickSort(arr, j + 1, high);
}
}
int main() {
int arr[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1);
printf("Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
Example Problem
Given array:
arr = [30, 10, 50, 20, 60, 40]
Let's sort using Quick Sort:
Step 1: Choose Pivot = 30
Partition:
• Left of 30 → [10, 20]
• Right of 30 → [50, 60, 40]
Now: [10, 20, 30, 50, 60, 40]
Step 2: QuickSort Left Part [10, 20]
Pivot = 10
Partition:
Left = []
Right = [20]
Now: [10, 20]
Step 3: QuickSort Right Part [50, 60, 40]
Pivot = 50
Partition:
Left = [40]
Right = [60]
Now: [40, 50, 60]
Final Sorted Array:
[10, 20, 30, 40, 50, 60]
Summary
• Time Complexity:
o Average: O(n log n)
o Worst-case: O(n²) (when pivot is poorly chosen)
• Efficient and fast for large datasets
• In-place sort, no need for extra memory
Would you like a visual diagram or Python version as well?
