Concept:
Insertion sort
Headline
The Insertion sort sorting algorithm
Citation
(http://en.wikipedia.org/wiki/Insertion_sort, 21 April 2013)
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Illustration
See the visualization of Insertion sort on Wikipedia:
http://en.wikipedia.org/wiki/Insertion_sort
See various illustrations of Insertion sort as available on YouTube, e.g.:
Iterative insertion sort in Java
Given a list of length n, in the already sorted prefix 0..i-1, elements are moved to the right to make space for the next element x from the as yet unsorted postfix i..n-1 to be inserted in the right position.
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int x = a[i];
int j = i;
while (j > 0 && a[j - 1] > x) {
a[j] = a[j - 1];
a[j - 1] = x;
j--;
}
}
}
Recursive insertion sort in Haskell
-- Polymorphic sorting
sort :: Ord a => [a] -> [a]
sort xs = inserts xs []
-- Insert given elements in an emerging result
inserts :: Ord a => [a] -> [a] -> [a]
inserts [] r = r
inserts (x:xs) r = inserts xs (insert x r)
-- Insert a given element in a list
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) =
if x <= y
then x : y : ys
else y : insert x ys
The main sorting function relies on two helpers to model sorting as repeated insertion. That is, the inserts helper successfully inserts all elements into an emerging result list; the insert help perform a single insert operation such that the given element is inserted into a readily sorted list in a way such that the result is sorted, too. The first equation of insert models that any value can be trivially inserted into an empty list. The second equation of insert compares the given value x with the head y of the sorted list. If x<=y then x belongs before y; otherwise y is maintained as the head and insertion continues into the tail of the list by means of recursion.
The implementation is exercised as follows:
main = do
let input = [2,4,3,1,4]
print $ sort input -- [1,2,3,4,4]
There are no revisions for this page.
User contributions
User edits
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.
Syntax for editing wiki
For you are available next options:will make text bold.
will make text italic.
will make text underlined.
will make text striked.
will allow you to paste code headline into the page.
will allow you to link into the page.
will allow you to paste code with syntax highlight into the page. You will need to define used programming language.
will allow you to paste image into the page.
is list with bullets.
is list with numbers.
will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.
will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.
will allow your to insert code snippets from @worker.