README
¶
Algorithms Package
This package provides implementations of various fundamental algorithms in Go, including sorting, searching, and string processing algorithms.
Features
Sorting Algorithms
- QuickSort: Divide-and-conquer sorting with pivot selection
- MergeSort: Divide-and-conquer sorting with merging
- HeapSort: Binary heap based sorting
- InsertionSort: Simple sorting by building sorted array
- BubbleSort: Simple comparison-based sorting
- CountingSort: Integer sorting using counting
- RadixSort: Non-comparative integer sorting
- ShellSort: Improved insertion sort with gap sequence
Searching Algorithms
- Linear Search: Simple sequential search
- Binary Search (Iterative and Recursive):
- Efficient search in sorted arrays
- Returns leftmost occurrence
- Jump Search: Block-based search for sorted arrays
- Interpolation Search: Improved binary search with interpolation
- Exponential Search: Search in unbounded arrays
- Fibonacci Search: Divide-and-conquer with Fibonacci numbers
String Algorithms
- Knuth-Morris-Pratt (KMP): Pattern matching with prefix function
- Rabin-Karp: Pattern matching with rolling hash
- Boyer-Moore: Pattern matching with bad character rule
- Longest Common Subsequence (LCS)
- Levenshtein Distance (Edit Distance)
Usage Examples
Sorting Examples
// QuickSort
arr := []int{64, 34, 25, 12, 22, 11, 90}
sorted := QuickSort(arr)
// MergeSort
sorted = MergeSort(arr)
// HeapSort
sorted = HeapSort(arr)
// InsertionSort
sorted = InsertionSort(arr)
// ShellSort
sorted = ShellSort(arr)
Searching Examples
arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
// Binary Search
index := BinarySearch(arr, 5) // Returns index of 5
// Jump Search
index = JumpSearch(arr, 7) // Returns index of 7
// Interpolation Search
index = InterpolationSearch(arr, 3) // Returns index of 3
// Exponential Search
index = ExponentialSearch(arr, 8) // Returns index of 8
String Algorithm Examples
// KMP Pattern Search
text := "AABAACAADAABAAABAA"
pattern := "AABA"
matches := KMPSearch(text, pattern) // Returns all occurrences
// Rabin-Karp Search
matches = RabinKarpSearch(text, pattern)
// Boyer-Moore Search
matches = BoyerMooreSearch(text, pattern)
// Longest Common Subsequence
lcs := LongestCommonSubsequence("ABCDGH", "AEDFHR")
// Levenshtein Distance
distance := LevenshteinDistance("kitten", "sitting")
Implementation Details
Time Complexities
Sorting Algorithms
- QuickSort: O(n log n) average, O(n²) worst case
- MergeSort: O(n log n)
- HeapSort: O(n log n)
- InsertionSort: O(n²)
- BubbleSort: O(n²)
- CountingSort: O(n + k) where k is the range
- RadixSort: O(d * (n + k)) where d is number of digits
- ShellSort: O(n log n) to O(n²) depending on gap sequence
Searching Algorithms
- Linear Search: O(n)
- Binary Search: O(log n)
- Jump Search: O(√n)
- Interpolation Search: O(log log n) average, O(n) worst case
- Exponential Search: O(log n)
- Fibonacci Search: O(log n)
String Algorithms
- KMP Search: O(n + m) where n is text length, m is pattern length
- Rabin-Karp: O(n + m) average, O(nm) worst case
- Boyer-Moore: O(n/m) best case, O(nm) worst case
- LCS: O(mn) where m, n are string lengths
- Levenshtein Distance: O(mn)
Space Complexities
- QuickSort: O(log n)
- MergeSort: O(n)
- HeapSort: O(1)
- String Pattern Matching: O(m)
- LCS and Edit Distance: O(mn)
Testing
Each algorithm comes with comprehensive test coverage. Run tests using:
go test ./...
Contributing
Contributions are welcome! Please ensure that any new features or modifications come with:
- Proper documentation
- Comprehensive test cases
- Example usage
- Time and space complexity analysis
License
This package is distributed under the MIT license. See the LICENSE file for more details.
Documentation
¶
Index ¶
- func BinarySearch(arr []int, target int) int
- func BinarySearchRecursive(arr []int, target int) int
- func BoyerMooreSearch(text, pattern string) []int
- func BubbleSort(arr []int) []int
- func CountingSort(arr []int) []int
- func CountingSortBytes(arr []byte) []byte
- func CountingSortString(str string) string
- func CountingSortWithRange(arr []int, minVal, maxVal int) []int
- func ExponentialSearch(arr []int, target int) int
- func FibonacciSearch(arr []int, target int) int
- func HeapSort(arr []int) []int
- func HibbardGaps(n int) []int
- func InsertionSort(arr []int) []int
- func InterpolationSearch(arr []int, target int) int
- func JumpSearch(arr []int, target int) int
- func KMPSearch(text, pattern string) []int
- func LevenshteinDistance(str1, str2 string) int
- func LinearSearch(arr []int, target int) int
- func LongestCommonSubsequence(text1, text2 string) string
- func MergeSort(arr []int) []int
- func PrattGaps(n int) []int
- func QuickSort(arr []int) []int
- func RabinKarpSearch(text, pattern string) []int
- func RadixSort(arr []int) []int
- func RadixSortBytes(arr [][]byte) [][]byte
- func RadixSortString(arr []string) []string
- func RecursiveCountNQueensSolutions(n int) int
- func RecursiveFactorial(n int) int
- func RecursiveGetNQueensBoard(solution []int) []string
- func RecursiveIsValidNQueensSolution(solution []int) bool
- func RecursiveNQueens(n int) [][]int
- func RecursiveReverseString(s string) string
- func SedgewickGaps(n int) []int
- func ShellSort(arr []int) []int
- func ShellSortWithGaps(arr []int, gaps []int) []int
- func SortingSort(arr []int) []int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
BinarySearch performs binary search on a sorted slice
func BinarySearchRecursive ¶
BinarySearchRecursive performs recursive binary search on a sorted slice
func BoyerMooreSearch ¶
BoyerMooreSearch performs Boyer-Moore pattern searching
func BubbleSort ¶
BubbleSort performs bubble sort on an integer slice
func CountingSort ¶
CountingSort implements the Counting Sort algorithm for non-negative integers Time Complexity: O(n + k) where n is the number of elements and k is the range of input Space Complexity: O(k)
func CountingSortBytes ¶ added in v1.1.0
CountingSortBytes implements Counting Sort for byte slices This is useful for sorting binary data or custom encodings
func CountingSortString ¶ added in v1.1.0
CountingSortString sorts a string using counting sort algorithm
func CountingSortWithRange ¶ added in v1.1.0
CountingSortWithRange implements Counting Sort for a known range of integers This version is more efficient when the range is known and smaller than the array size
func ExponentialSearch ¶
ExponentialSearch performs exponential search on a sorted slice
func FibonacciSearch ¶
FibonacciSearch performs Fibonacci search on a sorted slice
func InsertionSort ¶
InsertionSort performs insertion sort on an integer slice
func InterpolationSearch ¶
InterpolationSearch performs interpolation search on a sorted slice
func JumpSearch ¶
JumpSearch performs jump search on a sorted slice
func LevenshteinDistance ¶
LevenshteinDistance calculates the minimum number of single-character edits required to change one string into another
func LinearSearch ¶
LinearSearch performs linear search on a slice
func LongestCommonSubsequence ¶
LongestCommonSubsequence finds the longest common subsequence of two strings
func RabinKarpSearch ¶
RabinKarpSearch performs Rabin-Karp pattern searching
func RadixSort ¶ added in v1.1.0
RadixSort implements the Radix Sort algorithm for non-negative integers Time Complexity: O(d * (n + k)) where d is the number of digits, n is the number of elements and k is the range of values for each digit (10 for decimal)
func RadixSortBytes ¶ added in v1.1.0
RadixSortBytes implements Radix Sort for byte slices of equal length
func RadixSortString ¶ added in v1.1.0
RadixSortString implements Radix Sort for strings This implementation sorts strings of equal length
func RecursiveCountNQueensSolutions ¶ added in v1.1.0
RecursiveCountNQueensSolutions returns the number of solutions for the N-Queens problem
func RecursiveFactorial ¶ added in v1.1.0
RecursiveFactorial calculates n! recursively
func RecursiveGetNQueensBoard ¶ added in v1.1.0
RecursiveGetNQueensBoard converts a solution to a 2D board representation Returns a slice of strings where 'Q' represents a queen and '.' represents an empty cell
func RecursiveIsValidNQueensSolution ¶ added in v1.1.0
RecursiveIsValidNQueensSolution verifies if a given solution is valid
func RecursiveNQueens ¶ added in v1.1.0
RecursiveNQueens solves the N-Queens problem and returns all solutions Each solution is represented as a slice of integers where the index represents the row and the value represents the column where a queen is placed
func RecursiveReverseString ¶ added in v1.1.0
RecursiveReverseString reverses a string using recursion
func SedgewickGaps ¶ added in v1.1.0
Sedgewick sequence: 4^k + 3 * 2^(k-1) + 1
func ShellSort ¶ added in v1.1.0
ShellSort implements the Shell Sort algorithm Shell sort is an optimization of insertion sort that allows the exchange of items that are far apart
func ShellSortWithGaps ¶ added in v1.1.0
ShellSortWithGaps implements Shell Sort with custom gap sequence This version allows you to specify the gap sequence to use
func SortingSort ¶ added in v1.1.0
SortingSort performs counting sort on an integer slice
Types ¶
This section is empty.
Source Files