# Sorting Algorithms

We all know that Quicksort is one of the fastest algorithms for sorting. It's not often, however, that we get a chance to see exactly how fast Quicksort really is. The following applets chart the progress of several common sorting algorthms while sorting an array of data. (This is inspired by the algorithm animation work at Brown University and the video Sorting out Sorting from the University of Toronto (circa 1970!).)

This page shows the main sorting algorithms. Variations of these algorithms are shown here. A version with smaller applets is here.

 Bubble Sort (implemented by James Gosling and Jason Harrison) BubbleSort goes through the array repeatedly, exchanging adjacent elements that are in the wrong order. At the end of each such pass, the largest remaining element has been moved to its correct location. Selection Sort (implemented by Jason Harrison) SelectionSort divides the array into a sorted portion on the left and an unsorted portion on the right. It extends the sorted portion by selecting the smallest remaining element from the unsorted portion and placing it at the end of the sorted portion of the array. Insertion Sort (implemented by Jason Harrison) InsertionSort divides the array into a sorted portion on the left and an unsorted portion on the right. It extends the sorted portion by inserting the first unsorted element into the sorted portion, shuffling elements to the right as required to make room for the new element. Double Storage Merge Sort (implemented by Jack Snoeyink) MergeSort divides the array in half, sorts each half recursively, and then merges the two sorted halves together. It uses an extra array, equal in size to the original, to make merging efficient. In the animation, you'll see the magenta marker make two passes through the sorted halves. The first time, nothing appears to happen. This is when the two halves are being merged into the extra array. The second time through the data is copied from the extra array back to the original. Bottom-up Merge Sort (implemented by Byron Weber Becker) Bottom-up merge sort begins by merging each pair of 1-element subarrays to make sorted 2-element subarrays. Adjacent pairs of 2-element subarrays are merged to make 4-element subarrays. Merging adjacent arrays continues until the entire array is sorted. The algorithm requires a work array, doubling the required storage. It is not recursive. Shell Sort (implemented by Jason Harrison) Shellsort is a simple extension of InsertionSort which gains speed by allowing exchanges of elements that are far apart. The idea is to rearrange the array to give it the property that every hth element (starting anywhere) yields a sorted array. Such an array is said to be h-sorted. h decreases as the sort runs until, in the last pass, h is 1 and the algorithm is the same as InsertionSort. Heap Sort (implemented by Jason Harrison) HeapSort is similar to SelectionSort in that it always selects the largest (or smallest) element from the unsorted part of the array to move to the sorted part of the array. However, HeapSort first organizes the unsorted part of the array into a heap so that it can select the largest element quickly. After the largest element is removed, the heap must be reorganized. Naive Quick Sort (implemented by James Gosling and Byron Weber Becker) Quicksort begins by chooses a pivot. It then puts all the elements that are less than the pivot on the left end of the array, all the elements greater than the pivot on the right end of the array, and the pivot between them. The pivot is now in its final position and all the elements to its left (right) will stay to its left (right). Now recursively sort on the left side and the right side. This version chooses the last element as a pivot -- a very poor choice if the data is ordered or nearly ordered. Quick Sort (implemented by James Gosling) This is like the Naive QuickSort except that it chooses the middle element as the pivot.

If you're going to make a copy of this demo, you'll need to also copy the the SortAlgorithm class and the SortItem class.