Thanks, and that is a pretty solid method of thinking thanks!
Ok got the motherload of questions coming in:
1) Give an implementation of the divide-and-conquer sorting pattern that will realize the selection sort algorithm for an array with base type double.
Have no idea what it is asking of me, the answer they give me:
Code:
public class SelectionSort
{
public static void sort(double[] a,
int begin, int end)
{
if ((end - begin) >= 1)
{
int splitPoint = split(a, begin, end);
sort(a, begin, splitPoint);
sort(a, splitPoint + 1, end);
join(a, begin, splitPoint, end);
}//else sorting one (or fewer) elements
//so do nothing.
}
private static int split(double[] a,
int begin, int end)
{
int index = indexOfSmallest(begin, a, end);
interchange(begin,index, a);
return begin;
}
private static void join(double[] a, int begin,
int splitPoint, int end)
{
//Nothing to do.
}
private static int indexOfSmallest(int startIndex,
double[] a, int endIndex)
{
double min = a[startIndex];
int indexOfMin = startIndex;
int index;
for (index = startIndex + 1;
index < endIndex; index++)
if (a[index] < min)
{
min = a[index];
indexOfMin = index;
//min is smallest of a[startIndex]
//through a[index]
}
return indexOfMin;
}
private static void interchange(int i, int j, double[] a)
{
double temp;
temp = a[i];
a[i] = a[j];
a[j] = temp; //original value of a[i]
}
}
#2
This one basically uses the code from the last one, but seeing as I don't understand the last one I don't understand this one.
Write a class for sorting strings into lexicographic order that follows the outline of the class SelectionSort. Your definition, however, will use an ArrayList of the class ArrayList<string>, rather than an array of elements of type double. For words, lexicographic order reduces to alphabetic order if all the words are in either all lowercase or all uppercase letters. You can compare two strings to see which is lexicographically first by using the String method CompareTo. For strings s1 and s2, s1.compareTo(s2) returns a negative number if s1 is lexicographically before s2, returns 0 if s1 equals s2, and returns a postive number if s1 is lexicographically after s2. Call your class StringSelectionSort. A test program you can test your code with is provided below.
The test class
Code:
import java.util.ArrayList;
public class StringSelectionSortDemo
{
public static void main(String[] args)
{
ArrayList<String> b = new ArrayList<String>( );
b.add("time");
b.add("tide");
b.add("clouds");
b.add("rain");
System.out.println("ArrayList values before sorting:");
int i;
for (String e : b)
System.out.print(e + " ");
System.out.println( );
StringSelectionSort.sort(b);
System.out.println("ArrayList values after sorting:");
for (String e : b)
System.out.print(e + " ");
System.out.println( );
}
}
The correct code
Code:
import java.util.ArrayList;
/**
Class for sorting an ArrayList of Strings lexicographically
(approximately alphabetically).
*/
public class StringSelectionSort
{
/**
Sorts the ArrayList a so that a.get(0), a.get(1), . . .,
a.get(a.size( ) - 1) are in lexicographic order.
*/
public static void sort(ArrayList<String> a)
{
int index, indexOfNextSmallest;
for (index = 0; index < a.size( ) - 1; index++)
{//Place the correct value in position index:
indexOfNextSmallest =
indexOfSmallest(index, a);
interchange(index,indexOfNextSmallest, a);
//a.get(0), a.get(1),...,a.get(index)
//are sorted. The rest of the
//elements are in the remaining positions.
}
}
/**
Precondition: i and j are legal indices for the ArrayList a.
Postcondition: The values of a.get(i) and
a.get(j) have been interchanged.
*/
private static void interchange(
int i, int j, ArrayList<String> a)
{
String temp;
temp = a.get(i);
a.set(i, a.get(j));
a.set(j, temp);
}
/**
Returns the index of the lexicographically first value among
a.get(startIndex), a.get(startIndex+1),...,a.get(a.size( ) - 1)
*/
private static int indexOfSmallest(
int startIndex, ArrayList<String> a)
{
String min = a.get(startIndex);
int indexOfMin = startIndex;
int index;
for (index = startIndex + 1; index < a.size( ); index++)
if ((a.get(index)).compareTo(min) < 0)
{
min = a.get(index);
indexOfMin = index;
}
return indexOfMin;
}
}
How, what is happening in both of these questions?