Answer to Question #247814 in Algorithms for kofi

Question

1. Write a java program that allows a user to choose the searching or sorting algorithm and request the list of items to search or sort.

2. Compute the running time of the algorithms

3. Determine the time complexity of your algorithm the searching and sorting algorithms.

4. Display the search value or the sorted list to the user.

5. 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)$