Question

Linda creates an algorithm that takes an input sequence S and produces an output sequence T that is a sorting of the n elements of S.
a) In Java, give an algorithm, isSorted, for testing in O(n) time if T is sorted.
b) Explain why the algorithm isSorted is not sufficient to prove a particular output T of Linda's algorithm is a sorting of S.
c) Describe what additional information Linda's algorithm could output so that her algorithm's correctness could be established on any given S and T in O(n) time.

Answer 1

a) The following Java code is a simple test to check whether a string array sort function works as expected:

@Test
public void testSort() {
String[] arr = {"c", "a", "b", "c", "d"};
String[] expected = {"a", "b", "c", "c", "d"};
sort(arr); // this is the name of Linda's sorting function
assertArrayEquals(expected, arr);
}

b) The problem with the above function, testSort, is that it does not test whether Linda's sort() function is a stable sorting algorithm or not. A stable sort algorithm is one that retains the order of objects with the same keys. That is, objects with the same key appear in the same order in the output collection as in the input collection. We do not care about this much in simple integer arrays, but this is especially important for map-like data structures.

c) If Linda's algorithm is capable of stable sorting elements, it should be able to output a collection with mapped values where the order of the objects with same values in the output list is the same as that in the input list. If we know that this is possible, we can test this using a simple assertion that compares the two collections (input and output) in O(n) time, where n is the size of the input collection.

All the best!