A fast string sorting algorithm (MSD radix sort)

Your basic radix sort GoDoc

A fast string sorting algorithm

This is an optimized sorting algorithm equivalent to sort.Strings in the Go standard library. For string sorting, a carefully implemented radix sort can be considerably faster than Quicksort, sometimes more than twice as fast.

MSD radix sort

Radix sort

A discussion of MSD radix sort, its implementation and a comparison with other well-known sorting algorithms can be found in Implementing radixsort. In summary, MSD radix sort uses O(n) extra space and runs in O(n+B) worst-case time, where n is the number of strings to be sorted and B is the number of bytes that must be inspected to sort the strings.

Installation

Once you have installed Go, run the go get command to install the radix package:

go get github.com/yourbasic/radix

Documentation

There is an online reference for the package at godoc.org/github.com/yourbasic/radix.

Roadmap

Stefan Nilsson – korthaj

Owner
Algorithms to Go
Code should be correct, clear and efficient. Prefer simple. Avoid clever.
Algorithms to Go
Similar Resources

Small and fast FTS (full text search)

Microfts A small full text indexing and search tool focusing on speed and space. Initial tests seem to indicate that the database takes about twice as

Jul 30, 2022

Geziyor, a fast web crawling & scraping framework for Go. Supports JS rendering.

Geziyor Geziyor is a blazing fast web crawling and web scraping framework. It can be used to crawl websites and extract structured data from them. Gez

Dec 29, 2022

Fast and secure steganography CLI for hiding text/files in images.

Fast and secure steganography CLI for hiding text/files in images.

indie CLI This complete README is hidden in the target.png file below without the original readme.png this could have also been a lie as none could ev

Mar 20, 2022

A fast, easy-of-use and dependency free custom mapping from .csv data into Golang structs

csvparser This package provides a fast and easy-of-use custom mapping from .csv data into Golang structs. Index Pre-requisites Installation Examples C

Nov 14, 2022

Smartsort - A smart sorting algorithm for Go to sort filename containing digits that is not zero padded

smartsort A smart sorting algorithm for Go to sort filename containing digits th

Mar 26, 2022

A radix sorting library for Go (golang)

