Sorting algorithms

Let's we have some collection of elements, for example array of integers.

5, 25, 36, 100, 75, 0, 23, 80, 90, 7

Our task is to sort this array to get the result

0, 5, 7, 23, 25, 36, 75, 80, 90, 100

If you need an algorithm implementation for objects and lists see full source Sort.java.

quick sort

In most cases this algorithm gives the best results.

The basic idea is to select any element within the range [ind1; indn], for example middle element M. Then move all elements that are greater than M to the right side, and all elements that are less than M to the left side.

1. search first element that less (or equal) than M within range [M; indn]
2. search first element that greater (or equal) than M within range [ind1; M]
3. swap found elements
4. continue from the first step until no more elements are found

After that, we repeat the algorithm recursively for two new ranges, the boundaries of which are [ind1; M] and [M; indn]

Time complexity is O(n*log(n)), in worst case O(n²).

public static void quick(int[] src, int indStart, int indEnd) {
    if (src.length == 0 || indStart == indEnd) {
        return;
    }

    --indEnd;
    
    // compute index of middle element
    int m = src[(indEnd + indStart) / 2];
    int i = indStart, j = indEnd;

    do {
        // search element > m from begin
        while (src[i] < m && i < indEnd) i++;

        // search element <= m from end
        while (m < src[j] && j > indStart) j--;

        // if elements on different side
        if (i <= j)
            swapInt(src, i++, j--);
    } while (i <= j);

    if (indStart < j)
        quick(src, indStart, j + 1); // sort left side
    if (i < indEnd)
        quick(src, i, indEnd + 1); // sort right side
}

public static void quick(int[] src) {
    quick(src, 0, src.length);
}

buble sort

This is most simple and lower algorithm. But in essence, quicksort is a modification of this method.

The basic idea is to swap two neighbor elements if they don't match the sorting conditions. Thus most greatest element will be at end (or begin) after first pass.

Time complexity is O(n²).

public static void bubble(int[] src, int indStart, int indEnd) {
    if (src.length == 0 || indStart == indEnd) {
        return;
    }

    int i, j;

    for (i = indStart + 1; i < indEnd; i++) {
        for (j = indStart + 1; j < indEnd; j++)
            if (src[j - 1] > src[j]) {
                swapInt(src, j, j - 1);
            }
        }
    }

public static void bubble(int[] src) {
    bubble(src, 0, src.length);
}

insertion sort

The basic idea here is to insert the next unsorted element into the desired position of an already sorted range.

1. sort the first two elements
2. take the third element and insert it in the right place
3. apply step 2 to the fourth element and so on

Time complexity is O(n²), in best case O(n).

public static void insertion(int[] src, int indStart, int indEnd) {
    if (src.length == 0 || indStart == indEnd) {
        return;
    }

    int t, i, j;
    --indEnd;

    for (i = indStart + 1; i <= indEnd; ++i) {
        t = src[i];
        for (j = i - 1; j >= indStart && t < src[j]; --j)
            src[j + 1] = src[j];
        
        src[j + 1] = t;
    }
}

public static void insertion(int[] src) {
    insertion(src, 0, src.length);
}

Shell sort

The main idea here is to use the insert method on a part of the collection being sorted. For example, on the first pass, process every sixteenth element. On the second pass, every eighth element. And only on the last pass, use the usual insertion sort.

In addition to the sequence shown (..., 16,8,4,2,1), other sequences can be used, for example, N/2, N/4, …, 1 where N length of collection.

public static void shell(int[] src) {
    if (src.length == 0) {
        return;
    }

    int n = src.length;
    int t;

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            t = src[i];
            int j = i;
            while (j >= gap && src[j - gap] > t) {
                src[j] = src[j - gap];
                j -= gap;
            }
            src[j] = t;
        }
    }
}

selection sort

In this algorithm, the main idea is to find the smallest or largest element in each pass and swap it with the first or last unsorted element depending on the sort condition.

other

There are other sorting methods, like pyromidal and merge