Arrays, Strings & Their Operations in C: Syntax, Traversal, Sorting, Searching

TAKEAWAYS:

• Arrays store homogeneous data in contiguous memory, enabling efficient access via indices (O(1) for direct access).
• Strings in C are null-terminated character arrays (char str[] = {'H','i','\0'}), requiring manual length checks.
• Sorting algorithms (e.g., bubble sort) rearrange elements via comparisons/swaps, while searching (linear/binary) locates values with O(n) or O(log n) complexity.
• 2D arrays model matrices (e.g., game boards, spreadsheets) with row-major ordering.
• Common pitfalls include buffer overflows (unbounded string inputs) and off-by-one errors in loops.
• Real-world uses include Khalti’s transaction logs (sorted arrays for fraud detection) and Daraz’s product catalogs (2D arrays for inventory management).

Arrays in C: Definition and Initialization

Arrays are contiguous memory locations storing elements of the same data type. They enable efficient access via indices (starting at 0).

1D Array Syntax

int marks[5];          // Uninitialized array (garbage values)
int scores[] = {90, 85, 78, 92}; // Auto-size (4 elements)

Visualization: Memory Layout Key Points:

• Size must be a compile-time constant (no int n; scanf("%d", &n); int arr[n];).
• No bounds checking: Accessing marks[5] causes undefined behavior (likely a crash).

2D Arrays (Matrices)

int matrix[3][3] = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

Visualization: Row-Major Ordering Real-World Example: Daraz’s Product Catalog

• Stored as a 2D array where products[row][0] = ID, products[row][1] = price, etc.
• Enables quick lookup by category (e.g., for (int i = 0; i < electronics_rows; i++)).

Array Operations: Traversal, Sorting, Searching

1. Traversal (Looping Through Elements)

for (int i = 0; i < 5; i++) {
  printf("%d ", marks[i]);
}

Trace Table:

Error: Loop condition should be i < 4 (size - 1).

2. Sorting: Bubble Sort

Algorithm Flowchart

flowchart TD
  A["Start"] --> B["i = 0"]
  B --> C{""i < n-1""}
  C -->|"Yes"| D["j = 0"]
  D --> E{""j < n-i-1""}
  E -->|"Yes"| F["Swap if arr[j] > arr[j+1]"]
  F --> G["j++"]
  G --> E
  E -->|"No"| H["i++"]
  H --> C
  C -->|"No"| I["End"]

Code Example:

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]) {
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

Trace for arr = {5, 3, 8, 4} (n=4):

Optimization: Add a swapped flag to exit early if no swaps occur in a pass.

3. Searching: Linear vs. Binary Search

Binary Search Trace for arr = {2, 5, 8, 12, 16} (key=8):

Real-World Example: Nepal Stock Exchange (NEPSE) Index Tracking

• NEPSE’s daily closing prices are stored in a sorted array.
• Binary search locates the price for a specific date in O(log n) time.

Strings in C: Null-Terminated Character Arrays

Strings are arrays of characters ending with \0 (null terminator). Example:

char name[] = {'J', 'o', 'h', 'n', '\0'}; // Equivalent to "John"
char greeting[6] = "Hello"; // Auto-adds '\0'

String Operations

Pitfall: Buffer Overflow

char buffer[5];
gets(buffer); // UNSAFE: No bounds checking!

Fix: Use fgets(buffer, 5, stdin) to limit input to 4 chars + \0.

Real-World Example: eSewa’s User Authentication

• Passwords are stored as null-terminated strings in a database.
• strcmp() compares input passwords with stored hashes (e.g., strcmp(input, stored_hash) == 0).

Arrays vs. Strings: Comparison Table

## In the Real World

1. Khalti’s Transaction Logs

   • Idea Used: Sorted Arrays
   • How: Transactions are stored in an array sorted by timestamp. Binary search (O(log n)) quickly retrieves a user’s last transaction.
   • Example: To find all transactions for a user ID 12345, Khalti first sorts the array by user_id and uses binary search to locate the range.

2. Pathao’s Ride Queue

   • Idea Used: Queue (Circular Array)
   • How: Pathao’s driver assignment system uses a circular queue to manage ride requests. The oldest request (front) is assigned first.
   • Example:

     int queue[100], front = 0, rear = 0;
     // Enqueue: rear = (rear + 1) % 100;
     // Dequeue: front = (front + 1) % 100;
     

     If 5 requests arrive, rear moves to index 4. The first driver picks queue[front] (index 0).

3. NTC’s Traffic Route Optimization

   • Idea Used: 2D Arrays (Adjacency Matrix)
   • How: NTC models Kathmandu’s roads as a 2D array where graph[i][j] = travel time from intersection i to j.
   • Example: To find the fastest route from Thapathali to Koteshwor, NTC uses Dijkstra’s algorithm on the matrix.

## Exam Tip

1. Array Indexing

   • Always remember: indices start at 0 and size = length + 1.
   • Common mistake: for (int i = 1; i <= n; i++) → buffer overflow.

2. String Handling

   • Never use gets() in exams (or real code). Use fgets() or scanf("%s", str).
   • strlen() does not count the null terminator. Example: "Hi" has length 2.

3. Sorting/Searching

   • Binary search only works on sorted arrays. If the array is unsorted, use linear search.
   • For bubble sort, explain the pass-by-pass process in exams (e.g., "After 1st pass, largest element bubbles to the end").

4. 2D Arrays

   • Access elements as array[row][column].
   • To traverse all elements: for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++).

5. Practical Questions

   • Expect questions like:
     • "Write a function to reverse a string using an array."
     • "Sort a 2D array in ascending order row-wise."
     • "Find the second largest element in an array without sorting."

Visual Summary of Key Concepts

mindmap
  root((Arrays & Strings in C))
    Arrays
      1D Array
        Definition: Contiguous memory
        Example: int arr[5] = {1, 2, 3};
      2D Array
        Definition: Matrix (rows x columns)
        Example: int mat[2][2] = {{1, 2}, {3, 4}};
      Operations
        Traversal: for loop
        Sorting: Bubble/Selection
        Searching: Linear/Binary
    Strings
      Definition: Null-terminated char array
      Example: char str[] = "Hello";
      Functions: strlen, strcpy, strcmp
    Real-World
      Khalti: Sorted arrays for transactions
      Pathao: Circular queue for rides
      NTC: 2D array for traffic routes