In this lab, you will write a method that implements insertion sort. Below is the pseudocode for the program. Your insertion sort will sort an array of Strings lexicographically, meaning a – z.
for i = 1 to length(A)
j = i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j = j – 1 end while
I have provided a template for you to use. Finish the implementation for insertionSort and printArray. PrintArray should print out the contents of the array in the format shown below. In the driver, call the appropriate methods to match the output in the driver.
How do we compare strings to sort them correctly? Use the method compareTo provided in the string class. This method is used as follows:
If str1 comes before str2, compareTo will return a negative number. If str1 comes after str2, compareTo will return a positive number.
If str1 and str2 are the same, compareTo will return 0.
Tom, Steve, Ann, Zoe, Bob, Moana, Naomi, Kevin, Ryan, Nina, Dora, Wanda, Eric
Ann, Bob, Dora, Eric, Kevin, Moana, Naomi, Nina, Ryan, Steve, Tom, Wanda, Zoe