Answer to Question #247816 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.

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