001: package U2.T2.examples;
002:
003: import java.util.*;
004:
005: /**
006: * Performs a bi-directional bubble sort on "list", also known as a
007: * cocktail sort. After making bubbling from left to right, the
008: * algorithm then bubbles from right to left. There is a subtle error
009: * injected that causes the first element is ignored.
010: *
011: * <p>Call RT2 on this class with option --elemty=java.lang.Integer
012: */
013:
014: public class CocktailSort {
015: private Comparable[] list;
016:
017: /**
018: * The working function for Sort.
019: */
020: private void cocktail_sort() {
021: // INJECTING ERROR, beg should be initialized to 0:
022: int beg = 1; //Beginning index for the left-to-right pass
023: int end = list.length - 1; //End index for the left-to-right pass
024: Comparable tmp = null; //Temporary variable for swapping
025: boolean hasSwapped = false; //Denotes whether a swap was made during a pass
026: // main loop:
027: do {
028: hasSwapped = false;
029:
030: //Bubble sort from left-to-right starting at beg and ending at end
031: for (int i = beg; i < end; ++i) {
032:
033: if (list[i].compareTo(list[i + 1]) > 0) {
034: tmp = list[i];
035: list[i] = list[i + 1];
036: list[i + 1] = tmp;
037: hasSwapped = true;
038: }
039: }
040: --end; //Decrease end by one
041:
042: //Bubble sort from right-to-left starting at end and ending at beg
043: for (int i = end; i > beg; --i) {
044:
045: if (list[i].compareTo(list[i - 1]) < 0) {
046: tmp = list[i];
047: list[i] = list[i - 1];
048: list[i - 1] = tmp;
049: hasSwapped = true;
050: }
051: }
052: ++beg; //Increment beg by one
053:
054: } while ((hasSwapped == true) && (beg != end)); //While no swaps have been made
055: }
056:
057: /**
058: * Sort the given list.
059: */
060: public Comparable[] Sort(Comparable[] unsorted) {
061:
062: // Initializes list to the passed unsorted list, and then
063: // invokes the cocktail sort algorithm on that list. The
064: // resulting sorted list will then be returned.
065:
066: list = unsorted;
067: cocktail_sort();
068: return list;
069: }
070:
071: /**
072: * The specification of Sort.
073: */
074: public Comparable[] Sort_spec(Comparable[] unsorted) {
075:
076: Comparable[] r = Sort(unsorted);
077: boolean ok = true;
078: for (int i = 0; i < list.length - 1 && ok; i++)
079: ok = list[i].compareTo(list[i + 1]) <= 0;
080: assert ok : "POST";
081: return r;
082: }
083:
084: /**
085: * This one will sort a list. The result is put in an array.
086: */
087: public Comparable[] Sort(List<Comparable> unsorted) {
088: Comparable[] array = new Comparable[unsorted.size()];
089: for (int i = 0; i < unsorted.size(); i++)
090: array[i] = unsorted.get(i);
091: return Sort(array);
092:
093: }
094:
095: /**
096: * The spec. of Sort on List.
097: */
098: public Comparable[] Sort_spec(List<Comparable> unsorted) {
099:
100: Comparable[] r = Sort(unsorted);
101: boolean ok = true;
102: for (int i = 0; i < list.length - 1 && ok; i++)
103: ok = list[i].compareTo(list[i + 1]) <= 0;
104: assert ok : "POST";
105: return r;
106: }
107:
108: }
|