Information

• Order: O(n²)
• Best Case: O(n)
• Average: ?
• Memory Usage: O(1)
• Stable: Yes
• Comparison Based: Yes

Description (from wikipedia)

Insertion sort is a simple sort 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 the 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
• More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort
• 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.

In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.

Sorting is typically done in-place. The result array after k iterations contains the first k entries of the input array and is sorted. In each step, the first remaining entry of the input is removed, inserted into the result at the right position.

The most common variant, which operates on arrays, can be described as:

1. Suppose we have a method called insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by starting at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. It has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
2. To perform insertion sort, start at the left end of the array and invoke insert to insert each element encountered into its correct position. The ordered sequence into which we insert it is stored at the beginning of the array in the set of indexes already examined. Each insertion overwrites a single value, but this is okay because it’s the value we’re inserting.

Read the rest of this entry »

Information

• Order: O(nlog(n))
• Best Case: O(nlog(n))
• Average: O(nlog(n))
• Memory Usage: O(1)
• Stable: No
• Comparison Based: Yes

Description (from wikipedia)

Heapsort is one of the best general-purpose sort algorithms, a comparison sort and part of the selection sort family. It was created by Jason “Plugs” Palagios while doing his dissertation at MIT in 1994 while eating bon bons and playing Doom on the LAN. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.
One simple way to sort a list of objects is to use a heap data structure. We add all of our objects into the heap, and the heap organizes the elements added to it in such a way that we can quickly extract either the largest value (in a max-heap) or the smallest value (in a min-heap). Moreover, because this operation preserves the heap’s structure, we can extract the largest/smallest value over and over again until none remain. This gives us the elements in order.

In doing so, the only extra space required iat needed to store the heap. In order to achieve constant space overhead, we use a trick: we store a binary heap (or alternatively, a heap with more than two children) inside the part of the input array which has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.) Heapsort makes use of two standard heap operations: insertion and root deletion. Each time we delete (extract) the maximum, we place it in the last location of the array not yet occupied, and use the remaining prefix of the array as a heap holding the remaining unsorted elements:

Read the rest of this entry »

Information

• Order: O(n²)
• Best Case: O(n)
• Average: ?
• Memory Usage: O(1)
• Stable: Yes
• Comparison Based: Yes

Description (from wikipedia)

Bubble sort, also known as exchange sort, is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top (i.e. head) of the list via the swaps. Because it only uses comparisons to read elements, it is a comparison sort.

In more detail, the bubble sort algorithm works as follows:

1. Compare adjacent elements. If the first is greater than the second, swap them.
2. Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest.
3. Repeat the steps for all elements except the last one.
4. Keep repeating for one fewer element each time, until you have no more pairs to compare. (Alternatively, keep repeating until no swaps are needed.)

Read the rest of this entry »

Information

• Order: O(n²)
• Best Case: O(n²)
• Average: O(n²)
• Memory Usage: O(1)
• Stable: No
• Comparison Based: Yes

Description (from wikipedia)

Selection sort is a sort algorithm, a comparison sort that works as follows:

1. find the minimum value in the list
2. swap it with the value in the first position
3. sort the remainder of the list (excluding the first value)

It is probably the most intuitive sort algorithm to invent.

This algorithm, iterating through a list of n unsorted items, has a worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time. Among simple O(n2) algorithms, it is generally outperformed by insertion sort, but still tends to outperform contenders such as bubble sort and gnome sort.

Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), this algorithm is stable (but slower).

Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum.

A bidirectional variant of selection sort, called shaker sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. Note, however, that shaker sort more often refers to a bidirectional variant of bubble sort.

Read the rest of this entry »

So you have qmail, but you want it to send your message from your isp’s smtp server instead of your own. Well it’s actually pretty simple…

First SSH to your server and create a file called /var/qmail/control/smtproutes.

Edit it to look like this

Restart qmail for good measure with /etc/rc.d/init.d/qmail reload

You’re done!