# Data Structure and Algorithm
## Binary Search

int binary_search(int *arr, int target, int start, int end){
    int mid = 0;
    while(start <= end){
        mid = start + ((end-start)>>1);
        if(arr[mid] == target){
            return mid;
        }
        else if(arr[mid] > target){
            end = mid-1;
        }
        else{
            start = mid+1;
        }
    }
    return -1;
}

## Stack: First in, Last out
Operation: push, pop

#include <stdio.h>

typedef struct _node{
    int value;
    struct _node *next;
}node;

typedef struct _stack{
    node *head;
    int size;
}stack;

void stack_init(stack **_stack){
    stack *new_stack = malloc(sizeof(stack));
    new_stack -> size = 0;
    new_stack -> head = NULL;
    *_stack = new_stack;
}

void push(stack *_stack, int _value){
    node *new_node = malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = _stack -> head;
        _stack -> head = new_node;
        _stack -> size++;    
    }
}

int pop(stack *_stack){
    if(_stack -> size > 0){
        node *remove_node = _stack -> head;
        _stack -> head = _stack -> head -> next;
        int node_value = remove_node -> value;
        free(remove_node);
        _stack -> size--;
        return node_value;
    }
}

int main()
{
    stack *my_stack;
    stack_init(&my_stack);
    push(my_stack, 1);
    push(my_stack, 2);
    push(my_stack, 3);
    printf("%d \n", pop(my_stack));
    printf("%d \n", pop(my_stack));
    printf("%d \n", pop(my_stack));
    //result: 3 2 1
    return 0;
}

## Queue: First In, First Out
Operation: enqueue, dequeue

#include <stdio.h>

typedef struct _node{
    int value;
    struct _node *next;
}node;

typedef struct _queue{
    node *front;
    node *back;
    int size;
}queue;

void queue_init(queue **_queue){
    queue *new_queue = malloc(sizeof(queue));
    new_queue -> size = 0;
    new_queue -> front = NULL;
    new_queue -> back = NULL;
    *_queue = new_queue;
}

void enqueue(queue *_queue, int _value){
    node *new_node = malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = NULL;
        if(_queue -> size == 0){
            _queue -> front = new_node;
            _queue -> back = new_node;
        }
        else{
            _queue -> back -> next = new_node;
            _queue -> back = new_node;    
        }
        _queue -> size++;
    }
}

int dequeue(queue *_queue){
    if(_queue -> size > 0){
        node *remove_node = _queue -> front;
        _queue -> front = _queue -> front -> next;
        int node_value = remove_node -> value;
        free(remove_node);
        _queue -> size--;
        return node_value;
    }
    else
    return -1;
}

int main()
{
    queue *my_queue;
    queue_init(&my_queue);
    enqueue(my_queue, 1);
    enqueue(my_queue, 2);
    enqueue(my_queue, 3);
    printf("%d \n", dequeue(my_queue));
    printf("%d \n", dequeue(my_queue));
    printf("%d \n", dequeue(my_queue));
    // result: 1 2 3
    return 0;
}

## Single Linked List
Operation:
push/pop from front/back of the list
reverse list

#include <stdio.h>

typedef struct _node{
    int value;
    struct _node *next;
}node;

typedef struct _list{
    node *head;
    int size;
}list;

int is_empty(list *list){
    return list -> size > 0 ? 1 : 0;
}

void list_init(list **_list){
    list *new_list = (list *)malloc(sizeof(list));
    if(new_list != NULL){
        new_list -> size = 0;
        new_list -> head = NULL;
        *_list = new_list;
    }
}


int remove_node_at(list *_list, int _index, int *_value){
    node **list_pointer = &(_list -> head);
    int index = _index;
    if(_index < _list -> size){
        while(index > 0){
            list_pointer = &((*list_pointer) -> next);
            index--;
        }
        node *removal_node = *list_pointer;
        *_value = removal_node -> value;
        free(removal_node);
        *list_pointer = (*list_pointer) -> next;
        _list -> size--;
        return 0;
    }
    return -1;
}

void push_front_list(list *_list, int _value){
    node *new_node = (node *)malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = _list -> head;
        _list -> head = new_node;
        _list -> size++;
    }
}

int pop_front_list(list *_list, int *_pop_value){
    return remove_node_at(_list, 0, _pop_value);
}

void push_back_list(list *_list, int _value){
    node *new_node = (node *)malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = NULL;
        node *tail = _list -> head;
        while(tail -> next != NULL){
            tail = tail -> next;
        }
        tail -> next = new_node;
        _list -> size++;
    }
}

int pop_back_list(list *_list, int *_pop_value){
    return remove_node_at(_list, _list -> size - 1, _pop_value);
}


void travel_list(list *_list){
    node *travel = _list -> head;
    int count = 0;
    while(travel != NULL){
        printf("list %d address 0x%x value %d\n", count, travel, travel -> value);
        count++;
        travel = travel -> next;
    }
    printf("\n");
}

void reverse_list(list *_list){
    node *pre_node, *cur_node, *next_node;
    int list_size = _list -> size;
    if(list_size >= 2){
        pre_node = NULL;
        cur_node = _list -> head;
        next_node = _list -> head -> next;
        while(next_node != NULL){
            next_node = cur_node -> next;
            cur_node -> next = pre_node;
            pre_node = cur_node;
            cur_node = next_node;
        }
        _list -> head = pre_node;
    }
}

int main()
{
    list *my_list;
    list_init(&my_list);
    push_front_list(my_list, 1);
    push_front_list(my_list, 2);
    push_front_list(my_list, 3);
    push_front_list(my_list, 4);
    push_back_list(my_list, 0);
    travel_list(my_list);
    
    reverse_list(my_list);
    travel_list(my_list);
    int value;
    pop_front_list(my_list, &value);
    printf("pop value %d\n", value);
    travel_list(my_list);
    
    pop_front_list(my_list, &value);
    printf("pop value %d\n", value);
    travel_list(my_list);
    
    pop_back_list(my_list, &value);
    printf("pop value %d\n", value);
    travel_list(my_list);
    return 0;
}

## Doubly linked list

#include <stdio.h>

typedef struct _node{
    int value;
    struct _node *next;
    struct _node *prev;
}node;

typedef struct _list{
    node *head;
    node *tail;
    int size;
}list;

int is_empty(list *list){
    return list -> size > 0 ? 1 : 0;
}

void list_init(list **_list){
    list *new_list = (list *)malloc(sizeof(list));
    if(new_list != NULL){
        new_list -> size = 0;
        new_list -> head = NULL;
        new_list -> tail = NULL;
        *_list = new_list;
    }
}


int remove_node_at(list *_list, int _index, int *_value){
    node **list_pointer = &(_list -> head);
    int index = _index;
    if(_index < _list -> size){
        while(index > 0){
            list_pointer = &((*list_pointer) -> next);
            index--;
        }
        node *removal_node = *list_pointer;
        *_value = removal_node -> value;
        free(removal_node);
        node *prev = (*list_pointer) -> prev;
        *list_pointer = (*list_pointer) -> next;
        (*list_pointer) -> prev = prev;
        _list -> size--;
        return 0;
    }
    return -1;
}

int pop_front_list(list *_list, int *_pop_value){
    node *remove_node = _list -> head;
    if(_list -> size > 0){
        if(_list -> size == 1){
            _list -> head = NULL;
            _list -> tail = NULL;
        }
        else{
            _list -> head = _list -> head -> next;
            _list -> head -> prev = NULL;
        }
        _list -> size--;
        *_pop_value = remove_node -> value;
        free(remove_node);
        return 0;
    }
    return -1;
}

int pop_back_list(list *_list, int *_pop_value){
    node *removal_node = _list -> tail;
    if(_list -> size > 0){
        if(_list -> size == 1){
            _list -> head = NULL;
            _list -> tail = NULL;
        }
        else{
            _list -> tail = _list -> tail -> prev;
            _list -> tail -> next = NULL;
        }
        _list -> size--;
        *_pop_value = removal_node -> value;
        free(removal_node);
        return 0;
    }
    return -1;
}

void push_front_list(list *_list, int _value){
    node *new_node = (node *)malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = _list -> head;
        new_node -> prev = NULL;
        if(_list -> size > 0){
            _list -> head -> prev = new_node;
        }
        else{
            _list -> tail = new_node;
        }
        _list -> head = new_node;
        _list -> size++;
    }
}

void push_back_list(list *_list, int _value){
    node *new_node = (node *)malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = NULL;
        new_node -> prev = _list -> tail;
        if(_list -> size > 0){
            _list -> tail -> next = new_node;
        }
        else{
            _list -> head = new_node;
        }
        _list -> tail = new_node;
        _list -> size++;
    }
}

void forward_travel_list(list *_list){
    node *travel = _list -> head;
    int count = 0;
    while(travel != NULL){
        printf("list %d address 0x%x value %d\n", count, travel, travel -> value);
        count++;
        travel = travel -> next;
    }
    printf("\n");
}

void backward_travel_list(list *_list){
    node *travel = _list -> tail;
    int count = 0;
    while(travel != NULL){
        printf("list %d address 0x%x value %d\n", count, travel, travel -> value);
        count++;
        travel = travel -> prev;
    }
    printf("\n");
}

void reverse_list(list *_list){
    node *pre_node, *cur_node, *next_node;
    int list_size = _list -> size;
    if(list_size >= 2){
        pre_node = NULL;
        cur_node = _list -> head;
        next_node = _list -> head -> next;
        while(next_node != NULL){
            next_node = cur_node -> next;
            cur_node -> next = pre_node;
            cur_node -> prev = next_node;
            pre_node = cur_node;
            cur_node = next_node;
        }
        _list -> tail = _list -> head;
        _list -> head = pre_node;
    }
}

int main()
{
    list *my_list;
    list_init(&my_list);
    push_front_list(my_list, 1);
    push_front_list(my_list, 2);
    push_front_list(my_list, 3);
    push_front_list(my_list, 4);
    push_back_list(my_list, 0);
    forward_travel_list(my_list);
    backward_travel_list(my_list);
    int val;
    
    pop_front_list(my_list, &val);
    printf("pop value %d\n", val);
    pop_back_list(my_list, &val);
    printf("pop value %d\n", val);
    
    reverse_list(my_list);
    forward_travel_list(my_list);
    backward_travel_list(my_list);
    
    pop_back_list(my_list, &val);
    printf("pop value %d\n", val);
    pop_front_list(my_list, &val);
    printf("pop value %d\n", val);
    pop_back_list(my_list, &val);
    printf("pop value %d\n", val);
    
    return 0;
}

## Binary Search Tree
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

- The left sub-tree of a node has a key less than or equal to its parent node's key.

- The right sub-tree of a node has a key greater than to its parent node's key
- Complexity: Worst cast O(n), Average O(log(n))
Preorder Traversal 前序遍歷
理論上的遍歷順序是：根、左子樹、右子樹。根排在前面。
即是Depth-first Search。
Inorder Traversal 中序遍歷
理論上的遍歷順序是：左子樹、根、右子樹。根排在中間。
實際上是採用Depth-first Search，只不過更動了節點的輸出順序。
Postorder Traversal 後序遍歷
理論上的遍歷順序是：左子樹、右子樹、根。根排在後面。
實際上是採用Depth-first Search，只不過更動了節點的輸出順序。
Level-order Traversal 層序遍歷
即是Breath-first Search。

#include <stdio.h>

typedef struct _tree_node{
    int value;
    struct _tree_node *left;
    struct _tree_node *right;
}tree_node;

typedef struct _tree{
    tree_node *root;
    int size;
}tree;

void tree_init(tree **new_tree){
    tree *new = (tree *)malloc(sizeof(tree));
    if(new != NULL){
        new -> root = NULL;
        new -> size = 0;
        *new_tree = new;
    }
}

void insert(tree *_tree, int _value){
    tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> left = NULL;
        new_node -> right = NULL;
        if(_tree -> size == 0){
            _tree -> root = new_node;
        }
        else{
            tree_node *travel_node = _tree -> root;
            while(1){
                if(_value < travel_node -> value){
                    if(travel_node -> left == NULL){
                        travel_node -> left = new_node;
                        break;
                    }
                    else{
                        travel_node = travel_node -> left;
                    }
                }
                else if(_value > travel_node -> value){
                    if(travel_node -> right == NULL){
                        travel_node -> right = new_node;
                        break;
                    }
                    else{
                        travel_node = travel_node -> right;
                    }
                }
            }
        }
        _tree -> size++;
        
    }
}

void pre_order_print_tree(tree_node *_node){
    if(_node == NULL){
        return;
    }
    printf("%d ", _node -> value);
    pre_order_print_tree(_node -> left);
    pre_order_print_tree(_node -> right);
}

void in_order_print_tree(tree_node *_node){
    if(_node == NULL){
        return;
    }
    in_order_print_tree(_node -> left);
    printf("%d ", _node -> value);
    in_order_print_tree(_node -> right);
}

void reverse_in_order_print_tree(tree_node *_node){
    if(_node == NULL){
        return;
    }
    reverse_in_order_print_tree(_node -> right);
    printf("%d ", _node -> value);
    reverse_in_order_print_tree(_node -> left);
}

void post_order_print_tree(tree_node *_node){
    if(_node == NULL){
        return;
    }
    post_order_print_tree(_node -> left);
    post_order_print_tree(_node -> right);
    printf("%d ", _node -> value);
}

int main()
{
    tree *my_tree = NULL;
    tree_init(&my_tree);
    insert(my_tree, 39);
    insert(my_tree, 10);
    insert(my_tree, 100);
    insert(my_tree, 12);
    insert(my_tree, 50);
    insert(my_tree, 70);
    insert(my_tree, 80);  
    insert(my_tree, 390);  
    insert(my_tree, 1);  
    pre_order_print_tree(my_tree -> root);
    printf("\n");
    in_order_print_tree(my_tree -> root);
    printf("\n");
    post_order_print_tree(my_tree -> root);
    printf("\n");
    reverse_in_order_print_tree(my_tree -> root);
    //39 10 1 12 100 50 70 80 390
    //1 10 12 39 50 70 80 100 390
    //1 12 10 80 70 50 390 100 39
    //390 100 80 70 50 39 12 10 1
    return 0;
}

## Graph

Adjacency List Representation of graph
- Vertex − Each node of the graph is represented as a vertex
- Edge − Edge represents a path between two vertices or a line between two vertices.
- Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge.
- Path − Path represents a sequence of edges between the two vertices.

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

typedef struct _edge_node{
    int vertex;
    int weight;
    struct _edge_node *next;
}edge_node;

