Hello!
This repository is filled with code implementations of fundamental and some advance data structures, sorting algorithms, and graph traversal algorithms. This codebase was written in C# (you're welcome Microsofters and Unity developers). However, I made sure to make variables and functions as clear as possible so that it can be easily read and understood in every other programming language.
Feel free to look over my C# references and don't be shy if you find something wrong, found better ways to do things, or want to contribute to the bettering of this repository. Anything helps and is welcomed!
This repository was originally written in my notebook while I was studying for coding interviews and bettering my software engineering skills. I had decided to post my notes and implementations online so I have a digital copy of all the notes and implementation I took the time and hard work to figure out. I also decided to create this repository because I did have some difficulties finding resources for implementing data structures and algorithms in C#, especially for the more advance concepts. Generally, I found a lot of Java, C++, and Python resources but I thought it would be great for C# enthusiasts to have fundamentals they'd need to know all in one place.
This reference is divided into four folders: data structure, sorting algorithm, graph theory, and miscellaneous algorithms. Within those folders, there are sub folders for each individual concept. This is so we can add implementations in other languages, extra files for testing and general notes.
Note that each main.cs file contains the actual classes for the various data structures and algorithms but they do not contain Main functions. You may clone or test these files on your own, although in the future I may add my own tests and Main functions in this repository in the future to better help those using this as a resource.
- C#
- Lua
- Java
- Python
- More to come...
More to come!
Data Structures are essential tools for programmers that help store, organize, and manipulate data. There are many of them and it is important to know when best to use each structure and how they generally work.
Most programming languages have data structures built into their languages and could be called without having to construct a class yourself. Commonly, arrays are built into most languages and C# has classes for Stacks, Queues, and Dictionaries (which we call Hash Tables in this repository) built in, as well. However, you can construct your own variants of these data structures or, for data structures such as Priority Queues and Tries, you would have to create your own implementation for structures not already built into C#.
Sorting algorithms are self explanatory: they are algorithms which serve to sort a collection of data. There are many types of sorting algorithms, some fast (Quick Sort) and others terribly slow (Bubble Sort), and some space intensive and some not. Here is a neat video of common sorting algorithms visualized.
Sorting algorithms are important to study as they usually open up to other important programming concepts, such as heapifying with Heap Sort and recursion and divide and conquer with Merge Sort.
Sorting algorithms are also important to study as they are great ways to ease into Big O notation and space and time trade offs. An example, Bubble Sort may be incredibly slow but if your software happens to not care about speed and needs to fit into a small file and you prefer a simple sorting implementation, it could be a good choice. However, if space is not an issue you can go with a faster sort algorithm such as Merge Sort.
C# has an Array.Sort method built in which runs a sorting algorithm based on the partition size of what's to be sorted. A small collection of elements, a partition size of less than 16 elements, will have C# run an Insertion Sort Algorithm. If the partitions exceeds 2 * LogN where N is the range of the input array, C# uses Heap Sort. Otherwise, for most instances, C# will run Quick Sort. Note that the worst case time complexity of the Sort Method is O(n Log n) and the sorting is unstable, meaning that if two elements are equal they may not maintain their order with each other.
Graph Theory is the study of graphs and how the relationships between various entities could be best represented. Graphs are made up of vertices and edges, also called nodes and links. Using a graph that represents a neighborhood, think of a vertex as each individual house and an edge as the route between one house and the others.
Note that graphs can either be directed or undirected. A directed graph means that edges have a direction to another vertex that it is pointing to, meanwhile an undirected graph is a graph where the edges do not have this property.
Graphs can be represented in many ways but in this repository we focus on Adjacency Matrices and Adjacency Lists. An adjacency matrix is constructed via a 2D array while an Adjacency List can be constructed in many ways, such as a Hash Table with key value pairs of vertex to that vertex's list of edges. An adjacency matrix takes up a lot of space and is typically slower compared to the list but it is easier to implement. Adjacency lists are faster and space efficient but larger data sets can make implementing algorithms more complicated that it should be. It is important to know how to implement both kinds of graphs and when best to use them.
Graph theory is a great way to solve many kinds of relational problems and is widely used in software engineering. Some real world applications are constructing the relationships in a social network site, path finding in games and GPS, and garbage collection for programming languages.
-
Major one: Search Algorithms Folder incorrectly named. Must be changed to "Sort Algorithms" and all links must point to renamed folder
-
Update codebase to adhere to Google's Coding Style Guide for C# and other supported languages