zermelo A radix sorting library for Go. Trade memory for speed! import "github.com/shawnsmithdev/zermelo" func foo(large []uint64) zermelo.Sort(l

Jul 30, 2022

radix: a go radix tree with nearest matching

radix implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Feb 6, 2022

Provides the radix package that implements a radix tree.

go-radix Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Oct 26, 2021

Eunomia is a distributed application framework that support Gossip protocol, QuorumNWR algorithm, PBFT algorithm, PoW algorithm, and ZAB protocol and so on.

Introduction Eunomia is a distributed application framework that facilitates developers to quickly develop distributed applications and supports distr

Sep 28, 2021

golang sorting algorithm and data construction.

data-structures-questions 算法和程序结构是我们学习编程的基础,但是很多的时候,我们很多都是只是在应用,而没有深入的去研究这些,所以自己也在不断的思考和探索,然后分析,学习,总结自己学习的过程,希望可以和大家一起学习和交流下算法! 目录 网络协议 数据结构 算法 数据库 Go

Dec 17, 2022

The simplest sorting algorithm that sorts in quadratic time

The simplest sorting algorithm that sorts in quadratic time

Simplest sort Showcases the simplest sorting algorithm that works in quadratic time. From here. The pseudocode for this algo can be seen below (sorts

Oct 14, 2022

Is this the simplest (and most surprising) sorting algorithm ever?

Is this the simplest sorting algorithm

May 15, 2022

Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

Oct 7, 2022

Pure is a fast radix-tree based HTTP router

Pure is a fast radix-tree based HTTP router

package pure Pure is a fast radix-tree based HTTP router that sticks to the native implementations of Go's "net/http" package; in essence, keeping the

Dec 1, 2022

Golang metrics for calculating string similarity and other string utility functions

strutil strutil provides string metrics for calculating string similarity as well as other string utility functions. Full documentation can be found a

Jan 3, 2023

Recursively searches a map[string]interface{} structure for another map[string]interface{} structure

msirecurse Recursively searches a map[string]interface{} structure for existence of a map[string]interface{} structure Motivation I wrote this package

Mar 3, 2022

Inflection is a string transformation library. It transforms strings from CamelCase to underscored string.

Inflection Inflection is a string transformation library. It transforms strings from CamelCase to underscored string. This is an implement of Inflecti

Jul 25, 2022

Multi-String Pattern Matching Algorithm Using TrieHashNode

Multi-String Pattern Matching algorithm. This implementation is inspired from Aho-Corasick algorithm Getting Started modelA = mspm.NewModel("mspm_mode

Dec 9, 2022

String-matching in Golang using the Knuth–Morris–Pratt algorithm (KMP)

gokmp String-matching in Golang using the Knuth–Morris–Pratt algorithm (KMP). Disclaimer This library was written as part of my Master's Thesis and sh

Dec 8, 2022
Comments
  • mention worst/average case, and space usage?

    mention worst/average case, and space usage?

    Cool library. Having a drop-in for sort.Strings is fantastic. (Say hi to /r/golang!)

    The best case for any algorithm is, well, best, but what about the average and worst case? Those can dramatically impact the long tail (e.g. regarding timings or throughput). Could the README mention those?

    For string sorting, a carefully implemented radix sort can be considerably faster than Quicksort, sometimes more than twice as fast.

    Mentioning the space used is helpful to know, also. An O(n) algorithm on operations is useless if it takes O(n!) space!

String-matching in Golang using the Knuth–Morris–Pratt algorithm (KMP)

gokmp String-matching in Golang using the Knuth–Morris–Pratt algorithm (KMP). Disclaimer This library was written as part of my Master's Thesis and sh

Dec 8, 2022
Decode / encode XML to/from map[string]interface{} (or JSON); extract values with dot-notation paths and wildcards. Replaces x2j and j2x packages.

mxj - to/from maps, XML and JSON Decode/encode XML to/from map[string]interface{} (or JSON) values, and extract/modify values from maps by key or key-

Dec 29, 2022
A Go slugify application that handles string

slugify A Go slugify application that handles string Example: package main import ( "fmt" "github.com/avelino/slugify" ) func main() { text := "E

Sep 27, 2022
A collection of well-known string hash functions, implemented in Go

This library is a collection of "well-known" 32-bit string hashes, implemented in Go. It includes: Java string hash ELF-32 Jenkins' One-A

Mar 3, 2022
String i18n utilities for the Go Programming Language

About polyglot polyglot is a String translation package and tool for Go. Setup Make sure you have a working Go installation. See Getting Started Now r

Dec 22, 2022
Package strit introduces a new type of string iterator, along with a number of iterator constructors, wrappers and combinators.

strit Package strit (STRing ITerator) assists in development of string processing pipelines by providing a simple iteration model that allows for easy

Jun 21, 2022
User agent string parser in golang

User agent parsing useragent is a library written in golang to parse user agent strings. Usage First install the library with: go get xojoc.pw/userage

Aug 2, 2021
Go implementation of the bspatch algorithm

binarydist Package binarydist implements binary diff and patch as described on http://www.daemonology.net/bsdiff/. It reads and writes files compatibl

Nov 20, 2022
bluemonday: a fast golang HTML sanitizer (inspired by the OWASP Java HTML Sanitizer) to scrub user generated content of XSS

bluemonday bluemonday is a HTML sanitizer implemented in Go. It is fast and highly configurable. bluemonday takes untrusted user generated content as

Jan 4, 2023
Super Fast Regex in Go

Rubex : Super Fast Regexp for Go by Zhigang Chen ([email protected] or [email protected]) ONLY USE go1 BRANCH A simple regular expression libr

Sep 9, 2022