Sorting Algorithm

This post was migrated from Tistory. You can find the original here.

A collection of sorting algorithms

---

Insertion Sort

Pseudocode

pseudo code

Implementation

public class InsertionSort {
    static void insertionSort(int[] input) {
        int count = 0; // track the number of iterations
        for (int j = 1; j < input.length; j++) {
            count++;
            int key = input[j];
            int i = j - 1;
            while (i > -1 && input[i] > key) {
                count++;
                input[i + 1] = input[i];
                i -= 1;
            }
            input[i + 1] = key;
        }
        System.out.println(count);
    }

    public static void main(String[] args) {
    	// test with 30 elements
        
        // worst case (descending order array)
        int[] worstCase = {
                30, 29, 28, 27, 26, 25, 24, 23, 22, 21,
                20, 19, 18, 17, 16, 15, 14, 13, 12, 11,
                10, 9, 8, 7, 6, 5, 4, 3, 2, 1
        };
        insertionSort(worstCase); //464

        // best case (already sorted array)
        int[] bestCase = {
                1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                21, 22, 23, 24, 25, 26, 27, 28, 29, 30
        };
        insertionSort(bestCase); //29

        // average case (randomly ordered array)
        int[] averageCase = {
                12, 5, 29, 7, 18, 23, 2, 25, 14, 8,
                1, 27, 19, 3, 10, 30, 6, 22, 17, 4,
                16, 24, 9, 11, 28, 15, 21, 26, 13, 20
        };
        insertionSort(averageCase); //218
    }
}

visual illustration

Time Complexity

• Best case : O(n)
• Worst case : O(n^2)
• Average case : O(n^2)

Characteristics

• in-place sort: uses almost no extra memory
• stable sort: preserves the relative order of equal elements
• efficient for small lists or lists that are mostly sorted already

---

More to come