Very simple and very inefficient algorithm
n
^{2}1
(constant, only for the min element)for j = 0 ... n-2
// find the best element in a[j .. n-1]
best = j;
for i = j + 1 ... n -1
if a[i] < a[best]
best = i;
if best is not j
swap a[j], a[best]
n
, worst and average case: n
^{2}1
, Stable: Yes, Method: Exchangingwhile swapIsDone
swapIsDone = false
for i = 0 ... n - 1
if a[i-1] > a[i]
swap a[i] a[i-i]
swapIsDone = true
n
, worst and average case: n
^{2}1
, Stable: Yes, Method: Insertionfor i = 1 ... n - 1
valueToInsert = a[i]
holePos = i
while holePos > 0 and valueToInsert < A[holePos - 1]
a[holePos] = A[holePos - 1] // shift the larger value up
holePos = holePos - 1 // move the hole position down
A[holePos] = valueToInsert
n*log(n)
, worst: n
^{2}log(n)
stack spacefunction quicksort('array')
if len('array') <= 1:
return
select and remove a pivot value from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array':
if 'x' <= 'pivot':
append 'x' to 'less'
else:
append 'x' to greater
return concatenate (quicksort('less'), 'pivot', quicksort('greater'))
n
sublists, each containing 1
element (list of 1 element is sorted)n*log(n)
n
O(log(n)
) using the Three Hungarian’s Algorithmfunction merge_sort(list m)
// if list size is 0 (empty) or 1, consider it sorted
// (using less than or equal prevents infinite recursion
// for a zero length m)
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
n*log(n)
O(1)
map
n + r
n + r
r
is the range of numbers to be sortedn + r
n + k
k
= the number of bucketsn2 * k
n * k
Name | Best | Avg | Worst | Memory | Stable |
---|---|---|---|---|---|
Bubble | n | n^{2} | n^{2} | 1 | Yes |
Insertion | n | n^{2} | n^{2} | 1 | Yes |
Quick | n*log(n) | n*log(n) | n^{2} | log(n) | Depends |
Merge | n*log(n) | n*log(n) | n*log(n) | n | Yes |
Heap | n*log(n) | n*log(n) | n*log(n) | n | No |
Bogo | n | n*n! | n*n! | 1 | No |
O(n)
for each item in the list:
if that item has the desired value,
stop the search and return the location.
return nothing.
O(log(n))
function binarySearch(int items[], int key, int from, int to)
if (to < from):
// set is empty, so return value showing not found
return KEY_NOT_FOUND;
// calculate midpoint to cut set in half
int middle = midpoint(from, to);
if (a[middle] > key):
// key is in lower subset
return binarySearch(a, key, from, middle - 1);
else if (a[middle] < key):
// key is in upper subset
return binarySearch(a, key, middle + 1, to);
else:
// key has been found
return middle;
int binarySearch(int a[], int key, int from, int to)
// continue searching while [imin,imax] is not empty
while (from <= to):
//calculate the midpoint for roughly equal partition x/
int middle = midpoint(from, to);
// determine which subarray to search
if (a[middle] < key)
// change from index to search upper subarray
from = middle + 1;
else if (a[middle] > key)
// change to index to search lower subarray
to = middle - 1
else
// key found at index middle
return middle;
return KEY_NOT_FOUND;
log(log(n))
, Worst case: O(n)
public int interpolationSearch(int[] sortedArray, int toFind){
// Returns index of toFind in sortedArray, or -1 if not found
int low = 0;
int high = sortedArray.length - 1;
int mid;
while(sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
mid = low + ((toFind - sortedArray[low]) x (high - low)) /
(sortedArray[high] - sortedArray[low]);
// out of range is possible here
if (sortedArray[mid] < toFind)
low = mid + 1;
else if (sortedArray[mid] > toFind)
high = mid - 1;
else
return mid;
}
if (sortedArray[low] == toFind) return low;
else return -1; // Not found
}
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source)
{
var array = source.ToArray();
var n = array.Length;
for (var i = 0; i < n; i++)
{
// Exchange a[i] with random element in a[i..n-1]
int r = i + RandomProvider.Instance.Next(0, n - i);
var temp = array[i];
array[i] = array[r];
array[r] = temp;
}
return array;
}
public static class RandomProvider
{
private static Random Instance = new Random();
}