2017-02-12-qsort-base.go

package qsort

import "math/rand"

func QuickSort(data Interface, l int, r int) {
  if l >= r {
    return
  }
  
  pivot := partition(data, l, r)
  
  QuickSort(data, l, pivot-1)
  QuickSort(data, pivot+1, r)
}

func partition(data Interface, l, r int) int {
  pivot := randomInt(l, r)
  
  if pivot != l {
    data.Swap(pivot, l)
  }
  
  i := l + 1
  for j := l + 1; j <= r; j++ {
    if data.Less(j, l) {
      if i != j {
        data.Swap(i, j)
      }
      i++
    }
  }
  data.Swap(l, i-1)
  return i - 1
}

func randomInt(min, max int) int {
  return rand.Intn(max-min) + min
}

// From Golang source code:
// https://github.com/golang/go/blob/master/src/sort/sort.go
type Interface interface {
  // Len is the number of elements in the collection.
  Len() int
  // Less reports whether the element with
  // index i should sort before the element with index j.
  Less(i, j int) bool
  // Swap swaps the elements with indexes i and j.
  Swap(i, j int)
}

// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
type IntSlice []int

func (p IntSlice) Len() int           { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }