algorithms

package
v1.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 8, 2025 License: MIT Imports: 1 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func BinarySearch

func BinarySearch(arr []int, target int) int

BinarySearch performs binary search on a sorted slice

func BinarySearchRecursive

func BinarySearchRecursive(arr []int, target int) int

BinarySearchRecursive performs recursive binary search on a sorted slice

func BoyerMooreSearch

func BoyerMooreSearch(text, pattern string) []int

BoyerMooreSearch performs Boyer-Moore pattern searching

func BubbleSort

func BubbleSort(arr []int) []int

BubbleSort performs bubble sort on an integer slice

func CountingSort

func CountingSort(arr []int) []int

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

func CountingSortBytes(arr []byte) []byte

CountingSortBytes implements Counting Sort for byte slices This is useful for sorting binary data or custom encodings

func CountingSortString added in v1.1.0

func CountingSortString(str string) string

CountingSortString sorts a string using counting sort algorithm

func CountingSortWithRange added in v1.1.0

func CountingSortWithRange(arr []int, minVal, maxVal int) []int

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

func ExponentialSearch(arr []int, target int) int

ExponentialSearch performs exponential search on a sorted slice

func FibonacciSearch

func FibonacciSearch(arr []int, target int) int

FibonacciSearch performs Fibonacci search on a sorted slice

func HeapSort

func HeapSort(arr []int) []int

HeapSort performs heap sort on an integer slice

func HibbardGaps added in v1.1.0

func HibbardGaps(n int) []int

Hibbard sequence: 2^k - 1

func InsertionSort

func InsertionSort(arr []int) []int

InsertionSort performs insertion sort on an integer slice

func InterpolationSearch

func InterpolationSearch(arr []int, target int) int

InterpolationSearch performs interpolation search on a sorted slice

func JumpSearch

func JumpSearch(arr []int, target int) int

JumpSearch performs jump search on a sorted slice

func KMPSearch

func KMPSearch(text, pattern string) []int

KMPSearch performs Knuth-Morris-Pratt pattern searching

func LevenshteinDistance

func LevenshteinDistance(str1, str2 string) int

LevenshteinDistance calculates the minimum number of single-character edits required to change one string into another

func LinearSearch

func LinearSearch(arr []int, target int) int

LinearSearch performs linear search on a slice

func LongestCommonSubsequence

func LongestCommonSubsequence(text1, text2 string) string

LongestCommonSubsequence finds the longest common subsequence of two strings

func MergeSort

func MergeSort(arr []int) []int

MergeSort performs merge sort on an integer slice

func PrattGaps added in v1.1.0

func PrattGaps(n int) []int

Pratt sequence: 2^i * 3^j

func QuickSort

func QuickSort(arr []int) []int

QuickSort performs quick sort on an integer slice

func RabinKarpSearch

func RabinKarpSearch(text, pattern string) []int

RabinKarpSearch performs Rabin-Karp pattern searching

func RadixSort added in v1.1.0

func RadixSort(arr []int) []int

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

func RadixSortBytes(arr [][]byte) [][]byte

RadixSortBytes implements Radix Sort for byte slices of equal length

func RadixSortString added in v1.1.0

func RadixSortString(arr []string) []string

RadixSortString implements Radix Sort for strings This implementation sorts strings of equal length

func RecursiveCountNQueensSolutions added in v1.1.0

func RecursiveCountNQueensSolutions(n int) int

RecursiveCountNQueensSolutions returns the number of solutions for the N-Queens problem

func RecursiveFactorial added in v1.1.0

func RecursiveFactorial(n int) int

RecursiveFactorial calculates n! recursively

func RecursiveGetNQueensBoard added in v1.1.0

func RecursiveGetNQueensBoard(solution []int) []string

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

func RecursiveIsValidNQueensSolution(solution []int) bool

RecursiveIsValidNQueensSolution verifies if a given solution is valid

func RecursiveNQueens added in v1.1.0

func RecursiveNQueens(n int) [][]int

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

func RecursiveReverseString(s string) string

RecursiveReverseString reverses a string using recursion

func SedgewickGaps added in v1.1.0

func SedgewickGaps(n int) []int

Sedgewick sequence: 4^k + 3 * 2^(k-1) + 1

func ShellSort added in v1.1.0

func ShellSort(arr []int) []int

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

func ShellSortWithGaps(arr []int, gaps []int) []int

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

func SortingSort(arr []int) []int

SortingSort performs counting sort on an integer slice

Types

This section is empty.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL