Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Go}}: added another version
(→{{header|Go}}: added another version) |
|||
Line 1,694:
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted! [23 26 31 41 53 58 59 84 93 97]
</pre>
More traditional version of quicksort. It work generically with any container that conforms to <code>sort.Interface</code>.
<lang go>package main
import (
"fmt"
"sort"
)
func partition(a sort.Interface, first int, last int) int {
pivotIndex := first // pick first element
left := first+1
right := last
for left <= right {
for a.Less(left, pivotIndex) {
left++
}
for a.Less(pivotIndex, right) {
right--
}
if left <= right {
a.Swap(left, right)
left++
right--
}
}
a.Swap(pivotIndex, right) // put pivot into right place
return right
}
func quicksortHelper(a sort.Interface, first int, last int) {
if first >= last {
return
}
pivotIndex := partition(a, first, last)
quicksortHelper(a, first, pivotIndex-1)
quicksortHelper(a, pivotIndex+1, last)
}
func quicksort(a sort.Interface) {
quicksortHelper(a, 0, a.Len()-1)
}
func main() {
a := []int{1, 3, 5, 7, 9, 8, 6, 4, 2}
fmt.Printf("Unsorted: %v\n", a)
quicksort(sort.IntSlice(a))
fmt.Printf("Sorted: %v\n", a)
b := []string{"Emil", "Peg", "Helen", "Juergen", "David", "Rick", "Barb", "Mike", "Tom"}
fmt.Printf("Unsorted: %v\n", b)
quicksort(sort.StringSlice(b))
fmt.Printf("Sorted: %v\n", b)
}</lang>
{{out}}
<pre>
Unsorted: [1 3 5 7 9 8 6 4 2]
Sorted: [1 2 3 4 5 6 7 8 9]
Unsorted: [Emil Peg Helen Juergen David Rick Barb Mike Tom]
Sorted: [Barb David Emil Helen Juergen Mike Peg Rick Tom]
</pre>
| |||