sort.Interface
Like string formatting, sorting is a frequently used operation in many programs. Although a minimal Quicksort can be written in about 15 lines, a robust implementation is much longer, and it is not the kind of code we should wish to write anew or copy each time we need it.
Fortunately, the sort
package provides in-place sorting of any
sequence according to any ordering function.
Its design is rather unusual.
In many languages, the sorting algorithm is associated with the sequence
data type, while the ordering function is associated with the type of
the elements.
By contrast, Go’s sort.Sort
function assumes nothing about the
representation of either the sequence or its elements.
Instead, it uses an
interface, sort.Interface
, to specify the contract between the
generic sort algorithm and each sequence type that may be sorted.
An implementation of this interface determines both the concrete
representation of the sequence, which is often a slice, and
the desired ordering of its elements.
An in-place sort algorithm needs three things—the length of the
sequence, a means of comparing two elements, and a way to swap two
elements—so they are the three methods of sort.Interface
:
package sort type Interface interface { Len() int Less(i, j int) bool // i, j are indices of sequence elements Swap(i, j int) }
To sort any sequence, we need to define a type that implements these
three methods, then apply sort.Sort
to an instance of that
type.
As perhaps the simplest example, consider sorting a slice of
strings.
The new type StringSlice
and its Len
, Less
, and
Swap
methods are shown below.
type StringSlice []string func (p StringSlice) Len() int { return len(p) } func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] } func (p StringSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
Now we can sort a slice of strings, names
, by converting the slice
to a StringSlice
like this:
sort.Sort(StringSlice(names))
The conversion yields a slice value with the same length, capacity,
and underlying array as names
but with a type that has the three methods required for sorting.
Sorting a slice of strings is so common that the sort
package
provides the StringSlice
type, as well as a function called
Strings
so that the call above can be simplified to
sort.Strings(names)
.
The technique here is easily adapted to other sort orders, for
instance, to ignore capitalization or special characters.
(The Go program that sorts index terms and page numbers for this book
does this, with extra logic for Roman numerals.)
For more complicated sorting, we use the same idea, but with more
complicated data structures or more complicated implementations of
the sort.Interface
methods.
Our running example for sorting will be a music playlist, displayed as a table. Each track is a single row, and each column is an attribute of that track, like artist, title, and running time. Imagine that a graphical user interface presents the table, and that clicking the head of a column causes the playlist to be sorted by that attribute; clicking the same column head again reverses the order. Let’s look at what might happen in response to each click.
The variable tracks
below contains a playlist.
(One of the authors apologizes for the other author’s musical tastes.)
Each element is indirect, a pointer to a Track
.
Although the code below would work if we stored the Track
s
directly, the sort function will swap many pairs of elements, so it
will run faster if each element is a pointer, which is a single machine word,
instead of an entire Track
, which might be eight words or more.
type Track struct { Title string Artist string Album string Year int Length time.Duration } var tracks = []*Track{ {"Go", "Delilah", "From the Roots Up", 2012, length("3m38s")}, {"Go", "Moby", "Moby", 1992, length("3m37s")}, {"Go Ahead", "Alicia Keys", "As I Am", 2007, length("4m36s")}, {"Ready 2 Go", "Martin Solveig", "Smash", 2011, length("4m24s")}, } func length(s string) time.Duration { d, err := time.ParseDuration(s) if err != nil { panic(s) } return d }
The printTracks
function prints the playlist as a table.
A graphical display would be nicer, but this little routine uses the
text/tabwriter
package to produce a table whose columns are
neatly aligned and padded as shown below.
Observe that *tabwriter.Writer
satisfies io.Writer
.
It collects each piece of data written to it; its Flush
method formats the entire table and writes it to os.Stdout
.
func printTracks(tracks []*Track) { const format = "%v %v %v %v %v " tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0) fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length") fmt.Fprintf(tw, format, "-----", "------", "-----", "----", "------") for _, t := range tracks { fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length) } tw.Flush() // calculate column widths and print table }
To sort the playlist by the Artist
field, we define a new slice
type with the necessary Len
, Less
, and Swap
methods,
analogous to what we did for StringSlice
.
type byArtist []*Track func (x byArtist) Len() int { return len(x) } func (x byArtist) Less(i, j int) bool { return x[i].Artist < x[j].Artist } func (x byArtist) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
To call the generic sort routine, we must first convert tracks
to the new type, byArtist
, that defines the order:
sort.Sort(byArtist(tracks))
After sorting the slice by artist, the output from printTracks
is
Title Artist Album Year Length ----- ------ ----- ---- ------ Go Ahead Alicia Keys As I Am 2007 4m36s Go Delilah From the Roots Up 2012 3m38s Ready 2 Go Martin Solveig Smash 2011 4m24s Go Moby Moby 1992 3m37s
If the user requests “sort by artist” a second time, we’ll sort the
tracks in reverse. We needn’t define a new type byReverseArtist
with an inverted Less
method, however, since the sort
package provides a
Reverse
function that transforms any sort order to its inverse.
sort.Sort(sort.Reverse(byArtist(tracks)))
After reverse-sorting the slice by artist,
the output from printTracks
is
Title Artist Album Year Length ----- ------ ----- ---- ------ Go Moby Moby 1992 3m37s Ready 2 Go Martin Solveig Smash 2011 4m24s Go Delilah From the Roots Up 2012 3m38s Go Ahead Alicia Keys As I Am 2007 4m36s
The sort.Reverse
function deserves a closer look since it
uses composition (§6.3), which is an important idea.
The sort
package defines an unexported type reverse
,
which is a struct that embeds a sort.Interface
.
The Less
method for reverse
calls the Less
method
of the embedded sort.Interface
value, but with the indices
flipped, reversing the order of the sort results.
package sort type reverse struct{ Interface } // that is, sort.Interface func (r reverse) Less(i, j int) bool { return r.Interface.Less(j, i) } func Reverse(data Interface) Interface { return reverse{data} }
Len
and Swap
, the other two methods of reverse
,
are implicitly provided by the original sort.Interface
value
because it is an embedded field.
The exported function Reverse
returns an instance
of the reverse
type that contains the original
sort.Interface
value.
To sort by a different column, we must define a new type, such as
byYear
:
type byYear []*Track func (x byYear) Len() int { return len(x) } func (x byYear) Less(i, j int) bool { return x[i].Year < x[j].Year } func (x byYear) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
After sorting tracks
by year using
sort.Sort(byYear(tracks))
, printTracks
shows a
chronological listing:
Title Artist Album Year Length ----- ------ ----- ---- ------ Go Moby Moby 1992 3m37s Go Ahead Alicia Keys As I Am 2007 4m36s Ready 2 Go Martin Solveig Smash 2011 4m24s Go Delilah From the Roots Up 2012 3m38s
For every slice element type and every ordering function we need, we
declare a new implementation of sort.Interface
.
As you can see, the Len
and Swap
methods
have identical definitions for all slice types.
In the next example, the concrete type customSort
combines a
slice with a function, letting us define a new sort order by writing only
the comparison function.
Incidentally, the concrete types that implement sort.Interface
are not always slices; customSort
is a struct type.
type customSort struct { t []*Track less func(x, y *Track) bool } func (x customSort) Len() int { return len(x.t) } func (x customSort) Less(i, j int) bool { return x.less(x.t[i], x.t[j]) } func (x customSort) Swap(i, j int) { x.t[i], x.t[j] = x.t[j], x.t[i] }
Let’s define a multi-tier ordering function whose primary sort key is
the Title
, whose secondary key is the Year
, and whose tertiary key
is the running time, Length
. Here’s the call to Sort
using an
anonymous ordering function:
sort.Sort(customSort{tracks, func(x, y *Track) bool { if x.Title != y.Title { return x.Title < y.Title } if x.Year != y.Year { return x.Year < y.Year } if x.Length != y.Length { return x.Length < y.Length } return false }})
And here’s the result. Notice that the tie between the two tracks titled “Go” is broken in favor of the older one.
Title Artist Album Year Length ----- ------ ----- ---- ------ Go Moby Moby 1992 3m37s Go Delilah From the Roots Up 2012 3m38s Go Ahead Alicia Keys As I Am 2007 4m36s Ready 2 Go Martin Solveig Smash 2011 4m24s
Although sorting a sequence of length n requires O(n log n)
comparison operations, testing whether a sequence is already
sorted requires at most n−1 comparisons.
The IsSorted
function from the sort
package checks this for us.
Like sort.Sort
, it abstracts both the sequence and its ordering
function using sort.Interface
, but it never calls the
Swap
method:
This code demonstrates the IntsAreSorted
and Ints
functions and the IntSlice
type:
values := []int{3, 1, 4, 1} fmt.Println(sort.IntsAreSorted(values)) // "false" sort.Ints(values) fmt.Println(values) // "[1 1 3 4]" fmt.Println(sort.IntsAreSorted(values)) // "true" sort.Sort(sort.Reverse(sort.IntSlice(values))) fmt.Println(values) // "[4 3 1 1]" fmt.Println(sort.IntsAreSorted(values)) // "false"
For convenience, the sort
package provides versions of its
functions and types specialized for []int
, []string
, and
[]float64
using their natural orderings.
For other types, such as []int64
or []uint
,
we’re on our own, though the path is short.
Exercise 7.8:
Many GUIs provide a table widget with a stateful multi-tier sort: the
primary sort key is the most recently clicked column head, the
secondary sort key is the second-most recently clicked column head,
and so on. Define an implementation of sort.Interface
for
use by such a table.
Compare that approach with repeated sorting using sort.Stable
.
Exercise 7.9:
Use the html/template
package (§4.6) to
replace printTracks
with a function that displays the tracks as
an HTML table.
Use the solution to the previous exercise to arrange that each click on
a column head makes an HTTP request to sort the table.
Exercise 7.10:
The sort.Interface
type can be adapted to other uses.
Write a function
IsPalindrome(s sort.Interface) bool
that reports whether
the sequence s
is a palindrome, in other words, reversing the
sequence would not change it.
Assume that the elements at indices i
and j
are
equal if !s.Less(i, j) && !s.Less(j, i)
.
18.119.160.154