Insertion Sorting in Java

Time Complexity :
Average and Worst case is O(n^2)
Best case is O(n)


/**
 * A simple class to demonstrate the Insertion sorting algorithm
 */
public class InsertionSorting {

    public static void main(String[] args) {

        int[] intArray = {11, 2, 13, 4, 5, 7};
        InsertionSorting sorting = new InsertionSorting();
        sorting.printElements("Before Sorting", intArray);
        sorting.doSorting(intArray);
        sorting.printElements("After Sorting", intArray);
    }

    public void printElements(String message, int[] intArray) {
        System.out.println(message);
        for (Integer num : intArray) {
            System.out.println(num);
        }
    }

    /**
     * Sorting the numbers based on the insertion sort algorithm
     *
     * This algorithm takes the number/value compares it with all the previous numbers
     * Best case time complexity is O(n) and worst and avg case is O(n^2)
     *
     * @param intArray
     */
    public static void doSorting(int[] intArray) {

        int sortValue;
        int i, j;
        for (i = 1; i  0 && intArray[j-1] > sortValue; j--) { //Compare with all previous elements.
                intArray[j] = intArray[j - 1];                     // If the value is greater than, move down the elements
            }
            intArray[j] = sortValue;
        }
    }
}

Advertisements

Bubble Sorting in Java

Time Complexity :
Average and Worst case is O(n^2)
Best case is O(n)


/**
 * A simple class to demonstrate the bubble sorting
 */
public class BubbleSorting {

    public static void main(String[] args) {

        int[] intArray = {11, 2, 13, 4, 5, 7};
        BubbleSorting bubbleSorting = new BubbleSorting();
        bubbleSorting.printElements("Before Sorting", intArray);
        bubbleSorting.doSorting(intArray);
        bubbleSorting.printElements("After Sorting", intArray);
    }

    public void printElements(String message, int[] intArray) {
        System.out.println(message);
        for (Integer num : intArray) {
            System.out.println(num);
        }
    }

    /**
     * Sort the elements with Bubble sort algorithm
     * 
     * Large element will be bubbled to its proper position after each pass
     * Worst and Avg case complexity is O(n^2)
     * Best case is O(n)
     *
     * @param intArray
     */
    public static void doSorting(int[] intArray) {

        boolean isSwaped;
        int tmp;
        for (int i = 0; i < intArray.length - 1; i++) {
            isSwaped = false;
            for (int j = 1; j  intArray[j]) {
                    tmp = intArray[j];
                    intArray[j] = intArray[j - 1];
                    intArray[j - 1] = tmp;
                    isSwaped = true;
                }
            }
            if (!isSwaped) {
                System.out.println("No Elements are sorted in this pass.Hence its sorted already.Hence break the loop");
                break;
            }
        }
    }
}

Selection Sorting in Java

Time Complexity :
Best, Average and Worst case is O(n^2)

/**
 * A simple class to demonstrate the selection sorting algorithm
 */
public class SelectionSorting {

    public static void main(String[] args) {

        int[] intArray = {11, 2, 13, 4, 5, 7};
        SelectionSorting selectionSorting = new SelectionSorting();
        selectionSorting.printElements("Before Sorting", intArray);
        selectionSorting.doSorting(intArray);
        selectionSorting.printElements("After Sorting", intArray);
    }

    public void printElements(String message, int[] intArray) {
        System.out.println(message);
        for (Integer num : intArray) {
            System.out.println(num);
        }
    }

    /**
     * Sort the elements with Selection sort algorithm
     *
     * For each pass, the smallest element is selected and moved to the proper position[Ascending]
     * Worst, Best and Avg case complexity is O(n^2)
     *
     * @param intArray
     */
    public static void doSorting(int[] intArray) {

        int i, j;
        int minIndex;
        int temp;
        for (i = 0; i < intArray.length - 1; i++) {
            minIndex = i; //Min index is set as i
            for (j = i+1; j  intArray[j]) { // Compare the minIndex element with all the element                      // and change the minIndex
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                temp = intArray[minIndex];
                intArray[minIndex] = intArray[i];
                intArray[i] = temp;
            }
        }
    }
}