The Bubble Sort 2464

Charles Richmond

Insertion sort takes the next unsorted item and searches the sorted item list to find where to insert it in order.

Selection sort searches the unsorted item list to find the smallest item, then adds it to the end of the sorted item list.

Either sort can be done in place, moving the block of items between the insertion point (insertion sort) or end of the currently sorted items (selection sort) and the next unsorted item (insertion sort) or the selected item (selection sort) down one item to create space for the inserted-selected item.

Obviously you can also do them using separate memory areas for the unsorted and sorted items, at a cost of the extra space, but saving some time.

You can also do insertion sort from an input stream, but not selection sort, as you can't know the smallest item remaining if you haven't input it yet.

For external sorting, you can, however use either method from an input stream for the preliminary sorts before a merge. You read as many items as you can into memory, sort them and write out the sorted list, then repeat until done, and start the merge.

A variant of this is replacement selection sort, where you fill the input area, write out the smallest unmarked item and replace it with a new input item. If the new item is smaller than than the last output item, it won't fit into the current sorted list, so you mark it. Repeat until all items in the input area are marked, when you terminate the current output list, clear all marks and start the next output list with the smallest item currently in the input. This give initial sorted strings on average twice as long as straight replacement, typically saves one phase of merge.

--brian

-- "What's life? Life's easy. A quirk of matter. Nature's way of keeping meat fresh."