A fast string sorting algorithm (MSD radix sort)

Overview

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

You might also like...
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

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

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

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

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

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

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.

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.

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

golang sorting algorithm and data construction.

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

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

Implementation of Boyer-Moore fast string search algorithm in Go

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

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

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

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

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

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

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

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!

    opened by adamdecaf 1
Releases(1.1.0)
Owner
Algorithms to Go
Code should be correct, clear and efficient. Prefer simple. Avoid clever.
Algorithms to Go
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

Patrick-Ranjit D. Madsen 40 Oct 24, 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-

Charles Banning 533 Nov 22, 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

Avelino 32 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

Damian Gryski 64 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

Alexander Neumann 39 Sep 14, 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

Maxim 84 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

Alexandru Cojocaru 71 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

Keith Rarick 285 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

Microcosm 2.5k Nov 21, 2022
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

Moovweb 218 Sep 9, 2022