← Back to Tutorials Chapter 2

Arrays

Arrays are the simplest and most widely used data structure. They store elements in contiguous memory locations and provide O(1) access by index.

Array Basics

An array is a collection of elements of the same type placed in adjacent memory slots. Each element can be accessed directly using its index. The index typically starts at 0.

Memory Layout

If an array starts at memory address base and each element takes size bytes, then element i is located at base + i * size. This formula gives constant-time access.

Static vs Dynamic Arrays

Static arrays have a fixed size set at creation. Dynamic arrays (like Python's list or Java's ArrayList) automatically grow when elements are added, typically by doubling capacity, which gives amortized O(1) append.

Sorting Algorithms

Sorting arranges elements in a specified order (usually ascending). Here are common sorting algorithms:

Bubble Sort — O(n²)

Repeatedly steps through the list, swaps adjacent elements if they are in the wrong order, and repeats until no swaps are needed.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Selection Sort — O(n²)

Finds the smallest element and swaps it with the first unsorted position.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Insertion Sort — O(n²)

Builds the sorted array one element at a time by inserting each element into its correct position.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Merge Sort — O(n log n)

A divide-and-conquer algorithm that splits the array in half, recursively sorts each half, then merges the sorted halves.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Quick Sort — O(n log n) average

Selects a pivot, partitions the array into elements less than and greater than the pivot, then recursively sorts each partition.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Counting Sort — O(n + k)

A non-comparison sort that counts occurrences of each distinct value. Works well when the range of possible values (k) is small.

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for val in arr:
        count[val] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

Searching Algorithms

Linear Search — O(n)

Scans every element until the target is found. Simple but slow for large arrays.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Binary Search — O(log n)

Works on sorted arrays. Repeatedly divides the search interval in half.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Time Complexity Summary

• Access by index: O(1)
• Search (unsorted, linear): O(n)
• Search (sorted, binary): O(log n)
• Insertion at end (dynamic array, amortized): O(1)
• Insertion at beginning/middle: O(n)
• Deletion: O(n)