Algorithm | Rainmore

Quick Sort

public void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

private void sort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;

    int partition = partition(arr, lo, hi);

    sort(arr, lo, partition - 1);
    sort(arr, partition + 1, hi);
}

private int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;

    for (int j= lo; j <= hi - 1; j++) {
        if (arr[j] <= pivot) {
            i++;

            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[hi];
    arr[hi] = temp;

    return i + 1;
}

Merge Sort

public void sort(int[] arr) {
        sort(arr, new int[arr.length], 0, arr.length);
    }

    private void sort(int[] arr, int[] holder, int lo, int hi) {
        int d = hi - lo;
        if (d <= 1) return;

        int mid = lo + d/2;

        sort(arr, holder, lo, mid);
        sort(arr, holder, mid, hi);

        merge(arr, holder, lo, mid, hi);
    }

    private void merge(int[] arr, int[] holder, int lo, int mid, int hi) {
        int i = lo;
        int j = mid;

        for (int k = lo; k < hi; k++) {
            if (i == mid)               holder[k] = arr[j++];
            else if (j == hi)           holder[k] = arr[i++];
            else if (arr[j] < arr[i])   holder[k] = arr[j++];
            else                        holder[k] = arr[i++];
        }

        for (int k = lo; k < hi; k++) arr[k] = holder[k];
    }

Insert Sort

static void insertSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }

    insertSort(arr, n - 1);


    int j = n - 2;
    int tail = arr[j + 1];

    while (j >= 0 && arr[j] > tail) {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = tail;
}

Bubble Sort

No one uses it any more

static void bubbleSort(int[] arr, int n) {
    if (n == 1) {
        return;
    }

    IntStream.range(0, n - 1).forEach(i -> {
        int j = i + 1;
        if (arr[i] > arr[j]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    });

    bubbleSort(arr, n - 1);
}

Codility MissingInteger, Java 8

import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

private static void getResult(int[] a) {
    Set set = IntStream.of(a).boxed().collect(Collectors.toSet());

    int result = 1;
    while(set.contains(result)) {
        result++;
    }

    return result;
}

Reference: https://stackoverflow.com/questions/26532081/codility-missinginteger-java