algorithmic 0.0.9

A collection of useful algorithms keeping performance and flexibility on mind.

algorithmic

A collection of useful algorithms keeping performance and flexibility on mind.

Usage

The following import will give you access to all the algorithms in this package.

import 'package:algorithmic/algorithmic.dart';

You can also import these algorithms separately:

Libraries	Imported By
Search algorithms	'package:algorithmic/searching.dart'
Sort algorithms	'package:algorithmic/sorting.dart'
String algorithms	'package:algorithmic/string.dart'

Benchmarks

To run benchmark on your own machine:

$ dart run benchmark

You can check the benchmark.log file for the benchmark results.

Searching algorithms

Index searching algorithms attempt to find the index of an item from a list.

Binary Search

A faster searching algorithm for sorted list of items. It divides the list into two parts and discard one based on the middle value of them. This requires the list to be sorted in an increasing order.

Functions	Performance	Tests	Benchmark	Since
lowerBound()	O(log n)	✔️	✔️	0.0.3
upperBound()	O(log n)	✔️	✔️	0.0.3
binarySearch()	O(log n)	✔️	✔️	0.0.3
binarySearchUpper()	O(log n)	✔️	✔️	0.0.6
binarySearchQuick()	O(log n)	✔️	✔️	0.0.6

Linear Search

A general searching algorithm for any kind of list. It tests every elements on the list one by one.

Functions	Performance	Tests	Benchmark	Since
linearSearch()	O(n)	✔️	✔️	0.0.1
linearSearchBy()	O(n)	✔️	✔️	0.0.4
linearSearchReversed()	O(n)	✔️	✔️	0.0.1
linearSearchReversedBy()	O(n)	✔️	✔️	0.0.4

Sorting algorithms

Sorting algorithms puts a list of items into an increasing order.

Bubble Sort

Bubble sort performs sorting by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order.

Functions	Performance	Tests	Benchmark	Since
bubbleSort()	O(n²)	✔️	✔️	0.0.5

Comb Sort

Comb sort improves bubble sort by eliminating small values near the end of the list, since they slows down bubble sort. It has O(n) time complexity for an already sorted list.

Functions	Performance	Tests	Benchmark	Since
combSort()	O(n²)	✔️	✔️	0.0.8

Cocktail Shaker Sort

Cocktail shaker sort extends bubble sort by operating in two directions. It has O(n) time complexity for an already sorted list.

This algorithm is known by many other names, e.g.: bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, shuttle sort etc.

Functions	Performance	Tests	Benchmark	Since
cocktailShakerSort()	O(n²)	✔️	✔️	0.0.8

Selection Sort

Selection sort algorithm performs sorting by finding the minimum element from the unordered range and putting it at the beginning in each iteration.

Functions	Performance	Tests	Benchmark	Since
selectionSort()	O(n²)	✔️	✔️	0.0.5

Insertion Sort

Insertion sort sorts splits the list into two parts: the left part is ordered and the right part is unordered. In each iteration, it removes the first item from right part, and insert it into the left part maintaining the increasing order.

Functions	Performance	Tests	Benchmark	Since
insertionSort()	O(n²)	✔️	✔️	0.0.5

Gnome Sort

Gnome sort is a variation to the insertion sort which uses a much simpler implementation. It has O(n) time complexity for an already sorted list.

Functions	Performance	Tests	Benchmark	Since
gnomeSort()	O(n²)	✔️	✔️	0.0.5

Quick Sort

Quicksort is an in-place sorting algorithm that works by selecting a pivot element and partitioning the list surrounding it. There are several schemes for selecting the pivot. The sorting performance varies for different schemes.

Functions	Performance	Tests	Benchmark	Since
quickSortLomuto()	O(n log n)	✔️	✔️	0.0.6
quickSortHaore()	O(n log n)	✔️	✔️	0.0.7

Merge Sort

Merge sort is a divide and conquer based algorithm, which can handle very large arrays. Unlike quick sort, it promises O(n log n) performance in worst case and provides stable sort. But it requires equal amount of memory as the length of the array and the implementation runs slower compared than quick sort.

Functions	Performance	Tests	Benchmark	Since
mergeSort()	O(n log n)	✔️	✔️	0.0.8

Counting Sort

Counting sort is a specialized sorting algorithm to sort integers of ranges in linear time. It counts the frequencies of the numbers appearing in an array, and uses it to reconstruct a sorted list.

Functions	Performance	Tests	Benchmark	Since
countingSort()	O(n + k)	✔️	✔️	0.0.9
countingSortOf()	O(n + k)	✔️	✔️	0.0.9
	Here, k is the range of numbers

Radix Sort

Radix sort can sort a range of integers without using any comparisons. It is a special form of bucket sort, which distribute elements into buckets according to their radix.

Functions	Performance	Tests	Benchmark	Since
radixSort()	O(n log_b n)	✔️	✔️	0.0.9
radixSortOf()	O(n log_b n)	✔️	✔️	0.0.9
	Here, b is the radix

String Metrics

Levenshtein Distance

Levenshtein's algorithm returns the minimum number of operations to transform one string (or array) to another. The permitted operations here are insertion, deletion, and substitution.

Functions	Performance	Tests	Benchmark	Since
levenshteinDistance()	O(n m)	✔️	✔️	0.0.9
levenshteinDistanceOf()	O(n m)	✔️	✔️	0.0.9
	Here, n and m are string length

Links

• Benchmark
• Roadmap
• License