Insertion Sort
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:
-
Simple to implement
-
Efficient on (quite) small data sets
-
Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions
-
More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: the average time is n2/4 and it is linear in the best case
-
Stable (does not change the relative order of elements with equal keys)
-
In-place (only requires a constant amount O(1) of extra memory space)
-
It is an online algorithm, in that it can sort a list as it receives it.
Example:
insertionSort(array A)
for i = 1 to length[A]-1 do
begin
value = A[i]
j = i-1
while j >= 0 and A[j] > value do
begin
A[j + 1] = A[j]
j = j-1
end
A[j+1] = value
end
Shell Sort
Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
- insertion sort is efficient if the input is "almost sorted", and
- insertion sort is typically inefficient because it moves values just one position at a time.
Example:
void shell_sort(int A[], int size) {
int i, j, increment, temp;
increment = size / 2;
while (increment > 0) {
for (i = increment; i < size; i++) {
j = i;
temp = A[i];
while ((j >= increment) && (A[j-increment] > temp)) {
A[j] = A[j - increment];
j = j - increment;
}
A[j] = temp;
}
if (increment == 2)
increment = 1;
else
increment = (int) (increment / 2.2);
}
}
Merge Sort
In computer science, merge sort or mergesort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm.
Example:
function mergesort(m)
var list left, right, result
if length(m) ≤ 1
return m
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result
Quick Sort
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.
Example:
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))