Programming and Computer Science in Java:
Quiz #6a:   Sorting and sortDemos Pearls
David Kosbie, 2002-2003

Quiz Date:  Tue, Apr 1, 2003

Part 1:  Written Portion

• For this quiz portion, you may not use JCreator.
• No notes, no books, no calculators, no talking, etc
• The provided times sum to 60 minutes, but are only rough guides.
• Good luck!

Question 1: (2 minutes)  Write a Java method named "swap" which swaps two elements in an array of integers.

Question 2: (3 minutes)  Write the sequence of swaps (using the element values, and not the indices) when the following array is sorted using insertionsort:
5    3    8    2    1    4

Question 3:  (3 minutes) Write the sequence of swaps (using the element values, and not the indices) when the following array is sorted using bubblesort:
5    3    8    2    1    4

Question 4: (1 minute)  What is the first swap (and just the first swap) (using the element values, and not the indices) when the following array is sorted using quicksort:
5    3    8    2    1    4

Question 5:  (4 minutes) Write a Java method "insertionsort" which sorts an array of integers using insertionsort.

Question 6:  (2 minutes) Very briefly, why is "selectionsort" named "selectionsort"?

Question 7:  (5 minutes) Write a Java method "bubblesort" which sorts an array of integers using bubblesort.

Question 8:  (1 minute) Unless they are broken (as happens!), computers do precisely what they are told, no more and no less, even if these instructions are themselves erroneous (that is, buggy).  In one word, we call this _______________.

Question 9:  (2 minutes) What does the following Java code print out?
int x1 = 1, x2 = 2, x3 = 3;
x1 = ((x2 > x1) ? 4 : 5);
x2 = ((x2 > x1) ? 6 : 7);
System.out.println(x1 + "," + x2 + "," + x3);

Question 10:  (2 minutes)  Write a code snippet which prints out the number of milliseconds required to execute a single call to sortArray.  You can assume that an array "a" has already been initialized to some random size with random elements.

Question 11:  (5 minutes) Write a Java method, intToString, which takes an integer as its only argument, and returns a String which is the string representation of that integer.

Question 12:  (5 minutes) Write a Java method, printArray, which prints the elements of an array -- 10 elements per line.  You may assume that printInteger is already written for you, and that method prints an integer right-justified in a 6-character-wide field.

Question 13: (5 minutes)  Write a Java method, monthName, with the following signature:
public static String monthName(int i)
This method returns the 3-letter name of the ith month.  So if (i == 0), this method returns "jan", and if (i == 11) it returns "dec".  You are guaranteed that i will be in [0,11].  Note that to solve this, you must initialize an array of strings to the month names, the same way we initialized an array of strings in sortDemos.java to the names of the various sorts.

Question 14: (5 minutes)  Write a Java method, monthIndex, with the following signature:
public static int monthIndex(String name)
This method is basically the opposite of the preceding method.  So if (name == "jan"), this method returns 0, and if (name == "dec") it returns 11.  You are guaranteed that the name will be valid.  Note that to solve this, you must call the monthName method from the previous problem (that is, do not use an array of month names in this problem).

Question 15:  (7.5 minutes) Prove that insertionsort is O(n2).

Question 16:  (7.5 minutes) Prove that mergesort is O(nlogn).

Part 2:  JCreator Portion

• For this quiz portion, you may use JCreator.
• No notes, no books, no calculators, no talking, etc
• Good luck!
• You may begin this portion with the code in sortDemos.java, except with mergesort and quicksort removed.  This version is provided for you here:  sortDemosQuiz.htm

Question 17:  Write mergesort.

Question 18:  Write quicksort.