// Adjacency list representation
typedef struct _graph{
    // An array of pointers of edge_node
    edge_node * *edges;
    int number_of_nodes;
    int number_of_edges;
    bool is_directed;
}graph;

graph *create_graph(int _number_of_nodes, bool _is_directed){
    graph * new_graph = (graph *)malloc(sizeof(graph));
    new_graph -> number_of_edges = 0;
    new_graph -> number_of_nodes = _number_of_nodes;
    new_graph -> is_directed = _is_directed;
    new_graph -> edges = (edge_node **)malloc(sizeof(edge_node *) * _number_of_nodes);
    for(int i = 0; i < _number_of_nodes; i++){
        new_graph -> edges[i] = NULL;
    }
    return new_graph;
}

void print_graph(graph *_graph){
    for(int i = 0; i < _graph -> number_of_nodes; i++){
        printf("%d -->", i);
        edge_node *travel_node = _graph -> edges[i];
        while(travel_node != NULL){
            printf("%d ", travel_node -> vertex);
            travel_node = travel_node -> next;
        }
        printf("\n");
    }
}

void add_edge(graph *graph, int u, int _vertex, int _weight){
    edge_node *new_edge_node = (edge_node *)malloc(sizeof(edge_node));
    new_edge_node -> vertex = _vertex;
    new_edge_node -> weight = _weight;
    new_edge_node -> next = graph -> edges[u];
    graph -> edges[u] = new_edge_node;
    if(graph -> is_directed == false){
        new_edge_node = (edge_node *)malloc(sizeof(edge_node));
        new_edge_node -> vertex = u;
        new_edge_node -> weight = _weight;
        new_edge_node -> next = graph -> edges[_vertex];
        graph -> edges[_vertex] = new_edge_node;
    }
    graph -> number_of_edges++;
}

int main()
{
    graph *my_graph = create_graph(6, false);
    add_edge(my_graph, 2, 4, 1);
    add_edge(my_graph, 2, 5, 1);
    print_graph(my_graph);
    return 0;
}

## Heap

#include <stdio.h>

#define MAX_SIZE 1024

typedef struct _heap{
    int *arr;
    int size;
}heap;

heap *create_heap(){
    heap *new_heap = (heap *)malloc(sizeof(heap));
    new_heap -> arr = (int *)calloc(sizeof(int), MAX_SIZE);
    new_heap -> size = 0;
    return new_heap;
}

int is_empty(heap *_heap){
    return _heap -> size == 0 ? 1 : 0;
}

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

int max(int a, int b){
    return a > b ? a : b;
}

int min(int a, int b){
    return a < b ? a : b;
}

void insert_max_heap(heap *_heap, int value){
    _heap -> size++; // do not use index 0 to store value
    _heap -> arr[_heap -> size] = value;
    int index = _heap -> size;
    while(index > 1 && _heap -> arr[index] > _heap -> arr[index/2]){
        swap(&_heap -> arr[index], &_heap -> arr[index/2]);
        index = index / 2;
    }
}

int extract_max_heap(heap *_heap){
    if(_heap -> size == 0){
        return -1;
    }
    int value = _heap -> arr[1];
    // swap the head and tail
    _heap -> arr[1] = _heap -> arr[_heap -> size];
    _heap -> size--;
    int parent_index = 1;
    int left_child_index = 0;
    int right_child_index = 0;
    do{
        left_child_index = parent_index * 2;
        right_child_index = parent_index * 2 + 1;
         if(_heap -> size < left_child_index){
            break;
        }
        if(_heap -> arr[parent_index] >= max(_heap -> arr[left_child_index], _heap -> arr[right_child_index])){
            break;
        }
        // Heap node could be full or left child only
        if(_heap -> size == left_child_index || _heap -> arr[left_child_index] > _heap -> arr[right_child_index]){
              swap(&_heap -> arr[left_child_index], &_heap -> arr[parent_index]);
            parent_index = left_child_index;
        }
        else{
            swap(&_heap -> arr[right_child_index], &_heap -> arr[parent_index]);
            parent_index = right_child_index;
        }
    }while(parent_index < _heap -> size);
    return value;
}


void insert_min_heap(heap *_heap, int value){
    _heap -> size++; // do not use index 0 to store value
    _heap -> arr[_heap -> size] = value;
    int index = _heap -> size;
    while(index > 1 && _heap -> arr[index] < _heap -> arr[index/2]){
        swap(&_heap -> arr[index], &_heap -> arr[index/2]);
        index = index / 2;
    }
}

int extract_min_heap(heap *_heap){
    if(_heap -> size == 0){
        return -1;
    }
    int value = _heap -> arr[1];
    // swap the head and tail
    _heap -> arr[1] = _heap -> arr[_heap -> size];
    _heap -> size--;
    int parent_index = 1;
    int left_child_index = 0;
    int right_child_index = 0;
    do{
        left_child_index = parent_index * 2;
        right_child_index = parent_index * 2 + 1;
         if(_heap -> size < left_child_index){
            break;
        }
        if(_heap -> arr[parent_index] < min(_heap -> arr[left_child_index], _heap -> arr[right_child_index])){
            break;
        }
        // Heap node could be full or left child only
        if(_heap -> size == left_child_index || _heap -> arr[left_child_index] < _heap -> arr[right_child_index]){
              swap(&_heap -> arr[left_child_index], &_heap -> arr[parent_index]);
            parent_index = left_child_index;
        }
        else{
            swap(&_heap -> arr[right_child_index], &_heap -> arr[parent_index]);
            parent_index = right_child_index;
        }
    }while(parent_index < _heap -> size);
    return value;
}
int main()
{
    heap *myheap = create_heap();
    insert_max_heap(myheap, 1);
    insert_max_heap(myheap, 10);
    insert_max_heap(myheap, 3);
    insert_max_heap(myheap, 11);
    insert_max_heap(myheap, 21);
    insert_max_heap(myheap, 50);
    insert_max_heap(myheap, 4);
    insert_max_heap(myheap, 33);
    insert_max_heap(myheap, 1);
    insert_max_heap(myheap, 10);
    insert_max_heap(myheap, 3);
    insert_max_heap(myheap, 11);
    insert_max_heap(myheap, 21);
    insert_max_heap(myheap, 50);
    insert_max_heap(myheap, 4);
    insert_max_heap(myheap, 33);
    while(!is_empty(myheap)){
        printf("%d ", extract_max_heap(myheap));
    }
    printf("\n");
    //50 50 33 33 21 21 11 11 10 10 4 4 3 3 1 1                                                  
    
    heap *myheap2 = create_heap();
    insert_min_heap(myheap2, 1);
    insert_min_heap(myheap2, 10);
    insert_min_heap(myheap2, 3);
    insert_min_heap(myheap2, 11);
    insert_min_heap(myheap2, 21);
    insert_min_heap(myheap2, 50);
    insert_min_heap(myheap2, 4);
    insert_min_heap(myheap2, 33);
    insert_min_heap(myheap2, 1);
    insert_min_heap(myheap2, 10);
    insert_min_heap(myheap2, 3);
    insert_min_heap(myheap2, 11);
    insert_min_heap(myheap2, 21);
    insert_min_heap(myheap2, 50);
    insert_min_heap(myheap2, 4);
    insert_min_heap(myheap2, 33);
    while(!is_empty(myheap2)){
        printf("%d ", extract_min_heap(myheap2));
    }
    // 1 1 3 3 4 4 10 10 11 11 21 21 33 33 50 50 
    return 0;
}

## Sorting algorithm
bubble sort:
Best Case Time Complexity: O(n)
Worst Case Time Complexity: O(n2)
Worst Case Time Complexity: O(n2)
* bubble sort:
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
* selection sort:
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
* insertion sort:

* merge sort:
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves

* quick sort:
It picks an element as pivot and partitions the given array around the picked pivot.

void swap(int *a, int *b){
    if(*a == *b)
    return;
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void bubble_sort(int *a, int size){
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size - i - 1; j++){
            if(a[j] > a[j+1]){
                swap(&a[j], &a[j+1]);
            }
        }
    }
}

int find_min_index(int arr[], int start_index, int end_index){
    int min_val = arr[start_index];
    int min_index = start_index;
    for(int i = start_index + 1; i <= end_index; i++){
        if(arr[i] < min_val){
            min_val = arr[i];
            min_index = i;
        }
    }
    return min_index;
}

void selection_sort(int arr[], int size){
    for(int i = 0; i < size - 1; i++){
        int min_index = find_min_index(arr, i, size - 1);
        if( i != min_index){
            swap(&arr[i], &arr[min_index]);
        }
    }
}

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

void merge(int *a, int start, int end){
    int size = end-start+1;
    int tmp[size];
    int middle = (start+end) >> 1;
    int i = start, j = middle+1, k = 0;

    while(i <= middle && j <= end){
        if(a[i] < a[j]){
            tmp[k] = a[i];
            i++;
        }
        else{
            tmp[k] = a[j];
            j++;
        }
        k++;
    }
    while(i <= middle){
        tmp[k] = a[i];
        k++;
        i++;
    }
    while(j <= end){
        tmp[k] = a[j];
        j++;
        k++;
    }
    memcpy(&a[start], tmp, size*sizeof(int));
    
}

void merge_sort(int *a, int start, int end){
    if(start == end){
        return;
    }
    int m = (start+end) >> 1;
    merge_sort(a, start, m);
    merge_sort(a, m+1, end);
    merge(a, start, end);
}

int partition(int *a, int start, int end){
    // partition: select pivot to be a[end]
    // arrange the array so that the numbers in the left side of pivot is smaller
    // the right side is larger
    int pivot = a[end];
    int pivot_index = start;
    for(int i = start; i <= end; i++){
        if(a[i] < pivot){
            swap(&a[i], &a[pivot_index]);
            pivot_index++;
        }
    }
    swap(&a[end], &a[pivot_index]);
    return pivot_index;
}

