Saturday, July 14, 2012

Sorting Alogirthm in Java - Quick , Insertion, Merge, Heap, Selection, and Shell

You can find Java based implementation for Quick , Insertion, Merge, Heap, Selection, and Shell sorting algorithm. All those are properly tested, I assume you have good understand on how each algorithm works that helps you to understand the implementation much better.

HeapSort

public class HeapSort {

    public int[] sort(int[] a) {
        sort(a, a.length-1);
        return a;
    }

    public void sort(int[] a, int end) {
        for (int i = end / 2; i >= 1; i--) {
            fixHeap(a, i, end, a[i]);
        }
        for (int i = end; i > 0; i--) {
            swap(a, 0, i);
            fixHeap(a, 0, i - 1, a[0]);
        }
    }

    private void fixHeap(int[] a, int root, int end,
                         int key) {
        int child = 2 * root; // left child
        if (child < end && a[child] < a[child + 1]) {
            child++;
        }
        if (child <= end && key < a[child]) {
            a[root] = a[child];
            fixHeap(a, child, end, key);
        } else {
            a[root] = key;
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

InsertionSort


public class InsertionSort {

    public int[] sort(int[] input) {
        int size = input.length;
           for (int i = 1; i < size; i++) {
            int j = i;
            int x = input[i];
            while (j > 0 && input[j - 1] > x) {
                input[j] = input[j - 1];
                j--;
            }
            input[j] = x;
        }
        return input;
    }
}

MergeSort 

public class MergeSort {

    public int[] sort(int[] list) {
        mergeSort(list, 0, list.length-1);
        return list;
    }

    public void mergeSort(int list[], int first, int last) {
        if (first >= last) {
            return;
        }
        int middle = (first + last) / 2;
        mergeSort(list, first, middle);
        mergeSort(list, middle + 1, last);

        int size = (last - first) + 1;
        int[] results = new int[size];

        int start2 = middle + 1;
        int indexC = 0;
        int start1 = first;
        while ((start1 <= middle) && (start2 <= last)) {
            if (list[start1] < list[start2]) {
                results[indexC] = list[start1];
                start1++;
            } else {
                results[indexC] = list[start2];
                start2++;
            }
            indexC++;
        }
        if (start1 <= middle) {
            for (int i = start1; i <= middle; i++) {
                results[indexC] = list[i];
                indexC++;
            }
        } else {
            for (int j = start2; j <= last; j++) {
                results[indexC] = list[j];
                indexC++;
            }
        }

        int c = 0;
        for (int index = first; index <= last; index++) {
            list[index] = results[c];
            c++;
        }
    }
}

QuickSort

public class QuickSort {

    public int[] sort(int[] list) {
        quickSort(0, list.length - 1, list);
        return list;
    }

    public void quickSort(int start, int end, int[] list) {
        if (start >= end) return;
        int p = partition(start, end, list);
        quickSort(start, p, list);
        quickSort(p + 1, end, list);
    }

    private int partition(int start, int end, int[] list) {
        // First element
        int pivot = list[start];
        int pivotPoint = start;
        for (int index = start + 1; index <= end; index++) {
            if (list[index] < pivot) {
                pivotPoint = pivotPoint + 1;
                swap(pivotPoint, index, list);
            }
        }
        swap(start, pivotPoint, list);
        return pivotPoint;
    }

    private void swap(int i, int j, int[] list) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

SelectionSort

public class SelectionSort {
    public int[] sort(int[] input) {
        int size = input.length;
        for (int i = 0; i < size; i++) {
            int index = i;
            int currentMin = input[i];
            for (int j = i+1; j < size; j++) {
                int y = input[j];
                if (y < currentMin) {
                    currentMin = y;
                    index = j;
                }
            }
            int x = input[i];
            input[i] = input[index];
            input[index] = x;
        }
        return input;
    }
}

ShellSort 

public class ShellSort {
    public int[] sort(int[] a) {
        double passes = Math.floor(Math.log(a.length));
        while (passes > 1) {
            int increment = (int) (Math.pow(2, passes) - 1);
            for (int start = 0; start < increment; start++) {
                insertSort(start, increment, a);
            }
            passes = passes -1;
        }
        insertSort(0, 1, a);
        return a;
    }

    public void insertSort(int start, int increment, int[] a) {
        int j, k, temp;

        for (int i = start + increment; i < a.length; i += increment) {
            j = i;
            k = j - increment;
            if (a[j] < a[k]) {
                temp = a[j];
                do {
                    a[j] = a[k];
                    j = k;
                    k = j - increment;
                } while (j != start && a[k] > temp);
                a[j] = temp;
            }
        }
    }
}

No comments: