Elementary Sorts

Selection Sort

O(1/2(n^2)) -> O(n^2). It is in-place sort. We find smallest value and move it to the front. It is not stable algorithm.

class SortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] array) {
        int min
        int temp
        for (int i = 0; i < array.length; i++) {
            min = i
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j
                }
            }
            temp = array[i]
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

Insertion Sort

Complexity is about O(1/4(n^2)) in optimistic case - when the array is partially sorted, this algorithm works perfectly In worst case, it is O(1/2(n^2)) - when the values in reversed order. In general, O(n^2). It is in-place and stable. For sorted list, the complexity is O(n).

class InsertionSortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j -1]) {
                    int temp = array[j]
                    array[j] = array[j - 1]
                    array[j - 1] = temp;
                } else {
                    break
                }
            }
        }
    }
}

Shell Sort

O(n^(3/2). Not stable, can be done in-place.

class ShellSortArray {

    static void main(String[] args) {
        int[] array = [1, 5, 7, 3, 9, 1, -2]
        println array
        sort(array)
        println array
    }

    static void sort(int[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, ...

        while (h >= 1) {  // h-sort the array.
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    int temp = a[j]
                    a[j] = a[j - h];
                    a[j - h] = temp;

                }
            }
            h = h / 3;
        }
    }
}

Example: shuffle cards randomly

First idea: Generate random numbers and assign them to cards. Then sort the array.

Knuth shuffle: iterate through the cards and generate random number that is between 0 and i (i is current index).

Convex Hull

The first approach to calculate a convex hull could be:

1. Find most left point

2. Then find most right point to that point and repeat this until we get to the most left point