Algorithms 101: Sorting
This article will cover several sorting algorithms: working in quadratic time (bubble, insertion and selection sort), in loglinear time (merge sort, quicksort and heap sort) and in linear time, but only for special data types (counting and radix sort). Source code of examples used in this article is available in git repo.
Quadratic time algorithms
There is not much to say about quadratic time algorithms. Usually, they are not used by their own, but with some loglinear algorithm instead. For example, insertion sort sometimes is used inside merge sort or quicksort to sort small subarrays. As for bubble sort, usually it is considerably slower that other quadratic time sort algorithms and not used in practice.
Bubble sort
Idea: repeatedly iterate over an array comparing items pairwise and
exchanging if they are out of order. It is easy to notice that on each
step the biggest item will be placed at the end of an array, thus at
most n
iterations is needed to put all items in their places. This algorithm is
stable.
package com.dancingrobot84.algorithms.sorting;
import com.dancingrobot84.algorithms.util.ArraysExt;
public class BubbleSort {
public static void sort(int[] array) {
boolean isSorted;
do {
isSorted = true;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i+1]) {
ArraysExt.swap(array, i, i+1);
isSorted = false;
}
}
} while (!isSorted);
}
}
Insertion sort
Idea: iterate over an array keeping its left side sorted. When next item is
encountered, push it further to the left until it is less or equal than other
items. There are two loops, each of at most n
iterations, thus quadratic time.
This algorithm is stable.
package com.dancingrobot84.algorithms.sorting;
import com.dancingrobot84.algorithms.util.ArraysExt;
public class InsertionSort {
public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
for (int j = i; j > 0 && array[j] < array[j-1]; j--) {
ArraysExt.swap(array, j, j-1);
}
}
}
}
Selection sort
Idea: iterate over all positions in array. For each position i
search for
minimal item in the range of [i, n]
and put it in position i
. For each
iteration searching for minimal item will take O(n)
time, thus giving
quadratic time overall. This algorithm can be implemented as stable,
however, the implementation below is not stable.
package com.dancingrobot84.algorithms.sorting;
import com.dancingrobot84.algorithms.util.ArraysExt;
public class SelectionSort {
public static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int curMinIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[curMinIndex]) {
curMinIndex = j;
}
}
ArraysExt.swap(array, curMinIndex, i);
}
}
}
Loglinear time algorithms
Loglinear algorithms are the ones that widely used in practice. It is proven
that it is not possible to sort arbitrary data using comparisons faster than
in O(nlog(n))
time, so these algorithms are the fastest ones. However, which
algorithm to use in a program depends on its goals and constraints.
Merge sort
Idea: (top-down merge sort) split array in halves, sort each half
recursively and then merge them. Using master theorem, T(n) = 2T(n/2) + O(n) = O(nlog(n))
. This algorithm is stable.
Bottom-up merge sort treats n
-element array as n
singleton arrays. It merges
them pairwise producing n/2
two-element arrays, merging them again and again
until it merges two n/2
-element arrays into one. It can be implemented without
recursion.
The implementation below use O(n)
space for buffer
array which is used
for merging two subarrays. This is standard recursive top-down merge sort.
package com.dancingrobot84.algorithms.sorting;
import java.util.Arrays;
public class MergeSort {
public static void sort(int[] array) {
new Sorter(array).sort();
}
private static class Sorter {
private final int[] originalArray;
private final int[] buffer;
public Sorter(int[] array) {
originalArray = array;
buffer = new int[array.length];
}
public void sort() {
sort(0, originalArray.length-1);
}
private void sort(int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
sort(start, mid);
sort(mid+1, end);
merge(start, end);
}
private void merge(int start, int end) {
int mid = (start + end) / 2;
int left = start;
int right = mid+1;
int cur = 0;
for (; left <= mid && right <= end; cur++) {
if (originalArray[left] < originalArray[right]) {
buffer[cur] = originalArray[left];
left++;
} else {
buffer[cur] = originalArray[right];
right++;
}
}
for (; left <= mid; cur++, left++) {
buffer[cur] = originalArray[left];
}
for (; right <= end; cur++, right++) {
buffer[cur] = originalArray[right];
}
System.arraycopy(buffer, 0, originalArray, start, cur);
}
}
}
Merge sort is easily parallelizable algorithm. It is more efficient than quicksort on linked lists where it can be implemented using only constant space.
Quicksort
Idea: split array in two parts by comparing each element to the pivot, then
recursively sort these parts. Because quicksort depends on the contents of
array, it is possible to construct such array that will force this algorithm to
work quadratic time. Though this problem is easily solved by choosing random
element, to be precise it is necessary to say that this algorithm has
O(nlog(n))
time complexity in the average case and O(n^2)
time complexity
in the worst case. Space complexity is O(log(n))
in the average case and O(n)
in the worst case since this algorithm is recursive.
Another delicate part of quicksort is how to partition array in constant space.
In order to do that create hiStart
pointer which will store index of the
beginning of the second part of the array. Then iterate over the array comparing
items to pivot: if current item is less than pivot, swap it with the item at
hiStart
and increment hiStart
.
To speed up quicksort in the situation of repeated items one could implement
splitting into three parts: less than, equal to and greater than pivot. It
requires one more pointer, loEnd
which will store index of the end of the
first part.
The implementation below chooses random pivot and uses two-way partition. It is
not stable, however, it is possible to make quicksort stable, but it
requires additional O(n)
space. This implementation use O(1)
space.
package com.dancingrobot84.algorithms.sorting;
import com.dancingrobot84.algorithms.util.ArraysExt;
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static void sort(int[] array) {
sort(array, 0, array.length-1);
}
private static Random generator = new Random();
private static void sort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivotIndex = partition(array, start, end);
sort(array, start, pivotIndex);
sort(array, pivotIndex+1, end);
}
private static int partition(int[] array, int start, int end) {
int pivotIndex = start + generator.nextInt(end - start);
int pivot = array[pivotIndex];
ArraysExt.swap(array, pivotIndex, end);
int hiStart = start;
for (int i = start; i < end; i++) {
if (array[i] < pivot) {
ArraysExt.swap(array, hiStart, i);
hiStart += 1;
}
}
ArraysExt.swap(array, hiStart, end);
return hiStart;
}
}
Quicksort has better constant than merge sort and heap sort. When implemented well it could outperform its competitors drastically. It is possible to parallelize quicksort, but it is a bit harder to do than in case of merge sort.
Heap sort
Idea: build a heap on input array, then iteratively take minimal element out
of it until there is no items left. Since building a heap has O(n)
time
complexity and retrieving minimal element from it requires O(log(n))
time
overall time complexity for this sorting algorithm is O(nlog(n))
. This
algorithm is not stable.
This idea could be used on any data structure which supports building in
O(nlog(n))
or faster and retrieving minimum/maximum in O(log(n))
. Heap
is preferred because it is possible to build heap on the same input array,
thus spending only O(1)
space.
package com.dancingrobot84.algorithms.sorting;
import com.dancingrobot84.algorithms.datastructures.Heap;
import com.dancingrobot84.algorithms.datastructures.impl.BinaryHeap;
import com.dancingrobot84.algorithms.util.ArraysExt;
import java.util.Arrays;
public class HeapSort {
public static void sort(Integer[] array) {
Heap<Integer> heap = BinaryHeap.fromArray(array);
int i = array.length - 1;
while (heap.size() > 0) {
array[i] = heap.pop();
i--;
}
ArraysExt.reverse(array);
}
}
Linear time algorithms
Linear time sorting algorithms do not compare elements or they would work in
O(nlog(n))
. Instead, they either require some constraints on input or use
some knowledge about items of an array. They usually used in complex algorithms
to cut some time here and there, e.g. building suffix arrays or for sorting data
on parallel clusters.
Counting sort
Assumption: all items of input array belong to some finite set of items
or could be uniquely associated with a key from this finite set. Denote the
size of such set as k
.
Idea: iterate over input array counting how many times each distinct item
occurs here, then using this information put items in their places. To store
occurences we need array of integers of length k
and output array of length
n
, thus we need O(n+k)
space. Both of these array are traversed during the
execution of algorithm, so its time complexity is O(n+k)
too.
package com.dancingrobot84.algorithms.sorting;
import java.util.Arrays;
public class CountingSort {
public static final int K = 100;
public static void sort(int[] array) {
int[] counter = new int[K];
for (int item: array) {
counter[item]++;
}
int totalCount = 0;
for (int i = 0; i < K; i++) {
int oldCount = counter[i];
counter[i] = totalCount;
totalCount += oldCount;
}
int[] arrayCopy = Arrays.copyOf(array, array.length);
for (int item: arrayCopy) {
array[counter[item]] = item;
counter[item]++;
}
}
}
Radix sort
Assumption: each item from input array should be represented in positional
notation, i.e. as a collection of characters from finite alphabet of size k
where the power of each character depends on where it is placed within
a collection. Examples of positional notation are binary and decimal numbers
and strings.
Idea: sort input items by a single character in fixed position for all
possible positions, e.g. sort by 1st character, then by 2nd, continue until
all m
positions were used to sort items. Sorting at specified position
could be performed using counting sort since alphabet is finite, therefore
it takes O(m(n+k))
time and O(mn)
space to sort the whole array.
Depending on the starting position radix sort could be LSD (least significant digits first) or MSD (most significant digits first). The first one is used to sort in representation order (correct for decimals), the second one is for sorting in lexicographic order. The implementation below is LSD radix sort.
package com.dancingrobot84.algorithms.sorting;
import java.util.Arrays;
public class RadixSort {
public static final int K = 2;
public static final int M = 32;
public static void sort(int[] array) {
int[] temp = array;
for (int i = 0; i < M; i++) {
temp = sort(temp, i);
}
System.arraycopy(temp, 0, array, 0, array.length);
}
private static int[] sort(int[] array, int bit) {
int[] counter = new int[K];
for (int i = 0; i < array.length; i++) {
counter[getBit(array[i], bit)]++;
}
int totalCount = 0;
for (int i = 0; i < K; i++) {
int oldCount = counter[i];
counter[i] = totalCount;
totalCount += oldCount;
}
int[] result = new int[array.length];
for (int item: array) {
result[counter[getBit(item, bit)]] = item;
counter[getBit(item, bit)]++;
}
return result;
}
private static int getBit(int n, int k) {
return (n >> k) & 1;
}
}
Algorithms comparison chart
Algorithm | Avg. time | Worst time | Avg. space | Stability | Generality |
---|---|---|---|---|---|
Bubble | O(n2) | O(n2) | O(1) | Yes | Yes |
Insertion | O(n2) | O(n2) | O(1) | Yes | Yes |
Selection | O(n2) | O(n2) | O(1) | Yes | Yes |
Merge | O(nlog(n)) | O(nlog(n)) | O(n) | Yes | Yes |
Quick | O(nlog(n)) | O(n2) | O(log(n)) | No | Yes |
Heap | O(nlog(n)) | O(nlog(n)) | O(1) | No | Yes |
Counting | O(n+k) | O(n+k) | O(n+k) | No | No |
Radix | O(m(n+k)) | O(m(n+k)) | O(mn) | Yes | No |
-
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms