I wrote about data structures in my previous article. Those are basic abstract data structures that every programmer must know and how to implement them in Go.
There are also operations and algorithms that every programmer must know. An algorithm is a set of instructions designed to perform a specific task. Here, let me show you what operations they are and a few of the basic algorithms.
I updated my article about Big-O Notation. Before getting started, feel free to get to know about the big-O (O) notation. Those notations describe the time and space complexity of an algorithm. It is important to understand the complexity of an algorithm. So, we can optimize it.
We have NOT (~) symbol in C, but not in Go. To achieve NOT, we can use XOR (^). We XOR the number to itself.
There is no negative decimal in binary. To achieve a negative decimal, we calculated by 256 minus the number.
Regular Expressions
A regular expression (shortened as regex or regexp) is a sequence of characters that define a search pattern. Maybe you already know that. Here is how we implement it in Go. I brought some examples.
Take a look at the regexp package for more details.
Sortings
A sorting algorithm is an algorithm that puts elements of a list in a certain order. There are many sorting algorithms. Some of the popular sorting algorithms are Insertion Sort, Selection Sort, Bubble Sort, and Merge Sort. We don't cover any of those sorting algorithms here. But I brought some sorting examples with Go instead.
packagemainimport("fmt""sort")typepersonstruct{namestringageint}typebyAge[]person// Len ...
func(abyAge)Len()int{returnlen(a)}// Less ...
func(abyAge)Less(i,jint)bool{returna[i].age<a[j].age}// Swap ...
func(abyAge)Swap(i,jint){a[i],a[j]=a[j],a[i]}funcmain(){people:=[]person{{"Bob",31},{"John",42},{"Michael",17},{"Jenny",26},}fmt.Println(people)sort.Sort(byAge(people))fmt.Println(people)sort.Slice(people,func(i,jint)bool{returnpeople[i].name<people[j].name})fmt.Println(people)}
Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. It has a base state. It minimizes the problem recursively by calling itself. It simplifies the source code.
Dynamic Programming is an optimization to the recursion method. The concept stores the results of subproblems to avoid recomputation and optimizes or reduces the complexity.
The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into subproblems, to solve them in turn, and to compose their solutions to solve the given problem.
Backtracking is a general algorithm for finding solutions to some computational problems, which incrementally builds candidates to the solution and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution.
In short, I implemented those operations and algorithms in Go. Maybe later I will explain every single algorithm in detail. For now, feel free to visit my references for further explanation, The source code can be found here, https://github.com/aristorinjuang/go-algorithms.