Unit 1: Introduction & Arrays

Python Implementation

Python
def insert_at_position(array, size, capacity, position, value):
    """Insert 'value' at 'position' in array. Returns new size.
    
    Industry parallel: IRCTC inserts a new booking into the waitlist
    at the correct priority position — same shift-right logic.
    """
    # Edge case: array is full
    if size >= capacity:
        print("Error: Array is full. Cannot insert.")
        return size
    
    # Edge case: invalid position
    if position < 0 or position > size:
        print(f"Error: Position {position} out of range [0, {size}]")
        return size
    
    # Step 1: Shift elements right from end to position
    # This is the expensive part — O(n) in worst case
    for i in range(size, position, -1):
        array[i] = array[i - 1]
    
    # Step 2: Place the new value at position
    array[position] = value
    
    return size + 1


def delete_at_position(array, size, position):
    """Delete element at 'position'. Returns new size.
    
    Industry parallel: When a passenger cancels, IRCTC shifts 
    all waitlisted passengers up by one position.
    """
    # Edge case: empty array
    if size == 0:
        print("Error: Array is empty.")
        return size
    
    # Edge case: invalid position
    if position < 0 or position >= size:
        print(f"Error: Position {position} out of range [0, {size-1}]")
        return size
    
    # Step 1: Shift elements left from position+1 to end
    for i in range(position, size - 1):
        array[i] = array[i + 1]
    
    return size - 1


# === Driver Code ===
capacity = 10
arr = [0] * capacity
arr[0], arr[1], arr[2], arr[3], arr[4] = 10, 20, 30, 40, 50
size = 5

print("Original:", arr[:size])

# Insert 25 at position 2
size = insert_at_position(arr, size, capacity, 2, 25)
print("After insert 25 at pos 2:", arr[:size])

# Delete element at position 0
size = delete_at_position(arr, size, 0)
print("After delete at pos 0:", arr[:size])

C Implementation

C
#include <stdio.h>

int insertAt(int arr[], int size, int capacity, int pos, int val) {
    if (size >= capacity) { printf("Error: Array full\n"); return size; }
    if (pos < 0 || pos > size) { printf("Error: Invalid position\n"); return size; }
    for (int i = size; i > pos; i--)
        arr[i] = arr[i-1];    // Shift right
    arr[pos] = val;
    return size + 1;
}

int deleteAt(int arr[], int size, int pos) {
    if (size == 0) { printf("Error: Array empty\n"); return size; }
    if (pos < 0 || pos >= size) { printf("Error: Invalid position\n"); return size; }
    for (int i = pos; i < size-1; i++)
        arr[i] = arr[i+1];    // Shift left
    return size - 1;
}

int main() {
    int arr[10] = {10,20,30,40,50}, size = 5;
    size = insertAt(arr, size, 10, 2, 25);
    printf("After insert: ");
    for(int i=0;i<size;i++) printf("%d ", arr[i]);
    size = deleteAt(arr, size, 0);
    printf("\nAfter delete: ");
    for(int i=0;i<size;i++) printf("%d ", arr[i]);
    return 0;
}

Python Implementation

Python
def linear_search(array, size, key):
    """Search for 'key' by checking every element sequentially.
    
    Time: O(n) — must check each element in worst case.
    Industry use: Searching unsorted logs, small datasets.
    """
    for index in range(size):
        if array[index] == key:
            return index    # Found at this index
    return -1              # Not found


def binary_search(array, size, key):
    """Search for 'key' in a SORTED array using divide-and-conquer.
    
    Time: O(log n) — halves search space each step.
    Industry use: Flipkart searching 150M products, database index lookups.
    
    PREREQUISITE: Array MUST be sorted. If unsorted, results are WRONG.
    """
    low = 0
    high = size - 1
    
    while low <= high:
        # Safe midpoint calculation (avoids integer overflow in C/Java)
        mid = low + (high - low) // 2
        
        if array[mid] == key:
            return mid         # Found!
        elif array[mid] < key:
            low = mid + 1      # Key is in right half
        else:
            high = mid - 1     # Key is in left half
    
    return -1              # Not found


# === Driver Code ===
data = [11, 22, 33, 44, 55, 66, 77, 88, 99]

# Linear search — works on any array
print("Linear search for 55:", linear_search(data, len(data), 55))
print("Linear search for 42:", linear_search(data, len(data), 42))

# Binary search — requires sorted array
print("Binary search for 77:", binary_search(data, len(data), 77))
print("Binary search for 42:", binary_search(data, len(data), 42))

Step 1: low=0, high=8, mid=4 → arr[4]=55 < 77 → low=5
Step 2: low=5, high=8, mid=6 → arr[6]=77 == 77 → FOUND at index 6 ✓

Only 2 comparisons to search 9 elements! Linear would need 7.

C Implementation

C
#include <stdio.h>

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (arr[i] == key) return i;
    return -1;
}

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // Overflow-safe
        if (arr[mid] == key) return mid;
        else if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {11,22,33,44,55,66,77,88,99};
    printf("Linear(55): %d\n", linearSearch(arr, 9, 55));
    printf("Binary(77): %d\n", binarySearch(arr, 9, 77));
    return 0;
}

Python
def bubble_sort(array, size):
    """Sort array using repeated adjacent-element swaps.
    
    Time: O(n²) average/worst, O(n) best (already sorted with flag).
    Space: O(1) — in-place.
    Stable: Yes — equal elements maintain relative order.
    """
    for pass_num in range(size - 1):
        swapped = False    # Optimization: early termination
        
        for j in range(size - 1 - pass_num):
            if array[j] > array[j + 1]:
                array[j], array[j+1] = array[j+1], array[j]
                swapped = True
        
        if not swapped:       # Array is already sorted
            break

data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data, len(data))
print("Sorted:", data)

C
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
                swapped = 1;
            }
        if (!swapped) break;
    }
}

Python
def selection_sort(array, size):
    """Find minimum in unsorted part, swap to front. Repeat.
    
    Time: O(n²) always — no best-case advantage.
    Space: O(1). Unstable. But only O(n) swaps — useful when writes are costly.
    """
    for i in range(size - 1):
        min_index = i           # Assume current is minimum
        
        for j in range(i + 1, size):
            if array[j] < array[min_index]:
                min_index = j   # Found a smaller element
        
        # Only swap if minimum is not already in position
        if min_index != i:
            array[i], array[min_index] = array[min_index], array[i]

data = [64, 25, 12, 22, 11]
selection_sort(data, len(data))
print("Sorted:", data)

C
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        if (minIdx != i) {
            int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
        }
    }
}

Python
def insertion_sort(array, size):
    """Pick each element and insert it into its correct position 
    in the sorted portion.
    
    Time: O(n) best (nearly sorted), O(n²) worst. Space: O(1). Stable.
    Industry: Python/Java use this for small arrays inside Timsort/Introsort.
    """
    for i in range(1, size):
        key = array[i]       # Element to insert
        j = i - 1
        
        # Shift elements right until we find the correct position
        while j >= 0 and array[j] > key:
            array[j + 1] = array[j]
            j -= 1
        
        array[j + 1] = key  # Place in correct position

data = [12, 11, 13, 5, 6]
insertion_sort(data, len(data))
print("Sorted:", data)

C
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];
            j--;
        }
        arr[j+1] = key;
    }
}