# Algorithms and Data Structures in Go - Part 1 > Published at 2023-04-09T22:31:42+03:00 ``` ,_---~~~~~----._ _,,_,*^____ _____``*g*\"*, / __/ /' ^. / \ ^@q f [ @f | @)) | | @)) l 0 _/ \`/ \~____ / __ \_____/ \ | _l__l_ I } [______] I ] | | | | ] ~ ~ | | | | | ``` This is the first blog post about my Algorithms and Data Structures in Go series. I am not a Software Developer in my day job. In my current role, programming and scripting skills are desirable but not mandatory. I have been learning about Data Structures and Algorithms many years ago at University. I thought it would be fun to revisit/refresh my knowledge here and implement many of the algorithms in Go. => ./2023-04-09-algorithms-and-data-structures-in-golang-part-1.gmi 2023-04-09 Algorithms and Data Structures in Go - Part 1 (You are currently reading this) This post is about setting up some basic data structures and methods for this blog series. I promise, everything will be easy to follow in this post. It will become more interesting later in this series. ## Type constraints First, the package `ds` (data structures) defines the `types.go`. All examples will either operate on the `Integer` or `Number` type: ```go package ds import ( "golang.org/x/exp/constraints" ) type Integer interface { constraints.Integer } type Number interface { constraints.Integer | constraints.Float } ``` ## ArrayList Next comes the `arraylist.go`, which defines the underlying data structure all the algorithms of this series will use. `ArrayList` is just a type alias of a Go array (or slice) with custom methods on it: ```go package ds import ( "fmt" "math/rand" "strings" ) type ArrayList[V Number] []V func NewArrayList[V Number](l int) ArrayList[V] { return make(ArrayList[V], l) } ``` As you can see, the code uses Go generics, which I refactored recently. Besides the default constructor (which only returns an empty `ArrayList` with a given capacity), there are also a bunch of special constructors. `NewRandomArrayList` is returning an `ArrayList` with random numbers, `NewAscendingArrayList` and `NewDescendingArrayList` are returning `ArrayList`s in either ascending or descending order. They all will be used later on for testing and benchmarking the algorithms. ```go func NewRandomArrayList[V Number](l, max int) ArrayList[V] { a := make(ArrayList[V], l) for i := 0; i < l; i++ { if max > 0 { a[i] = V(rand.Intn(max)) continue } a[i] = V(rand.Int()) } return a } func NewAscendingArrayList[V Number](l int) ArrayList[V] { a := make(ArrayList[V], l) for i := 0; i < l; i++ { a[i] = V(i) } return a } func NewDescendingArrayList[V Number](l int) ArrayList[V] { a := make(ArrayList[V], l) j := l - 1 for i := 0; i < l; i++ { a[i] = V(j) j-- } return a } ``` ## Helper methods The `FirstN` method only returns the first N elements of the `ArrayList`. This is useful for printing out only parts of the data structure: ```go func (a ArrayList[V]) FirstN(n int) string { var sb strings.Builder j := n l := len(a) if j > l { j = l } for i := 0; i < j; i++ { fmt.Fprintf(&sb, "%v ", a[i]) } if j < l { fmt.Fprintf(&sb, "... ") } return sb.String() } ``` The `Sorted` method checks whether the `ArrayList` is sorted. This will be used by the unit tests later on: ```go func (a ArrayList[V]) Sorted() bool { for i := len(a) - 1; i > 0; i-- { if a[i] < a[i-1] { return false } } return true } ``` And the last utility method used is `Swap`, which allows swapping the values of two indices in the `ArrayList`: ```go func (a ArrayList[V]) Swap(i, j int) { aux := a[i] a[i] = a[j] a[j] = aux } ``` ## Sleep sort Let's implement our first algorithm, sleep sort. Sleep sort is a non-traditional and unconventional sorting algorithm based on the idea of waiting a certain amount of time corresponding to the value of each element in the input `ArrayList`. It's more of a fun, creative concept rather than an efficient or practical sorting technique. This is not a sorting algorithm you would use in any production code. As you can imagine, it is quite an inefficient sorting algorithm (it's only listed here as a warm-up exercise). This sorting method may also return false results depending on how the Goroutines are scheduled by the Go runtime. ```go package sort import ( "codeberg.org/snonux/algorithms/ds" "sync" "time" ) func Sleep[V ds.Integer](a ds.ArrayList[V]) ds.ArrayList[V] { sorted := ds.NewArrayList[V](len(a)) numCh := make(chan V) var wg sync.WaitGroup wg.Add(len(a)) go func() { wg.Wait() close(numCh) }() for _, num := range a { go func(num V) { defer wg.Done() time.Sleep(time.Duration(num) * time.Second) numCh <- num }(num) } for num := range numCh { sorted = append(sorted, num) } return sorted } ``` This Go code implements the sleep sort algorithm using generics and goroutines. The main function `Sleep[V ds.Integer](a ds.ArrayList[V]) ds.ArrayList[V]` takes a generic `ArrayList` as input and returns a sorted `ArrayList`. The code creates a separate goroutine for each element in the input array, sleeps for a duration proportional to the element's value, and then sends the element to a channel. Another goroutine waits for all the sleeping goroutines to finish and then closes the channel. The sorted result `ArrayList` is constructed by appending the elements received from the channel in the order they arrive. The `sync.WaitGroup` is used to synchronize goroutines and ensure that all of them have completed before closing the channel. ### Testing For testing, we only allow values up to 10, as otherwise, it would take too long to finish: ```go package sort import ( "fmt" "testing" "codeberg.org/snonux/algorithms/ds" ) func TestSleepSort(t *testing.T) { a := ds.NewRandomArrayList[int](10, 10) a = Sleep(a) if !a.Sorted() { t.Errorf("Array not sorted: %v", a) } } ``` As you can see, it takes `9s` here for the algorithm to finish (which is the highest value in the `ArrayList`): ```sh ❯ go test ./sort -v -run SleepSort === RUN TestSleepSort --- PASS: TestSleepSort (9.00s) PASS ok codeberg.org/snonux/algorithms/sort 9.002s ``` I won't write any benchmark for sleep sort; that will be done for the algorithms to come in this series :-). E-Mail your comments to `paul@nospam.buetow.org` :-) => ../ Back to the main site