A Primer on Elementary Sorting Algorithms

Introduction to Elementary Sorts

Sorting is a fundamental problem in computer science that involves rearranging a collection of items into a specific order. This primer covers three elementary sorting algorithms—Selection Sort, Insertion Sort, and Shellsort—as well as a method for shuffling.

These algorithms are “elementary” because they are relatively simple to understand and implement, but they are generally not efficient enough for large-scale datasets compared to more advanced algorithms like Mergesort or Quicksort.

The Comparable Interface

To make our sorting algorithms general, we rely on Java’s Comparable interface. Any data type that implements compareTo() can be sorted. This method defines a “total order” for the objects, allowing the sort algorithm to determine if one object is less than, equal to, or greater than another.

1. Selection Sort

Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

How It Works

1. Iterate from i = 0 to N-1.
2. In each iteration, find the index min of the smallest remaining element in the unsorted part of the array (a[i] to a[N-1]).
3. Swap the element at a[i] with the element at a[min].

Performance

• Compares: ~ ½ N²
• Exchanges: N
• Time Complexity: O(N²)
• Key Feature: The number of exchanges is linear (N), which means data movement is minimal. However, the running time is quadratic and insensitive to the input; it’s just as slow for a sorted array as it is for a random one.

2. Insertion Sort

Insertion sort builds the final sorted array one item at a time. It is much more efficient than selection sort for partially sorted arrays.

How It Works

1. Iterate from i = 1 to N-1.
2. For each element a[i], compare it with the elements to its left.
3. Shift all larger elements to the right to make space and insert a[i] into its correct sorted position.

Performance

• Compares (Average): ~ ¼ N²
• Exchanges (Average): ~ ¼ N²
• Time Complexity: O(N²) in the average and worst cases.
• Best Case: O(N) for an already sorted array (N-1 compares, 0 exchanges).
• Key Feature: For partially sorted arrays (where the number of inversions is low), insertion sort runs in linear time. This makes it a practical choice for small or nearly-sorted arrays.

3. Shellsort

Shellsort is an improvement over insertion sort that allows the exchange of items that are far apart. It works by h-sorting the array for a decreasing sequence of h values.

How It Works

1. Choose an increment sequence (e.g., the 3x+1 sequence: 1, 4, 13, 40, …).
2. Start with the largest increment h less than N/3.
3. h-sort the array: Use insertion sort, but instead of comparing an element with its adjacent one, compare it with the one h positions behind it.
4. Decrease h by dividing by 3 and repeat until h is 1. The final pass (1-sort) is just a regular insertion sort, but at this point, the array is already highly sorted, making it very fast.

Performance

• Time Complexity: The exact complexity is unknown and depends on the increment sequence. For the 3x+1 sequence, the worst-case number of compares is O(N^(3/2)).
• Key Feature: Shellsort is a simple idea that leads to a substantial performance gain over insertion and selection sort. It’s a good choice for medium-sized arrays and has a tiny code footprint.

4. Shuffling

The goal of shuffling is to rearrange an array into a uniformly random permutation.

Knuth (Fisher-Yates) Shuffle

This is the standard algorithm for producing an unbiased shuffle.

How It Works

1. Iterate from i = 0 to N-1.
2. In each iteration, pick an integer r uniformly at random between 0 and i (inclusive).
3. Swap the element at a[i] with the element at a[r].

Performance

• Time Complexity: O(N)
• Key Feature: It guarantees a uniformly random permutation in linear time, assuming a good source of random numbers.