void quick_sort(int *a, int start, int end){
    if(start < end){
        int index = partition(a, start, end);
        quick_sort(a, start, index-1);
        quick_sort(a, index+1, end);
    }
}

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

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

## Graph
DFS: simliar the pre-order travel
BFS: Use queue
Number of paths

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


typedef struct _node{
    int value;
    struct _node *next;
}node;

typedef struct _queue{
    node *front;
    node *back;
    int size;
}queue;

void queue_init(queue **_queue){
    queue *new_queue = malloc(sizeof(queue));
    new_queue -> size = 0;
    new_queue -> front = NULL;
    new_queue -> back = NULL;
    *_queue = new_queue;
}

void enqueue(queue *_queue, int _value){
    node *new_node = malloc(sizeof(node));
    if(new_node != NULL){
        new_node -> value = _value;
        new_node -> next = NULL;
        if(_queue -> size == 0){
            _queue -> front = new_node;
            _queue -> back = new_node;
        }
        else{
            _queue -> back -> next = new_node;
            _queue -> back = new_node;    
        }
        _queue -> size++;
    }
}

int dequeue(queue *_queue){
    if(_queue -> size > 0){
        node *remove_node = _queue -> front;
        _queue -> front = _queue -> front -> next;
        int node_value = remove_node -> value;
        free(remove_node);
        _queue -> size--;
        return node_value;
    }
    else
    return -1;
}

typedef struct _edge_node{
    int vertex;
    int weight;
    struct _edge_node *next;
}edge_node;

// Adjacency list representation
typedef struct _graph{
    // An array of pointers of edge_node
    edge_node * *edges;
    int number_of_nodes;
    int number_of_edges;
    bool is_directed;
}graph;

graph *create_graph(int _number_of_nodes, bool _is_directed){
    graph * new_graph = (graph *)malloc(sizeof(graph));
    new_graph -> number_of_edges = 0;
    new_graph -> number_of_nodes = _number_of_nodes;
    new_graph -> is_directed = _is_directed;
    new_graph -> edges = (edge_node **)malloc(sizeof(edge_node *) * _number_of_nodes);
    for(int i = 0; i < _number_of_nodes; i++){
        new_graph -> edges[i] = NULL;
    }
    return new_graph;
}

void print_graph(graph *_graph){
    for(int i = 0; i < _graph -> number_of_nodes; i++){
        printf("%d -->", i);
        edge_node *travel_node = _graph -> edges[i];
        while(travel_node != NULL){
            printf("%d ", travel_node -> vertex);
            travel_node = travel_node -> next;
        }
        printf("\n");
    }
}

void add_edge(graph *graph, int u, int _vertex, int _weight){
    edge_node *new_edge_node = (edge_node *)malloc(sizeof(edge_node));
    new_edge_node -> vertex = _vertex;
    new_edge_node -> weight = _weight;
    new_edge_node -> next = graph -> edges[u];
    graph -> edges[u] = new_edge_node;
    if(graph -> is_directed == false){
        new_edge_node = (edge_node *)malloc(sizeof(edge_node));
        new_edge_node -> vertex = u;
        new_edge_node -> weight = _weight;
        new_edge_node -> next = graph -> edges[_vertex];
        graph -> edges[_vertex] = new_edge_node;
    }
    graph -> number_of_edges++;
}

edge_node *get_neighbors(graph *_graph, int node){
    return _graph -> edges[node];
}

void graph_dfs(graph *g, int start, bool visted[]){
    if(visted[start]){
        return;
    }
    visted[start] = true;
    printf("%d ", start);
    edge_node *e = get_neighbors(g, start);
    while(e != NULL){
        graph_dfs(g, e -> vertex, visted);
        e = e -> next;
    }
}

void graph_bfs(graph *g, int start, bool visted[]){
    queue *travel_queue;
    queue_init(&travel_queue);
    enqueue(travel_queue, start);
    while(travel_queue -> size > 0){
        int v = dequeue(travel_queue);
        if(!visted[v]){
            printf("%d ", v);
            visted[v] = true;
            edge_node *neb = get_neighbors(g, v);
            while(neb != NULL){
                if(visted[neb -> vertex] == false){
                    enqueue(travel_queue, neb -> vertex);
                }
                neb = neb -> next;
            }
        }
    }
    free(travel_queue);
}

int graph_number_of_paths(graph *g, int start, int end, bool visted[]){
    if(start == end){
        return 1;
    }
    visted[start] = true;
    edge_node *neb = get_neighbors(g, start);
    int sum = 0;
    while(neb != NULL){
        if(!visted[neb -> vertex]){
            sum += graph_number_of_paths(g, neb -> vertex, end, visted);
        }
        neb = neb -> next;
    }
    visted[start] = false;
    return sum;
}

int main()
{
    graph *my_graph = create_graph(13, false);
    add_edge(my_graph, 0, 1, 1);
    add_edge(my_graph, 1, 2, 12);
    add_edge(my_graph, 1, 3, 10);
    add_edge(my_graph, 2, 4, 11);
    add_edge(my_graph, 2, 5, 13);
    add_edge(my_graph, 3, 5, 12);
    add_edge(my_graph, 3, 7, 13);
    add_edge(my_graph, 4, 6, 9);
    add_edge(my_graph, 5, 6, 7);
    add_edge(my_graph, 6, 7, 15);
    add_edge(my_graph, 8, 9, 12);
    add_edge(my_graph, 8, 10, 10);
    add_edge(my_graph, 9, 10, 10);
    add_edge(my_graph, 10, 11, 9);
    add_edge(my_graph, 11, 12, 10);
    print_graph(my_graph);
    
    bool visted[13] = {0};
    for(int i = 0; i < 13; i++)
    graph_dfs(my_graph, i, visted);
    printf("\n");
    
    bool visted2[13] = {0};
    for(int i = 0; i<13; i++)
    graph_bfs(my_graph, i, visted2);
    printf("\n");
    
    bool visted3[13] = {0};
    int start = 4;
    int end = 6;
    printf("%d ways to go from %d to %d", graph_number_of_paths(my_graph,start,end,visted3), start, end);
    return 0;
}

## Dijkstra shortest path

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

typedef struct _edge{
    int vertex;
    int weight;
}edge;

typedef struct _heap{
    edge *arr;
    int size;
}heap;

heap *create_heap(int size){
    heap *new_heap = (heap *)malloc(sizeof(heap));
    new_heap -> arr = (edge *)calloc(sizeof(edge), size);
    new_heap -> size = 0;
    for(int i = 0; i < size; i++){
        new_heap -> arr[i].vertex = 0;
        new_heap -> arr[i].weight = 0;
    }
    return new_heap;
}

int is_empty(heap *_heap){
    return _heap -> size == 0 ? 1 : 0;
}

void swap(edge *a, edge *b){
    edge tmp = *b;
    *b = *a;
    *a = tmp;
}

int max(int a, int b){
    return a > b ? a : b;
}

int min(int a, int b){
    return a < b ? a : b;
}

void insert_min_heap(heap *_heap, edge value){
    _heap -> size++; // do not use index 0 to store value
    _heap -> arr[_heap -> size] = value;
    int index = _heap -> size;
    while(index > 1 && _heap -> arr[index].weight < _heap -> arr[index/2].weight){
        swap(&_heap -> arr[index], &_heap -> arr[index/2]);
        index = index / 2;
    }
}

edge extract_min_heap(heap *_heap){
    edge e = {0,0};
    if(_heap -> size == 0){
        return e;
    }
    edge value = _heap -> arr[1];
    // swap the head and tail
    
    _heap -> arr[1].weight = _heap -> arr[_heap -> size].weight;
    _heap -> arr[1].vertex = _heap -> arr[_heap -> size].vertex;
    _heap -> size--;
    int parent_index = 1;
    int left_child_index = 0;
    int right_child_index = 0;
    do{
        left_child_index = parent_index * 2;
        right_child_index = parent_index * 2 + 1;
         if(_heap -> size < left_child_index){
            break;
        }
        if(_heap -> arr[parent_index].weight < min(_heap -> arr[left_child_index].weight, _heap -> arr[right_child_index].weight)){
            break;
        }
        // Heap node could be full or left child only
        if(_heap -> size == left_child_index || _heap -> arr[left_child_index].weight < _heap -> arr[right_child_index].weight){
              swap(&_heap -> arr[left_child_index], &_heap -> arr[parent_index]);
            parent_index = left_child_index;
        }
        else{
            swap(&_heap -> arr[right_child_index], &_heap -> arr[parent_index]);
            parent_index = right_child_index;
        }
    }while(parent_index < _heap -> size);
    return value;
}

void print_heap(heap *h){
    int l = h -> size;
    for(int i = 1; i <= l; i++){
        printf("{%d, %d} ", h ->arr[i].vertex, h ->arr[i].weight);
    }
    printf("\n");
}

typedef struct _edge_node{
    int vertex;
    int weight;
    struct _edge_node *next;
}edge_node;

// Adjacency list representation
typedef struct _graph{
    // An array of pointers of edge_node
    edge_node * *edges;
    int number_of_nodes;
    int number_of_edges;
    bool is_directed;
}graph;

graph *create_graph(int _number_of_nodes, bool _is_directed){
    graph * new_graph = (graph *)malloc(sizeof(graph));
    new_graph -> number_of_edges = 0;
    new_graph -> number_of_nodes = _number_of_nodes;
    new_graph -> is_directed = _is_directed;
    new_graph -> edges = (edge_node **)malloc(sizeof(edge_node *) * _number_of_nodes);
    for(int i = 0; i < _number_of_nodes; i++){
        new_graph -> edges[i] = NULL;
    }
    return new_graph;
}

