Anonymous user
Order by pair comparisons: Difference between revisions
added go
(→{{header|C++}}: added c) |
(added go) |
||
Line 302:
Is indigo > blue? (y/n) y
{ "red" "orange" "yellow" "green" "blue" "indigo" "violet" }
</pre>
=={{header|Go}}==
===Go: Binary search insertion sort===
<lang go>package main
import (
"fmt"
"sort"
"strings"
)
var count int = 0
func interactiveCompare(s1, s2 string) bool {
count++
fmt.Printf("(%d) Is %s < %s? ", count, s1, s2)
var response string
_, err := fmt.Scanln(&response)
return err == nil && strings.HasPrefix(response, "y")
}
func main() {
items := []string{"violet", "red", "green", "indigo", "blue", "yellow", "orange"}
var sortedItems []string
// Use a binary insertion sort to order the items. It should ask for
// close to the minimum number of questions reqired
for _, item := range items {
fmt.Printf("Inserting '%s' into %s\n", item, sortedItems)
// lower_bound performs the binary search using InteractiveCompare to
// rank the items
spotToInsert := sort.Search(len(sortedItems), func(i int) bool {
return interactiveCompare(item, sortedItems[i])
})
sortedItems = append(sortedItems[:spotToInsert],
append([]string{item}, sortedItems[spotToInsert:]...)...)
}
fmt.Println(sortedItems)
}</lang>
{{out}}
<pre>
Inserting 'violet' into []
Inserting 'red' into [violet]
(1) Is red < violet? y
Inserting 'green' into [red violet]
(2) Is green < violet? y
(3) Is green < red? n
Inserting 'indigo' into [red green violet]
(4) Is indigo < green? n
(5) Is indigo < violet? y
Inserting 'blue' into [red green indigo violet]
(6) Is blue < indigo? y
(7) Is blue < green? n
Inserting 'yellow' into [red green blue indigo violet]
(8) Is yellow < blue? y
(9) Is yellow < green? y
(10) Is yellow < red? n
Inserting 'orange' into [red yellow green blue indigo violet]
(11) Is orange < blue? y
(12) Is orange < yellow? y
(13) Is orange < red? n
[red orange yellow green blue indigo violet]
</pre>
===Go: Standard sort with custom comparator===
<lang go>package main
import (
"fmt"
"sort"
"strings"
)
var count int = 0
type sortable []string
func (s sortable) Len() int { return len(s) }
func (s sortable) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sortable) Less(i, j int) bool {
s1, s2 := s[i], s[j]
count++
fmt.Printf("(%d) Is %s < %s? ", count, s1, s2)
var response string
_, err := fmt.Scanln(&response)
return err == nil && strings.HasPrefix(response, "y")
}
func main() {
items := sortable{"violet", "red", "green", "indigo", "blue", "yellow", "orange"}
sort.Sort(items)
fmt.Println(items)
}</lang>
{{out}}
<pre>
(1) Is orange < violet? y
(2) Is red < orange? y
(3) Is green < orange? n
(4) Is indigo < green? n
(5) Is blue < indigo? y
(6) Is blue < green? n
(7) Is yellow < indigo? y
(8) Is yellow < blue? y
(9) Is yellow < green? y
(10) Is yellow < orange? n
(11) Is violet < indigo? n
[red orange yellow green blue indigo violet]
</pre>
| |||