2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
|
Select a Chapter:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
| Chapter Thirteen listings: 4 classes | ||
public class CompOp // collecting various sorting algorithms
{
// SELECTION SORT
/** Precondition: size <= item.length; item[0]...item[size-1]
* are non-null values all Comparable to each other.
* Postcondition: The array contains the values it initially
* had but with item[0]...item[size-1] in ascending order. */
public static void selectionSort (Comparable[] item, int size)
{ for (int k = 0; k < size - 1; k++)
swapMinToFront (item, k, size - 1);
} //=======================
private static void swapMinToFront (Comparable[] item,
int start, int end)
{ int indexSmallest = start;
for (int k = start + 1; k <= end; k++)
{ if (item[k].compareTo (item[indexSmallest]) < 0)
indexSmallest = k;
}
Comparable saved = item[start];
item[start] = item[indexSmallest];
item[indexSmallest] = saved;
} //=======================
/** Return the smallest value in item[start]...item[end]. */
public static Comparable findMinimum (Comparable[ ] item,
int start, int end)
{ Comparable smallestSoFar = item[start];
for (int k = start + 1; k <= end; k++)
{ if (item[k].compareTo (smallestSoFar) < 0)
smallestSoFar = item[k];
}
return smallestSoFar;
} //=======================
/** Return the median of 3000 random double values. */
public static double median() // independent
{ final int numToSort = 3000;
Double[] item = new Double [numToSort];
for (int k = 0; k < numToSort; k++)
item[k] = new Double (Math.random());
selectionSort (item, numToSort);
return item[numToSort / 2].doubleValue();
} //=======================
// INSERTION SORT
/** Precondition: size <= item.length; item[0]...item[size-1]
* are non-null values all Comparable to each other.
* Postcondition: The array contains the values it initially
* had but with item[0]...item[size-1] in ascending order. */
public static void insertionSort (Comparable[] item, int size)
{ for (int k = 1; k < size; k++)
insertInOrder (item, k);
} //=======================
private static void insertInOrder (Comparable[] item, int m)
{ Comparable save = item[m];
for (; m > 0 && item[m - 1].compareTo (save) > 0; m--)
item[m] = item[m - 1];
item[m] = save;
} //=======================
// BINARY SEARCH
/** Precondition: item[0]...item[size-1] are all non-null,
* in ascending order, and Comparable with target.
* Returns: whether target is one of the array values. */
public static boolean binarySearch (Comparable[] item,
int size, Comparable target)
{ if (size <= 0) //1
return false; //2
int lowerBound = 0; //3
int upperBound = size - 1; //4
while (lowerBound < upperBound) //5
{ int midPoint = (lowerBound + upperBound) / 2; //6
if (item[midPoint].compareTo (target) < 0) //7
lowerBound = midPoint + 1; //8
else //9
upperBound = midPoint; //10
} //11
return item[lowerBound].equals (target); //12
} //=======================
// 3 RECURSIVE METHODS
public static void insertionSort (Comparable[] item, int size)
{ if (size > 1)
{ insertionSort (item, size - 1); //recur
insertInOrder (item, size - 1);
}
} //=======================
public static void selectionSort (Comparable[] item, int size)
{ if (size > 1)
{ swapMaxToRear (item, 0, size - 1);
selectionSort (item, size - 1); //recur
}
} //=======================
public static void printBinary (String prefix, int numDigits)
{ if (numDigits <= 1)
System.out.println (prefix + "0\n" + prefix + "1");
else
{ printBinary (prefix + "0", numDigits - 1); //recur
printBinary (prefix + "1", numDigits - 1); //recur
}
} //=======================
// QUICKSORT AND MERGESORT: MAIN METHODS
/** Precondition: size <= item.length; item[0]...item[size-1]
* are non-null values all Comparable to each other.
* Postcondition: The array contains the values it initially
* had but with item[0]...item[size-1] in ascending order. */
public static void quickSort (Comparable[] item, int size)
{ new QuickSorter (item).sort (0, size - 1);
} //=======================
/** Precondition: size <= item.length; item[0]...item[size-1]
* are non-null values all Comparable to each other.
* Postcondition: The array contains the values it initially
* had but with item[0]...item[size-1] in ascending order. */
public static void mergeSort (Comparable[] item, int size)
{ Comparable[] spare = new Comparable [item.length];
new MergeSorter (item, spare).sort (0, size - 1);
} //=======================
// IN-PLACE MERGESORT BY 2S
/** Precondition: size <= item.length; item[0]...item[size-1]
* are non-null values all Comparable to each other.
* Postcondition: The array contains the values it initially
* had but with item[0]...item[size-1] in ascending order. */
public static void mergeSortBy2s (Comparable[] item, int size)
{ int jump = 1;
while (jump * 2 < size)
jump *= 2;
for ( ; jump >= 1; jump /= 2)
sortGroups (item, size, jump);
} //=======================
private static void sortGroups(Comparable[] item, int size,
int jump)
{ for (int k = jump; k < size; k++)
insertInOrder (item, k, jump); // left as an exercise
} //=======================
} // END OF CompOp
public class QuickSorter
{
private Comparable[] itsItem; // the array to be sorted
public QuickSorter (Comparable[] item)
{ itsItem = item;
} //=======================
/** Precondition: start <= end; itsItem[start]...itsItem[end]
* are the Comparable values to be sorted. */
public void sort (int start, int end)
{ if (start < end) //1
{ int mid = split (start, end); //2
sort (start, mid - 1); //3
sort (mid + 1, end); //4
} //5
} //=======================
private int split (int lo, int hi)
{ Comparable pivot = itsItem[lo]; //6
boolean lookHigh = true; //7
while (lo < hi) //8
{ if (lookHigh) //9
{ if (itsItem[hi].compareTo (pivot) >= 0) //10
hi--; //11
else //12
{ itsItem[lo++] = itsItem[hi]; //13
lookHigh = false; //14
} //15
} //16
else //17
{ if (itsItem[lo].compareTo (pivot) <= 0) //18
lo++; //19
else //20
{ itsItem[hi--] = itsItem[lo]; //21
lookHigh = true; //22
} //23
} //24
} //25
itsItem[lo] = pivot; //26
return lo; //27
} //=======================
}
public class MergeSorter
{
private Comparable[] itsItem; // the array to be sorted
private Comparable[] itsSpare; // spare to facilitate sorting
public MergeSorter (Comparable[] item, Comparable[] spare)
{ itsItem = item;
itsSpare = spare;
} //=======================
public void sort (int start, int end)
{ if (start < end) //1
{ int mid = (start + end) / 2; //2
sortToSpare (start, mid); //3
sortToSpare (mid + 1, end); //4
merge(itsSpare, itsItem, start, mid, mid + 1, end); //5
} //6
} //=======================
private void sortToSpare (int start, int end)
{ if (start >= end) //7
itsSpare[start] = itsItem[start]; //8
else //9
{ int mid = (start + end) / 2; //10
sort (start, mid); //11
sort (mid + 1, end); //12
merge(itsItem, itsSpare, start, mid, mid + 1, end); //13
} //14
} //=======================
private void merge (Comparable[] from, Comparable[] into,
int lo, int mid, int hi, int end)
{ for (int spot = lo; spot <= end; spot++) //15
{ if (lo > mid || (hi <= end //16
&& from[lo].compareTo (from[hi]) > 0)) //17
into[spot] = from[hi++]; //18
else //19
into[spot] = from[lo++]; //20
} //21
} //=======================
}
class WorkerByBirth implements Comparable
{
private static int theNumComps = 0;
private Object itsWorker;
public WorkerByBirth (Object given)
{ itsWorker = given;
} //=======================
public int compareTo (Object ob)
{ theNumComps++;
return ((Worker) itsWorker).getBirthYear()
- ((Worker) ob).getBirthYear();
} //=======================
public static int numComps (Object[] givenArray, int size)
{ Comparable[] tempArray = new Comparable [size];
for (int k = 0; k < size; k++)
tempArray[k] = new WorkerByBirth (given[k]);
theNumComps = 0;
CompOp.insertionSort (tempArray, size);
for (int k = 0; k < size; k++)
given[k] = tempArray[k].itsWorker;
return theNumComps;
} //=======================
}
|
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |