path: root/gemfeed/2023-04-09-algorithms-and-data-structures-in-golang-part-1.md

# 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 Go - Part 1 (You are currently reading this)](./2023-04-09-algorithms-and-data-structures-in-golang-part-1.md)  

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 `foo@paul.cyou` :-)

[Back to the main site](../)