Vector-like object, so we don't explicity refer to the vector.
/**
* Sort all the elements in the subvector between lb and ub.
* pre: 0 <= lb <= ub < size()
* pre: the elements in the vector are comparable using
* a lessEqual method
* post: elementAt(lb) <= elementAt(lb+1) <= ... elementAt(ub)
* post: no element is added to or removed from the vector
*/
public void selectionSort(int lb, int ub)
{
// Variables
int index_of_largest; // ... element in subrange
// The preconditions will be checked in the following
// function call, so we don't check them here
// Base case: one element, so it's sorted
if (lb == ub) {
return;
}
// Find the index of the largest element in the subrange
index_of_largest = indexOfLargest(lb,ub);
// Swap that element and the last element
swap(index_of_largest, ub);
// Sort the rest of the subvector (if there is any)
// Note that we don't have to compare ub-1 to lb, since
// the preconditions and the base case take care of it.
selection_sort(lb,ub-1);
} // selectionSort
/**
* Find the index of the largest element in a subvector
* pre: 0 <= lb <= ub < size()
* pre: the elements in the vector are comparable using
* a lessEqual method
* post: returns I s.t. for all i, lb <= i <= ub,
* elementAt(I) >= elementAt(i)
*/
public int indexOfLargest(int lb, int ub) {
// Variables
int guess; // Current guess as to index of largest
// Check the preconditions
Assert.pre(lb <= ub, "nonempty subrange");
Assert.pre(0 <= lb, "reasonable starting point");
Assert.pre(ub < size(), "reasonable ending point");
// Make initial guesses
guess = lb;
// Repeatedly improve our guesses until we've looked at
// all the elements
for(int i = lb+1; i <= lb; ++i) {
if (elementAt(guess).lessEqual(elementAt(i))) {
guess = i;
} // if
} // for
// That's it
return guess;
} // index_of_largest
Vector)
/**
* Sort a subvector.
* pre: 0 <= lb <= ub < size()
* pre: the elements in the vector are comparable using
* a lessEqual method
* post: elementAt(lb) <= elementAt(lb+1) <= ... <= elementAt(ub)
*/
public void insertionSort(int lb, int ub)
{
// Variables
Object tmp; // The object that we'll be inserting
// Check the preconditions
Assert.pre(lb <= ub, "nonempty subrange");
Assert.pre(0 <= lb, "reasonable starting point");
Assert.pre(ub < size(), "reasonable ending point");
// Base case: one element, so it's sorted
if (lb == ub) {
return;
}
// Remember the element at the end, and then remove it
tmp = elementAt(ub);
removeElementAt(ub);
// Sort all but that element
insertionSort(lb,ub-1);
// Insert the element at the proper place. This may throw an
// IncomparableException.
insert(findPlace(lb,ub-1,tmp), tmp);
} // insertionSort
findPlace() (which finds the proper place in the vector to insert the element).
Each insertion requires O(n) steps, and each place determination takes
O(log_2(n)) steps, so the running time is O(n*(n+log_2(n)) which is O(n).
temp
/**
* Sort a vector, returning a sorted version of the vector.
* pre: The elements in the vector are comparable.
* post: Returns a sorted version of the vector (defined elsewhere).
* post: The original vector is not changed.
*/
public static VectorOfComparable mergeSort(VectorOfComparable v) {
int middle; // Index of middle element
// Base case: vector of size 0 or 1
if (v.size() <= 1) {
return v.clone(); // Cloned, so that it is safe to modify
// the returned vector
} // if
// Recursive case: split and merge
middle = v.size() / 2; // Integer division gives integer
return merge(mergeSort(v.subVector(0,middle));
mergeSort(v.subVector(middle+1,v.size())));
} // mergeSort
/**
* Merge two sorted vectors into a single sorted vector.
* pre: Both vectors are sorted
* pre: Elements in both vectors are comparable
* post: The returned vector is sorted, and contains all the
* elements of the two vectors
* post: The two arguments are not changed
*/
public static VectorOfComparable merge(VOC left, VOC right) {
// Variables
Vector result = new VectorOfComparable(left.size()+right.size());
int left_index=0; // Index into left vector
int right_index=0; // Index into right vector
int index=0; // Index into result vector
// As long both vectors have elements, copy the smaller one.
while ((left_index<left.size()) && (right_index<right.size())) {
if(left[left_index].smaller(right[right_index])) {
result[index++] = left[left_index++];
} // first element in left subvector is smaller
else {
result[index++] = right[right_index++];
} // first element in right subvector is smaller
} // while
// Copy any remaining parts of each vector.
while(left_index<left.size()) {
result[index++] = left[left_index++];
}
while(right_index<right.size()) {
result[index++] = right[right_index++];
}
// That's it
return result;
} // merge
/**
* Sort a subvector using quick sort.
* pre: All elements are comparable.
* pre: 0 <= lb <= ub < size()
* post: The vector is sorted.
*/
public void quickSort(int lb, int ub) {
// Variables
Comparable pivot; // The pivot used to split the vector
int mid; // The position of the pivot
// Base case: size one
if (lb == ub) return;
// Pick a pivot. Often, this is the second element of the
// vector (for some reason, it works better than the first).
// More clever selection techniques might also exist.
pivot = selectPivot(lb,ub);
// Determine the position of the pivot
mid = split(pivot, lb, ub);
// Recurse
if (mid-1>lb) quickSort(lb,mid-1);
if (mid+1<ub) quickSort(mid+1,ub);
} // quickSort
/**
* Partition a vector into two subvectors: those less than or
* equal to a particular element (the pivot), and those greater
* than the pivot.
* returns: The index of the pivot (mid) if it's in the vector.
* returns: the index of the largest element smaller than
* pivot, if it's not.
* pre: lb <= ub
* pre: the elements in the vector are comparable
* post: for all 0 <= i <= mid, mid < j < size()
* elementAt(i) <= elementAt(j)
*/
public int partition(Comparable pivot, int lb, int ub) {
// Keep going until we reach the middle
while(lb < ub) {
// If we have a small enough element on the left, advance
// the lower-bound.
if (elementAt(lb).lessEqual(pivot)) ++lb;
// If we have a large enough element on the right, advance
// the upper bound. For safety, we don't advance both in the
// same round.
else if (pivot.less(elementAt(ub))) --ub;
// If necessary, swap elements in the wrong part of the
// vector
if (pivot.less(elementAt(lb)) &&
elementAt(ub).less(pivot)) {
swap(lb,ub);
}
} // while
// lb = ub, so we can return
return lb;
} // split
partition method
actually works (that it partitions correctly and that it terminates). selectionSort, and would take time O(n^2). (this page was taken from http://www.math.grin.edu/~rebelsky/Courses/CS152/98S/Outlines/outline.25.html)