Question

1. Which sorting algorithm can be improved with the following simple optimization? During each pass, you keep track of whether a swap was made. At the end of a pass, if no swaps were made, you can assume the list is sorted.

a. Insertion sort

b. Selection sort

c. Bubble Sort

d. None of the above

2. If you want to use Java's built-in Collections.sort() method to sort an ArrayList, what do you have to ensure about the type of object stored in your ArrayList?

a. That it is a primitive

b. That the object class implements Comparable

c. That all the objects in the ArrayList are of the EXACT same class (ie not sub-class objects)

d. That the object class contains a String or int field so that it can be used for sorting

3. Insertion Sort and Selection Sort have what order of worst-case complexity?

a. O(1)

b. O(n)

c. O(n²)

d. O(log n)

Answer 1

1. Which sorting algorithm can be improved with the following simple optimization? During each pass, you keep track of whether a swap was made. At the end of a pass, if no swaps were made, you can assume the list is sorted.

The correct answer is option c, Bubble sort.

To optimize bubble sort, we can introduce a flag to check if elements are getting swapped inside the inner for loop. Hence, in the inner for loop, we check whether swapping of elements is taking place or not, for each time. If for a particular iteration, if there is no swapping, it means the array has been sorted and we can jump out of the for loop, instead of performing all the iterations.

2. If you want to use Java's built-in Collections.sort() method to sort an ArrayList, what do you have to ensure about the type of object stored in your ArrayList?

The correct answer is option b, The object class implements comparable.

For the objects to have a natural order they must implement the interface java.lang.Comparable. The Comparable interface has a method called compareTo(), which gives a negative, 0, a positive if the current value is less than, equal to, or greater than the value we are comparing with, respectively.

3. Insertion Sort and Selection Sort have what order of worst-case complexity?

The correct answer is option c, O(n2).

Worst case happens in insertion sort if the array to be sorted is a reverse-sorted array. For selection sort, best, average and worst case time complexity is O(n2) which is independent of distribution of data.