Answer to Question #247815 in Algorithms for desmond

Question

1. Be innovative and design a user-friendly application

Note: the programming should take the list to search or sort at the running time, not compile time. [You are submitting the java code and the computed running time/time complexity of the algorithms

Answer 1

Insertion sort:

public static void sort(String[] a) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j-1].compareTo(a[j]) > 0)
                exch(a, j, j-1);
            else break;
        }
    }
}

running time:

• Best case. When the input array is already in sorted order, the total number of compares in ~ n and the running time is linear.
• Worst case. When the input is reverse sorted, the number of compares is ~ 1/2 n² and the running time is quadratic.
• Average case. When the input is randomly ordered, the expected number of compares is ~ 1/4 n² and the running time is quadratic.
  

time complexities: $O(n^2)$ and $O(n)$