void print_graph(graph *_graph){
    for(int i = 0; i < _graph -> number_of_nodes; i++){
        printf("%d -->", i);
        edge_node *travel_node = _graph -> edges[i];
        while(travel_node != NULL){
            printf("%d ", travel_node -> vertex);
            travel_node = travel_node -> next;
        }
        printf("\n");
    }
}

void add_edge(graph *graph, int u, int _vertex, int _weight){
    edge_node *new_edge_node = (edge_node *)malloc(sizeof(edge_node));
    new_edge_node -> vertex = _vertex;
    new_edge_node -> weight = _weight;
    new_edge_node -> next = graph -> edges[u];
    graph -> edges[u] = new_edge_node;
    if(graph -> is_directed == false){
        new_edge_node = (edge_node *)malloc(sizeof(edge_node));
        new_edge_node -> vertex = u;
        new_edge_node -> weight = _weight;
        new_edge_node -> next = graph -> edges[_vertex];
        graph -> edges[_vertex] = new_edge_node;
    }
    graph -> number_of_edges++;
}

edge_node *get_neighbors(graph *_graph, int node){
    return _graph -> edges[node];
}

#define NIL -1 
#define INFINITY 0xcf
void dijkistra(graph *g, int start, int dest){
    heap *h = create_heap(g -> number_of_edges);
    int distance[g -> number_of_nodes];
    int parent[g -> number_of_nodes];
    for(int i = 0; i < g -> number_of_nodes; i++){
        distance[i] = INFINITY;
        parent[i] = NIL;
    }
    edge e = {start, 0};
    insert_min_heap(h, e);
    print_heap(h);
    distance[start] = 0;
    parent[start] = NIL;
    while(h -> size > 0){
        edge u = extract_min_heap(h);
        printf("select: %d %d\n", u.vertex, u.weight);
        edge_node *e = get_neighbors(g, u.vertex);
        while(e != NULL){
            printf("(%d) from %d to neighbor %d weight %d %d\n",distance[u.vertex], u.vertex , e -> vertex, e->weight ,distance[e -> vertex]);
            if(distance[u.vertex] + (e -> weight) < distance[e -> vertex]){
                distance[e -> vertex] = distance[u.vertex] + e -> weight;
                parent[e -> vertex] = u.vertex;
                edge ed = {e->vertex, distance[e->vertex]};
                insert_min_heap(h, ed);
                printf("  add\n");
                }
            else{
                printf("  negelect\n");
            }
            e = e -> next;
        }
        print_heap(h);
    }
    int path[g -> number_of_nodes];
    int pathSize = 0;
    int d = dest;
    do{
        path[pathSize++] = d;
        d = parent[d];
    }while(d != NIL);
    printf("shortest path from %d to %d is %d \n", start, dest, distance[dest]);
    for(int i = pathSize - 1; i >= 0; i--){
        printf("%d ", path[i]);
    }
}

int main()
{
    graph *my_graph = create_graph(12 + 1, false);
    add_edge(my_graph, 1, 2, 12);
    add_edge(my_graph, 1, 3, 10);
    add_edge(my_graph, 2, 4, 11);
    add_edge(my_graph, 2, 5, 13);
    add_edge(my_graph, 3, 5, 12);
    add_edge(my_graph, 3, 7, 13);
    add_edge(my_graph, 4, 6, 9);
    add_edge(my_graph, 5, 6, 7);
    add_edge(my_graph, 6, 7, 15);
    add_edge(my_graph, 6, 10, 13);
    add_edge(my_graph, 6, 11, 11);
    add_edge(my_graph, 7, 8, 7);
    add_edge(my_graph, 8, 9, 12);
    add_edge(my_graph, 8, 10, 10);
    add_edge(my_graph, 9, 10, 10);
    add_edge(my_graph, 10, 11, 9);
    add_edge(my_graph, 11, 12, 10);
    dijkistra(my_graph, 1 ,12);
    // shortest path from 1 to 12 is 50                                                                                         
    // 1 3 5 6 11 12
    return 0;
}

## Factorial
n! = 1x2x3...xn

int fact(int n){
    if(n == 0){
        return 1;
    }
    return n * fact(n - 1);
}

## Fibonacci Series
Fibnacci Series: 1 1 2 3 5 8 13 21 .....

- Recursive solution: O(2^n)

int fib(int n){
    if(n == 1 || n == 2){
        return 1;
    }
    return (fib(n-1) + fib(n-2));
}

- Memorized solution: O(n)

int fib_memo(int n, int *memo){
    if(n == 1 || n ==2){
        return 1;
    }
    if(memo[n] != 0){
        return n;
    }
    else{
        int result = (fib(n-1) + fib(n-2));
        memo[n] = result;
        return result;
    };
}

- Dynamic programming: O(n), no recursion needed

// buttom up approach
int fib_dp(int n){
    if(n == 1 || n ==2){
        return 1;
    }
    int arr[n+1];
    arr[1] = 1;
    arr[2] = 1;
    for(int i = 3; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}