SortingAlgorithms.jl

Extra sorting algorithms extending Julia's sorting API
Popularity
54 Stars
Updated Last
10 Months Ago
Started In
September 2013

Sorting Algorithms

Build status Coverage Status deps

The SortingAlgorithms package provides three sorting algorithms that can be used with Julia's standard sorting API:

  • HeapSort – an unstable, general purpose, in-place, O(n log n) comparison sort that works by heapifying an array and repeatedly taking the maximal element from the heap.
  • TimSort – a stable, general purpose, hybrid, O(n log n) comparison sort that adapts to different common patterns of partially ordered input data.
  • CombSort – an unstable, general purpose, in-place, O(n log n) comparison sort with O(n^2) pathological cases that can attain good efficiency through SIMD instructions and instruction level parallelism on modern hardware.

Usage

	julia> using SortingAlgorithms

	julia> words = map(chomp,[readlines(open("/usr/share/dict/words"))...])
	235886-element Array{ASCIIString,1}:
	 "A"
	 "a"
	 "aa""zythum"
	 "Zyzomys"
	 "Zyzzogeton"

	julia> sort!(words, alg=TimSort)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "Aani"
	 "Aaron""zymurgy"
	 "zythem"
	 "zythum"

	julia> sort!(words, alg=TimSort, by=length)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "B"
	 "C""scientificophilosophical"
	 "tetraiodophenolphthalein"
	 "thyroparathyroidectomize"

	julia> sort!(words, alg=HeapSort)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "Aani"
	 "Aaron""zymurgy"
	 "zythem"
	 "zythum"

	julia> sort!(words, alg=HeapSort, by=length)
	235886-element Array{ASCIIString,1}:
	 "L"
	 "p"
	 "U""scientificophilosophical"
	 "tetraiodophenolphthalein"
	 "thyroparathyroidectomize"

	julia> sort!(randn(1000), alg=CombSort)
	1000-element Array{Float64,1}:
	 -2.86255
	 -2.72041
	 -2.582343.15075
	  3.20058
	  3.23942

Other packages that provide sorting algorithms

While SortingAlgorithms.jl is the most widely used sorting package in the Julia ecosystem, other packages are available: