home

DSA in C

Table of Contents

Arrays

Array is a contiguous space in memory that is meant to store elements of similar data types.

Elements in an array can be accessed via a simple mathematical expression: mem + width * offset

The mem is the starting memory address of the array where the first element is stored.

The width variable represents the width of the data type that are stored as elements in that array. So if we are talking about an array that stores integer elements of size 4 bytes (size are usually taken in bytes) and its starting address is 1000 (say), the address of its elements will be 1000, 1004, 1008, 1012, …

The offset (more commonly known as index) is the position of the element we want to access.

The starting address (mem) points to the first element of the array. So, to access the first element using the above formula, we would have to set the offset to 0:

mem + width * 0 → mem which is the starting address that we wanted.

To take another example let's try to access the 4th element of an array, for this we would have to set the offset to 3:

mem + width * 3

The mem represents the first element, so adding the width 3 times would give us the 4th element.

  • This is why array's index start at 0 in most programming languages.
  • This is also why accessing elements of an array happens in constant time (O(1)).
  • Arrays are not growable (fixed in size) but can be reallocated (entire new space allocated + old values copied).

Let's take a look at a C program in which we access array elements using pointers (their memory addresses) 

#include <stdio.h>

int main() {
    int width = sizeof(int);
    int arr[4] = {10, 20, 30, 40};

    // C under the hood adds (* sizeof(int)) to the offset so we just need to
    // add the offset to the arr pointer
    printf("1st element using C's syntax %d\n", *(arr + 0));
    printf("4th element using C's syntax %d", *(arr + 3));
}

1st element using C's syntax 10
4th element using C's syntax 40

Array representation

#include <stdio.h>

int main() {
    // array of size 10 initialised with first
    // three elements set to 1, 2 and, 3 respectively.
    int arr[10] = {1,2,3};

    // rest of the elements set using a for loop
    for (int i = 3; i < 10; ++i) {
        arr[i] = i + 1;
    }

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

1 2 3 4 5 6 7 8 9 10

Arrays in C can be accessed using pointers also.

The identifier name (arr in this case) is the pointer to the first element in the array.

Adding (or incrementing/decrementing) pointers value can give access to the elements of the array. In case of integer arrays, adding 1 adds size of int to the address of first element in array to get the address of second element. So, to get the fourth element, we can do (arr+3). 

#include <stdio.h>

int main() {
    // array of size 10 initialised with first
    // three elements set to 1, 2 and, 3 respectively.
    int arr[10] = {1,2,3};

    // rest of the elements set using a for loop
    for (int i = 3; i < 10; ++i) {
        *(arr+i) = i + 1;
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", *(arr+i));
    }
}

1 2 3 4 5 6 7 8 9 10

Inserting elements

Inserting at index n

The code below initiliases an array of size 100 to ignore any resizing that may be required later.

To insert an element at index n:

  • We move each element one index after its current position. Iterating from last to n (inclusive) and moving ith to (i+1)th position is one way to do it.
  • we simply put a desired value at index n.

The code below shows this algorithm in action. It also prints after insertion. 

#include <stdio.h>

int insert(int* arr, int size, int pos, int elem) {
  for (int i = size - 1; i >= pos - 1; --i) {
    arr[i + 1] = arr[i];
  }

  arr[pos - 1] = elem;
  return size + 1;
}

int main() {
  int n = 5;
  //            0 1 2 3 4
  int arr[100] = {1,2,3,4,5};

  // last position
  int pos = 3;
  int elem = 999;

  n = insert(arr, n, pos, elem);

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

1 2 999 3 4 5

Ideally, we should not take array of size more than what we need and we should use realloc to resize the array for insertion. C++ has vectors for this usecase.

Let's look at a program that uses realloc to resize the array for insertion. 

#include <stdio.h>
#include <stdlib.h>


int main() {
    // array of size 7
    int* arr =  (int *) malloc(7 * sizeof(int));
    int n = 4;

    // initilalize elems
    for (int i = 0; i < 7; i++) {
      arr[i] = i + 1;
    }

    // increase size of insertion (doubling)
    *arr = *(int*) realloc(arr, 2 * 7 * sizeof(int));

    // shift elems to the right by 1
    for (int i = 12; i >= n; --i) {
        arr[i + 1] = arr[i];
    }

    *(arr+n) = 69;

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

1 2 3 4 69 5 6 7 0 0 0 134465 0 0

The programm above gets really close to the implementation of vectors (growable arrays). If we keep track of capacity (max elems a vector can store) and length (total elems currently in the array), we can check if we need to grow (double the size) the array size using realloc. This is more efficient the restricting array size to a certain number (100 in previous example).

References:

Append element

Appending an element is just inserting a new element at the end of the array. 

#include <stdio.h>

int insert(int* arr, int size, int pos, int elem) {
  for (int i = size - 1; i >= pos - 1; --i) {
    arr[i + 1] = arr[i];
  }

  arr[pos - 1] = elem;
  return size + 1;
}

int main() {
  int n = 5;
  //            0 1 2 3 4
  int arr[7] = {1,2,3,4,5};

  // last position
  int pos = n + 1;
  int elem = 999;

  n = insert(arr, n, pos, elem);

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

1 2 3 4 5 999

Prepend element

Prepending an element is just inserting a new element at the beginning of the array. 

#include <stdio.h>

int insert(int* arr, int size, int pos, int elem) {
  for (int i = size - 1; i >= pos - 1; --i) {
    arr[i + 1] = arr[i];
  }

  arr[pos - 1] = elem;
  return size + 1;
}

int main() {
  int n = 5;
  //            0 1 2 3 4
  int arr[7] = {1,2,3,4,5};

  // last position
  int pos = 1;
  int elem = 999;

  n = insert(arr, n, pos, elem);

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

999 1 2 3 4 5

Deleting elements

We do exactly the opposite of what we did in the Inserting at index n section. Instead of iterating from the last element till the position n, we iterate from postion n till the last and shift every element one index back from it's original position. 

#include <stdio.h>

int main() {
  int pos = 3;
  int elem;
  int n = 5;
  //            0 1 2 3 4
  int arr[7] = {1,2,3,4,5};

  for (int i = pos - 1; i <= n - 1; i++) {
    arr[i] = arr[i+1];
  }

  n--;

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

1 2 4 5

2D Arrays

Square matrix multiplication using 2D arrays in c. 

#include <stdio.h>

int main() {
  int matrix1[][3] = {{1,2,3}
                     ,{4,5,6}
                     ,{7,8,9}};

  int matrix2[][3] = {{1,0,1}
                     ,{1,1,0}
                     ,{0,0,1}};

  int result[][3] = {{0,0,0}
                    ,{0,0,0}
                    ,{0,0,0}};

  int n_matrix1 = sizeof(matrix1) / sizeof(matrix1[0]);

  for (int i = 0; i < n_matrix1; ++i) {
    for (int j = 0; j < n_matrix1; ++j) {
      for (int k = 0; k < n_matrix1; ++k) {
        result[i][j] += matrix1[i][k] * matrix2[k][j];
      }
    }
  }

  for (int i = 0; i < n_matrix1; ++i) {
    for (int j = 0; j < n_matrix1; ++j) {
      printf("%d ", result[i][j]);
    }
    printf("\n");
  }
}

3 2 4 
9 5 10 
15 8 16

String as an array of characters

#include <stdio.h>

int main() {
    // char *s = "this is a string!";
    char s[] = "this is a string";
    printf("%s", s);
    return 0;
}

this is a string

Iterate through each character of a string and print it with a space afterwards. 

#include <stdio.h>

int main() {
    char *s = "print this!";
    int string_size = strlen(s);

    for (int i = 0; i < string_size; ++i) {
        // *(s + i) -> s[i]
        printf("%c ", *(s + i));
    }

    return 0;
}

p r i n t   t h i s !

Take string input from user 

#include <stdio.h>

int main() {
  char *str;
  size_t len = 0;
  ssize_t line_size = 0;

  getline(&str, &len, stdin);
  printf("%s", str);
}

Linked list

A simple Linked List implementation that contains integer data elements. 

#include <stdio.h>

// linked list node declaration
struct Node {
    int val;
    struct Node* next;
};

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->val = 69;

    struct Node* last = head;
    for (int i = 100; i <= 110; ++i) {
        // create a node
        struct Node* temp = malloc(sizeof(struct Node));
        temp->val = i;

        // append
        last->next = temp;
        last = last->next;
    }

    struct Node* iter = head;

    while(iter != NULL) {
        printf("%d ", iter->val);
        iter = iter->next;
    }
    printf("\n");
}

69 100 101 102 103 104 105 106 107 108 109 110

TODO Searching in a linked list

TODO insertion

TODO Deletion

TODO Mergin two linked lists

TODO Circular linked lists

Stacks

Using global arrays

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

int top = -1;
int stack[100];
int n = 100;

int push(int el) {
  if (top == n) {
    // overflow
    return -1;
  }
  stack[++top] = el;
  return 0;
}

int pop() {
  if (top < 0) {
    // underflow
    return -1;
  }

  return stack[top--];
}

void display() {
  int i = top;
  printf("========================\n");
  printf("Stack: \n");
  while(i >= 0) {
    printf("%d\n", stack[i]);
    i--;
  }
  printf("========================\n");
}

int main() {
  while(true) {
    printf("Enter choice: \n");
    printf("1. Push element in stack\n");
    printf("2. Pop element in stack\n");
    printf("3. Display stack\n");
    printf("4. Exit\n");

    int option;
    scanf("%d", &option);

    switch(option) {
      case 1: {
        int el;
        printf("Enter element to push: ");
        scanf("%d", &el);
        int st = push(el);

        if (st == -1) {
          printf("failed to push element in stack (overflow)\n");
        }
        break;
      }

      case 2: {
        int st = pop();
        if (st == -1) {
          printf("failed to pop element from stack (underflow)\n");
        }
        break;
      }

      case 3:
        display();
        break;

      case 4:
        exit(0);
        break;

      default:
        exit(0);
        break;
    }
  }
}

Using pointers to avoid global variables

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

int push(int *stack, int *top, int n, int el) {
  if (*top == n) {
    // overflow
    return -1;
  }
  *top = *top + 1;
  stack[*top] = el;
  return 0;
}

int pop(int *stack, int *top) {
  if (*top < 0) {
    // underflow
    return -1;
  }

  int el = stack[*top];
  *top = *top - 1;
  return el;
}

void display(int *stack, int top) {
  printf("========================\n");
  printf("Stack: \n");
  while(top >= 0) {
    printf("%d\n", stack[top]);
    top--;
  }
  printf("========================\n");
}

int main() {
  int top = -1;
  int n = 100;
  int stack[n];

  while(true) {
    printf("Enter choice: \n");
    printf("1. Push element in stack\n");
    printf("2. Pop element in stack\n");
    printf("3. Display stack\n");
    printf("4. Exit\n");

    int option;
    scanf("%d", &option);

    switch(option) {
      case 1: {
        int el;
        printf("Enter element to push: ");
        scanf("%d", &el);
        int st = push(stack, &top, n, el);

        if (st == -1) {
          printf("failed to push element in stack (overflow)\n");
        }
        break;
      }

      case 2: {
        int st = pop(stack, &top);
        if (st == -1) {
          printf("failed to pop element from stack (underflow)\n");
        }
        break;
      }

      case 3:
        display(stack, top);
        break;

      case 4:
        exit(0);
        break;

      default:
        exit(0);
        break;
    }
  }
}

Queues

Queue implementation using arrays

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

int enqueue(int *arr, int *rear, int *front, int n, int el) {
  if (*rear == (n - 1)) {
    // overflow
    return -1;
  }
  if (*front == -1) {
    *front = 0;
  }
  arr[++(*rear)] = el;
  return 0;
}

int dequeue(int *rear, int *front) {
  // underflow
  if (*front == -1 || *front > *rear) {
    return -1;
  }

  *front = *front + 1;
  return 0;
}

void display(int *arr, int rear, int front) {
  if (front == -1) {
    printf("empty queue\n");
    return;
  }
  printf("Queue: ");
  while (rear >= front) {
    printf("%d ", arr[rear]);
    rear--;
  }
  printf("\n");
}

int main() {
  int n = 100;
  int queue[n];
  int front = -1;
  int rear = -1;

  while(true) {
    printf("Enter choice: \n");
    printf("1. Push element in queue\n");
    printf("2. Pop element in queue\n");
    printf("3. Display queue\n");
    printf("4. Exit\n");

    int option;
    scanf("%d", &option);

    switch(option) {
      case 1: {
        int el;
        printf("Enter element to push: ");
        scanf("%d", &el);
        int st = enqueue(queue, &rear, &front, n, el);

        if (st == -1) {
          printf("failed to push element in queue (overflow)\n");
        }
        break;
      }

      case 2: {
        int st = dequeue(&rear, &front);
        if (st == -1) {
          printf("failed to pop element from queue (underflow)\n");
        }
        break;
      }

      case 3:
        display(queue, rear, front);
        break;

      case 4:
        exit(0);
        break;

      default:
        exit(0);
        break;
    }
  }
}

Queue using two stacks in C.

Maintain two stacks, intermediate stack and a final stack.

  • enqueue: push in the intermediate stack.
  • dequeue: check if final stack is empty. When empty, pop every element from the intermediate stack and push them in the final stack. Then pop an element from the final stack.
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>

int s_empty(int *top);

int s_push(int *stack, int *top, int n, int el) {
    if (*top == n) {
        // overflow
        return -1;
    }
    *top = *top + 1;
    stack[*top] = el;
    return 0;
}

int s_pop(int *stack, int *top) {
    if (s_empty(top)) {
        // underflow
        return -1;
    }

    int el = stack[*top];
    *top = *top - 1;
    return el;
}

int s_empty(int *top) {
    if (*top < 0) {
        return 1;
    }
    return 0;
}

void s_display(int *stack, int top) {
    while(top >= 0) {
        printf("%d ", stack[top]);
        top--;
    }
}

int main() {
    int top = -1;
    int n = 10;
    int si[n];
    int queue[n];
    int q_top = -1;

    int option;

    do {
        printf("Enter choice: \n");
        printf("1. Enqueue element in queue\n");
        printf("2. Dequeue element in queue\n");
        printf("3. Display queue\n");
        printf("4. Exit\n");

        scanf("%d", &option);

        switch(option) {
            case 1: {
                // enqueue
                int el;
                printf("Enter element you want to insert: ");
                scanf("%d", &el);
                s_push(si, &top, n, el);
                break;
            }

            case 2: {
                // dequeue
                if (s_empty(&q_top)) {
                    while (!s_empty(&top)) {
                        s_push(queue, &q_top, n, s_pop(si, &top));
                    }
                }
                int el = s_pop(queue, &q_top);
                if (el != -1) {
                    printf("dequeued %d from queue\n", el);
                } else {
                    printf("queue is empty\n");
                }
                break;
            }

            case 3: {
                // display
                printf("Queue: ");
                // display queue from top to bottom
                s_display(queue, q_top);
                // display si from bottom to top
                if (top != -1) {
                    for (int i = 0; i <= top; i++) {
                        printf("%d ", si[i]);
                    }
                }

                printf("\n");
                break;
            }
        }
    } while(option != 4);
}

Circular Queue

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

int is_empty(int front) {
    return front == -1;
}

int is_full(int rear, int front, int size) {
  if ((front == rear + 1) || (front == 0 && rear == size - 1)) {
    return 1;
  }
  return 0;
}

int enqueue(int *arr, int *rear, int *front, int n, int el) {
    if (is_full(*rear, *front, n)) {
        // overflow
        return -1;
    }

    if (*front == -1) {
        *front = 0;
    }

    *rear = (*rear + 1) % n;
    arr[*rear] = el;
    return 0;
}

int dequeue(int* queue, int *rear, int *front, int n) {
    if (is_empty(*front)) {
        // underflow
        return -1;
    }

    int el = queue[*front];

    if (*front == *rear) {
        *front = -1;
        *rear = -1;
    } else {
        *front = (*front + 1) % n;
    }

    return el;
}

void display(int *arr, int rear, int front, int n) {
    if (is_empty(front)) {
        printf("empty queue\n");
        return;
    }

    printf("arr: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    int i;
    for (i = front; i != rear; i = (i + 1) % n) {
        printf("%d ", arr[i]);
    }
    printf("%d ", arr[i]);

    printf("\n");

    printf("front = %d\nrear = %d\n", front, rear);
}

int main() {
    int n = 5;
    int queue[n];
    int front = -1;
    int rear = -1;

    while(true) {
        printf("Enter choice: \n");
        printf("1. Push element in queue\n");
        printf("2. Pop element in queue\n");
        printf("3. Display queue\n");
        printf("4. Exit\n");

        int option;
        scanf("%d", &option);

        switch(option) {
        case 1: {
            int el;
            printf("Enter element to push: ");
            scanf("%d", &el);
            int st = enqueue(queue, &rear, &front, n, el);

            if (st == -1) {
                printf("failed to push element in queue (overflow)\n");
            }
            break;
        }

        case 2: {
            int st = dequeue(queue, &rear, &front, n);
            if (st == -1) {
                printf("failed to pop element from queue (underflow)\n");
            } else {
                printf("dequeued %d from queue\n", st);
            }
            break;
        }

        case 3:
            display(queue, rear, front, n);
            break;

        case 4:
            exit(0);
            break;

        default:
            exit(0);
            break;
        }
    }
}

TODO Trees

TODO Graphs

Sorting

Bubble Sort

Bubble the biggest element to the end. Do it till n (size of array). The array is sorted. 

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int arr[] = {1,6,3,9,2,0, 999, -2, -20};
    int size = sizeof(arr) / sizeof(int);

    for (int pass = 0; pass < (size - 1); pass++) {
        for (int j = 0; j < size - 1 - pass; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }

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

-20 -2 0 1 2 3 6 9 999
  • TODO draw each pass of sorting
  • TODO optimise (check for swap and terminate early (premature termination))

Insertion Sort

Maintain a sorted subarray inside array. Iterate over array elements and put elements in the sorted subarray. 

#include <stdio.h>

void insertion_sort(int *arr, int size) {
    for (int i = 1; i < size; ++i) {
        int value = arr[i];
        int hole = i - 1;
        while (hole >= 0 && (arr[hole] > value)) {
            arr[hole + 1] = arr[hole];
            hole = hole - 1;
        }
        arr[hole + 1] = value;
    }
}

int main() {
    int arr[] = {6, 9, 7, 3, 5, 10, 9};
    int size = sizeof(arr) / sizeof(int);

    printf("Unsorted: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertion_sort(arr, size);

    printf("Sorted: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Unsorted: 6 9 7 3 5 10 9 
Sorted: 3 5 6 7 9 9 10

Quick Sort

Take a pivot point. Everything smaller than pivot element goes to the left and bigger elements go to the right. Recursively call until the array length is 1 and the array is sorted. O(nlogn) O(n2) in worst case 

#include <stdio.h>

void swap(int *a, int *b);

int partition(int *arr, int start, int end) {
    int pi = end;
    int pivot = arr[pi];
    int pivot_place = start;

    for (int i = start; i < end; ++i) {
        if (arr[i] < pivot) {
            swap(&arr[i], &arr[pivot_place]);
            pivot_place++;
        }
    }

    swap(&arr[pi], &arr[pivot_place]);
    return pivot_place;
}

void quick_sort(int *arr, int left, int right) {
    if (left >= right) return;

    int pivot_i = partition(arr, left, right);
    quick_sort(arr, left, pivot_i - 1);
    quick_sort(arr, pivot_i + 1, right);
}

int main() {
    int arr[] = {7, 2, 6, 8, 5, 3, 4, 9, -2};
    int size = sizeof(arr) / sizeof(int);

    printf("Unsorted: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quick_sort(arr, 0, size - 1);

    printf("Sorted: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Unsorted: 7 2 6 8 5 3 4 9 -2 
Sorted: -2 2 3 4 5 6 7 8 9

Selection Sort

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selection_sort(int *arr, int size) {
    for (int i = 0; i < size - 1; ++i) {
        int pos = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[pos]) {
                pos = j;
            }
        }

        if (pos != i) {
            swap(&arr[i], &arr[pos]);
        }
    }
}

int main() {
    int arr[] = {1, 9, 10, 20, 2, 4, -2};
    int size = sizeof(arr) / sizeof(int);

    printf("Unsorted: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    selection_sort(arr, size);

    printf("Sorted: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Unsorted: 1 9 10 20 2 4 -2 
Sorted: -2 1 2 4 9 10 20

Merge Sort

Bubble sort, Insertion sort and selection sort are all O(n2). Let's take a look at a sorting algorithm that's O(nlogn) in the worst case. 

#include <stdio.h>

void merge(int *arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;
  int L[n1], R[n2];

  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 L and R back into arr
  int i = 0;
  int j = 0;
  int k = left;

  while (i < n1 && j < n2) {
    if (L[i] < R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  // copy remaining L if any
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  // copy remaining R if any
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

void merge_sort(int *arr, int left, int right) {
    if (left == right) {
        return;
    }

    int mid = (left + right) / 2;

    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

int main() {
    int arr[] = {1, 9, 8, 10, 20, 2, 4, -2};
    int size = sizeof(arr) / sizeof(int);

    printf("array: ");
    for (int i = 0; i < size; ++i) printf("%d ", arr[i]);
    printf("\n");

    merge_sort(arr, 0, size - 1);

    printf("after merge: \n");
    for (int i = 0; i < size; ++i) printf("%d ", arr[i]);
    printf("\n");
}

array: 1 9 8 10 20 2 4 -2 
merging: 1 9 8 10 	20 2 4 -2 
merging: 1 9 	8 10 
merging: 1 	9 
merging: 8 	10 
merging: 20 2 	4 -2 
merging: 20 	2 
merging: 4 	-2 
after merge: 
-2 1 2 4 8 9 10 20

Heap Sort

TODO Hashing Techniques

Searching

Linear search

#include <stdio.h>

int main() {
    int arr[] = {1,2,3,99,2389,21};
    int size = sizeof(arr) / sizeof(int);
    int target = 99;

    int found_index = -1;

    for (int i = 0; i < size; ++i) {
        if (arr[i] == target) {
            found_index = i;
        }
    }

    if (found_index >= 0) {
        printf("Element %d found at index %d\n", arr[found_index], found_index);
    } else {
        printf("element not found");
    }

    return 0;
}

Element 99 found at index 3

Count number of occurences in an array 

#include <stdio.h>

int count(int *arr, int size, int target) {
    int count = 0;

    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 3, 4, 4, 6, 9, 4};
    int target = 4;
    int size = sizeof(arr) / sizeof(int);

    printf("%d occurs %d times in the array", target, count(arr, size, target));
}

4 occurs 3 times in the array

Binary Search

Using recursion. 

#include <stdio.h>

int binary_search(int *arr, int left, int right, int target) {
    if (left > right) {
        return -1;
    }

    int mid = (left + right) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (target > arr[mid]) {
        return binary_search(arr, mid + 1, right, target);
    } else {
        return binary_search(arr, left, mid - 1, target);
    }
}

int main() {
    int arr[] = {1, 3, 9, 22, 29};
    int size = sizeof(arr) / sizeof(int);

    printf("found 1 at index: %d\n", binary_search(arr, 0, size - 1, 1));
    printf("found 3 at index: %d\n", binary_search(arr, 0, size - 1, 3));
    printf("found 9 at index: %d\n", binary_search(arr, 0, size - 1, 9));
    printf("found 22 at index: %d\n", binary_search(arr, 0, size - 1, 22));
    printf("found 29 at index: %d\n", binary_search(arr, 0, size - 1, 29));
}

found 1 at index: 0
found 3 at index: 1
found 9 at index: 2
found 22 at index: 3
found 29 at index: 4

#include <stdio.h>

int binary_search_it(int *arr, int left, int right, int target) {
    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (target > arr[mid]) {
            return binary_search_it(arr, mid + 1, right, target);
        } else {
            return binary_search_it(arr, left, mid - 1, target);
        }
    }
}

int main() {
    int arr[] = {1, 3, 9, 22, 29};
    int size = sizeof(arr) / sizeof(int);

    printf("found 1 at index: %d\n", binary_search_it(arr, 0, size - 1, 1));
    printf("found 3 at index: %d\n", binary_search_it(arr, 0, size - 1, 3));
    printf("found 9 at index: %d\n", binary_search_it(arr, 0, size - 1, 9));
    printf("found 22 at index: %d\n", binary_search_it(arr, 0, size - 1, 22));
    printf("found 29 at index: %d\n", binary_search_it(arr, 0, size - 1, 29));
}

found 1 at index: 0
found 3 at index: 1
found 9 at index: 2
found 22 at index: 3
found 29 at index: 4

TODO File Handling

Author: Siddhant Kumar