Hi, I'm Ataias Reis

Programmer, made in Brazil, Alma mater University of Brasilia

30 days of code in Go: Day 22 - QuickSort

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!

Tags
comments powered by Disqus