Handout 31

Sorting II*

---

Shell Sort

The idea of Shellsort is the following:

1. arrange the data sequence in a two-dimensional array
2. sort the columns of the array

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

Shell sort requires asymptotically fewer than O(n²) comparisons and exchanges in the worst case. Although it is easy to develop an intuitive sense of how this algorithm works, it is very difficult to analyze its execution time, but estimates range from O(nlog₂ n) to O(n^1.5) depending on implementation details.
Another Shell Sort Example

Binary Tree Sort

A binary search tree (BST) is a binary tree which has the following properties:

• Each node has a value.
• A total order is defined on these values.
• The left subtree of a node contains only values less than the node's value.
• The right subtree of a node contains only values greater than or equal to the node's value.
• The major advantage of binary search trees is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

A binary search tree can be used to implement a simple but inefficient sorting algorithm. Similar to insertion sort, we insert all the values we wish to sort into a new ordered data structure, in this case a binary search tree, then traverse it in order, building our result.
The worst-case time of build_binary_tree is O(n²) � if you feed it a sorted list of values, it chains them into a linked list with no left subtrees. For example, build_binary_tree([1, 2, 3, 4, 5]) yields the tree (None, 1, (None, 2, (None, 3, (None, 4, (None, 5, None))))).

Merge Sort

Conceptually, merge sort works as follows:

• Divide the unsorted list into two sublists of about half the size
• Sort each of the two sublists
• Merge the two sorted sublists back into one sorted list.

Mergesort is a O(nlog(n)) sorting algorithm. It is easy to implement merge sort such that it is stable, meaning it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm.

Heapsort

A heap is a specialized tree-based data structure that satisfies the heap property. Its base datatype (used for node keys) must be an ordered set.

If B is a child node of A, then the heap property is that:

key(A) >= key(B)

This implies that the greatest element is always in the root node, and such a heap is sometimes called a max heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min heap.) This is why heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

Example of a complete binary max heap

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.

Heapsort example

QuickSort

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

The steps are:

• Pick an element, called a pivot, from the list.
• Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
• Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

Quicksort on average, makes O(n log n) comparisons to sort n items. However, in the worst case, it makes O(n²) comparisons. Typically, quicksort is significantly faster in practice than other O(n log n) 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 possibility of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

A Comparison of Sorts