README
¶
Sorting Algorithms
Merge Sort
The mere sort algorithm was inspired by this example.
pseudo code
split each element into partitions of size 1
recursively merge adjacent partitions
for i = leftPartIdx to rightPartIdx
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue
else: copy rightPartHeadValue; Increase InvIdx
copy elements back to original array
Documentation
¶
Overview ¶
Package sort provides a collection of sorting algorithms implemented in Go.
The package includes the following functions:
BubbleSort: Implements the bubble sort algorithm to sort a slice of integers. Bubble sort has a runtime complexity of O(n^2) in the worst case and O(n) in the best case.
MergeSort: Implements the merge sort algorithm to sort a slice of integers. Merge sort is a divide-and-conquer algorithm with a runtime complexity of O(n * logn).
Merge: Merges two sorted slices of integers into a single sorted slice. This function ensures that both input slices are sorted before merging them.
MergeSimple: Merges two sorted slices of integers into a single sorted slice. This function demonstrates the simplicity and power of the standard library.
Example usage:
package main
import (
"fmt"
"github.com/eng618/go-eng/algo/sort"
)
func main() {
data := []int{5, 4, 3, 2, 1}
sorted := sort.BubbleSort(data)
fmt.Println(sorted) // Output: [1 2 3 4 5]
data = []int{5, 4, 3, 2, 1}
sorted = sort.MergeSort(data)
fmt.Println(sorted) // Output: [1 2 3 4 5]
left := []int{1, 3, 5}
right := []int{2, 4, 6}
merged := sort.Merge(left, right)
fmt.Println(merged) // Output: [1 2 3 4 5 6]
// Example usage of Standard
leftSimple := []int{1, 3, 5}
rightSimple := []int{2, 4, 6}
standard := sort.Standard(leftSimple, rightSimple)
fmt.Println(standard) // Output: [1 2 3 4 5 6]
}
Package sort is a collection of sorting algorithms.
See https://visualgo.net/en/sorting for a visual example of merge sort.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BubbleSort ¶ added in v0.15.2
BubbleSort takes the provided data (slice of int) and applies the bubble sort algorithm to sort the data. The runtime of bubble sort is at best O(n) and at worst O(n^2).
Example ¶
package main
import (
"fmt"
"github.com/eng618/go-eng/algo/sort"
)
func main() {
input := []int{5, 3, 8, 4, 2}
sorted := sort.BubbleSort(input)
fmt.Println(sorted)
}
Output: [2 3 4 5 8]
func Merge ¶ added in v0.4.2
Merge takes two slices of integers, l and r, and returns a new slice containing all elements from both input slices, sorted in ascending order. The function ensures that both input slices are sorted before merging them. It then iterates through both slices, adding the smaller element from either slice to the result slice until all elements from both input slices have been added.
Parameters:
- l: A slice of integers.
- r: A slice of integers.
Returns:
A new slice of integers containing all elements from l and r, sorted in ascending order.
Example ¶
package main
import (
"fmt"
"github.com/eng618/go-eng/algo/sort"
)
func main() {
left := []int{1, 3, 5}
right := []int{2, 4, 6}
merged := sort.Merge(left, right)
fmt.Println(merged)
}
Output: [1 2 3 4 5 6]
func MergeSort ¶
MergeSort takes the provided data (slice of int) and applies the merge sort algorithm to sort the data. The runtime of merge sort is at best, at worst, and at average always O(n * logn).
Example ¶
package main
import (
"fmt"
"github.com/eng618/go-eng/algo/sort"
)
func main() {
data := []int{5, 4, 3, 2, 1}
sorted := sort.MergeSort(data)
fmt.Println(sorted)
}
Output: [1 2 3 4 5]
func Standard ¶ added in v0.15.2
Standard merges two sorted slices into a single sorted slice. It takes two slices of integers, l and r, and returns a new slice containing all elements from both input slices, sorted in ascending order. This function demonstrates the simplicity and power of the standard library.
Parameters:
- l: A sorted slice of integers.
- r: A sorted slice of integers.
Returns:
A new sorted slice containing all elements from both input slices.
Example ¶
package main
import (
"fmt"
"github.com/eng618/go-eng/algo/sort"
)
func main() {
l := []int{1, 3, 5}
r := []int{2, 4, 6}
result := sort.Standard(l, r)
fmt.Println(result)
}
Output: [1 2 3 4 5 6]
Types ¶
This section is empty.
Source Files