Hi there! Today’s challenge is another algorithm that I learned more in detail
in the *Algorithms: Design and Analysis, Part 1* course from Coursera:
*QuickSort*. This algorithm chooses a pivot and does a partial sort around that
pivot, having all elements less than the pivot to its left and all greater to
its right, considering we want the number in increasing order. The main function
is `qsort`

which calls the function to choose a pivot and another to partition
around the pivot.

The way I learned in class considered the pivot to be the first element of the
array and then I had indexes `i`

and `j`

to separate the portions of the array.
All elements to the left of position `i`

were smaller than the pivot, excluding
the pivot itself in position 0. This left all elements greater than the pivot to
the right of position `i`

. Something I took some time to understand was that
this is actually generic. I can choose any pivot as long as I swap it with the
first element.

There were three ways of choosing a pivot that I considered when doing the
assignment, but here I present just the last one, namely the median of three
method. I consider the elements in the first, middle and last positions in the
array and then I take the median of these three elements to be the pivot. The
`getPivot`

function returns the index of the pivot so that the `qsort`

function
can use it. In the end of a `qsort`

call, the element is sorted in place and the
number of comparisons is returned. For each recursive call of an array of size
`m`

, I count `m-1`

comparisons.

The solution is presented below. Notice I expect the number of elements `n`

in
the array as the first input and then `n`

elements separated by `\n`

.

```
package main
import (
"fmt"
)
// returns the index of the median here
func argmedian(index, values []int) int {
swaps := 1
// simple bubble sort to sort three values
// and then we return the middle value
for swaps > 0 {
swaps = 0
for i := 0; i < len(index)-1; i++ {
if values[i+1] < values[i] {
swap(values, i, i+1)
swap(index, i, i+1)
swaps++
}
}
}
return index[1]
}
func getPivot(a []int) int {
index := make([]int, 3)
values := make([]int, 3)
index[0] = 0
values[0] = a[0]
if len(a)%2 == 0 {
index[1] = len(a)/2 - 1
values[1] = a[len(a)/2-1]
} else {
index[1] = len(a) / 2
values[1] = a[len(a)/2]
}
index[2] = len(a) - 1
values[2] = a[len(a)-1]
return argmedian(index, values)
}
func swap(a []int, i, j int) {
a[i], a[j] = a[j], a[i]
}
func partition(a []int, pivot_i int) (int, int) {
swap(a, pivot_i, 0)
p := a[0] // pivot
finalPlace := 0
if len(a) > 2 {
i := 0
pivotNotInPlace := false
for j := 1; j < len(a); j++ {
if a[j] < p {
i++
swap(a, i, j)
pivotNotInPlace = true
}
}
// pivot in rightful position
// case of len(a) > 2
if pivotNotInPlace {
a[0] = a[i]
a[i] = p
finalPlace = i
}
} else if len(a) == 2 {
if a[1] < p {
a[0] = a[1]
a[1] = p
finalPlace = 1
}
}
return finalPlace, len(a) - 1
}
func qsort(a []int) int {
n := 0 // number of comparisons
if len(a) <= 1 {
return n
}
pivot_index := getPivot(a)
i, n0 := partition(a, pivot_index)
n += n0
n += qsort(a[:i])
n += qsort(a[i+1:])
return n
}
func main() {
// Input file has N
// in the first line
N := 0
fmt.Scanf("%d\n", &N)
// allocate memory
X := make([]int, N)
for i := 0; i < N; i++ {
fmt.Scanf("%d\n", &X[i])
}
// n is the number of comparisons
// quicksort has done
n := qsort(X)
for i := 0; i < N; i++ {
fmt.Printf("%d\n", X[i])
}
fmt.Printf("#Comparisons: %d\n", n)
}
```

That’s all for this day of coding in Go. Thanks for readings!