This repository contains a collection of implementations of common data structures and algorithms in C.
The data structures included in this repository are:
- Stack
- Array
- Binary tree
- Linked list
Graph traversal algorithms are algorithms for visiting every vertex in a graph. Included in this repo
- Depth-first search (DFS) is a graph traversal algorithm that explores a graph by visiting the vertices in depth, implemented using a stack.
- Breadth-first search (BFS) is a graph traversal algorithm that explores a graph by visiting the vertices in breadth, implemented using a queue.
- Prim's algorithm: A greedy algorithm for finding a minimum spanning tree of a graph.
- Kruskal's algorithm: A greedy algorithm for finding a minimum spanning tree of a graph.
-
Bubble Sort: Bubble sort is a simple sorting algorithm that works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. The algorithm continues iterating through the list until there are no more swaps needed.
-
Insertion Sort: sorting algorithm that works by building the sorted list one element at a time. The algorithm starts with an empty sorted list and then repeatedly inserts the next element into the correct position in the list.
-
Merge Sort: divide-and-conquer sorting algorithm that works by recursively dividing the list into two halves, sorting each half, and then merging the two sorted halves back together.
-
Quick Sort: another divide-and-conquer sorting algorithm that works by partitioning the list around a pivot element. The algorithm then recursively sorts the two sublists created by the partition.
-
Selection Sort: sorting algorithm that works by finding the smallest element in the list and swapping it with the first element. The algorithm then repeats this process for the remaining elements in the list. Selection sort is a simple sorting algorithm, but it is not efficient.
| Sorting Algorithm | Pros | Cons |
|---|---|---|
| Bubble Sort | Stable, simple to implement | Inefficient |
| Insertion Sort | Stable, simple to implement | Inefficient for large lists |
| Merge Sort | Efficient | Not stable, additional memory required |
| Quick Sort | Efficient | Not stable, can be inefficient for small lists |
| Selection Sort | Simple to implement, stable | Inefficient |