Home Previous Next

CSC205::Lecture Note::Week 11
Assignments | Handouts | Resources | Email Thurman { compufoo::Twitter | Facebook | YouTube}
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview Assignment(s):  Code [stack & queue revisited] NumberSystemStack.java | CircularArrayQ.java | Buffer.java | PriorityQueue.java
[sort/search] BubbleSort.java | Bsearch.java

Priority Queues

A  priority queue  allows the highest priority element to be removed from a queue even though it may not be the "oldest."

Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.

An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Review Abstract Classes

Inheritance

Inheritance allows classes to be defined in terms of other classes.

In Java, inheritance is implemented when a class extends another class.

Polymorphism is when an object of a child class is used as an object of its parent class. In other words, an object of a given class can have multiple forms, either as it own class or as any class it extends.

By default, all classes extend the Object class that comes with the JSDK. Therefore, every object is-an object of class Object.

Some benefits obtained from using inheritance are.

You are not limited to just one layer of inheritance. The inheritance tree, or class hierarchy, can be as deep as needed.

In general, the further down in the hierarchy a class appears, the more specialized its behavior. [Class extension is most commonly used for specialization.]

The following is an example class hierarchy.

                        BankAccount
                     (account#, balance)
                              |
                    +---------+----------+
                    |                    |
            CheckingAccount       SavingsAccount
                                         |
                                +--------+------------+
                                |                     |
                          PassBookAccount     InvestmentAccount
                                       
   public class BankAccount extends Object {...}
   public class CheckingAccount extends BankAccount {...}
   public class SavingsAccount extends BankAccount {...}
   public class PassBookAccount extends SavingsAccount {...}
   public class InvestmentAccount extends SavingsAccount {...}

   CheckingAccount  "is-a"  BankingAccount  and  PassBookAccount
   "is-a"  SavingsAccount  and so on.

	Note:  BankAccount extends Object.

Java supports single-inheritance only (i.e. a class can extend only one class).

Typical characteristics of a derived class are.

The representation of the parent class cannot be altered (i.e. neither data nor functionality [behavior] can be removed).

Functionality defined in the parent class can be modified by overriding the appropriate methods in the derived class.

If a parent method is overridden in the child class and the child wants to invoke the parent's method, then the super keyword must be used to qualify the method name.

   class Foo {
      void echo() {...}
   }

   class Bar extends Foo {
      void echo() { 
         super.echo();  //invoke echo() implemented in the parent class
         ...
      }
   }

From 1999 (so it might be dated/stale): JavaWorld.com::How to avoid traps and correctly override methods from java.lang.Object

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Abstract Classes and Methods

An abstract class is one that is used for derivation only. Objects cannot be instantiated from an abstract class. Attempting to do so at compile-time is a syntax error. Attempting to do so at run-time causes an error.

An abstract class can contain data and methods. Some of the methods may in turn be declared to be abstract. Abstract methods have no implementations.

If a class contains an abstract method, then it must be an abstract class. However, you can have an abstract class that doesn't have any abstract methods.

An abstract method is a method that is declared, but the method's implementation is found in one of the derived classes. In otherwords, the classes that extend an abstract class are responsible for providing implementations of the abstract methods.

   Syntax:

      abstract class SomeClassName { ... }

The Number class in the java.lang package represents the abstract concept of numbers. It is used as a superclass to the wrapper classes (e.g. Integer and Float).

   public abstract class Number implements java.io.Serializable {
       public abstract int intValue();
       public abstract long longValue();
       public abstract float floatValue();
       public abstract double doubleValue();
       public byte byteValue() { return (byte)intValue(); }
       public short shortValue() { return (short)intValue(); }
   }

Each wrapper class (e.g. Byte, Integer, etc.) extends Number (except for Character).

The Number class ensures that there is common functionality across all classes that extend it (e.g. intValue()).

Every class that inherits from Number must implement the methods that are defined to be abstract. The Number class contains a couple of non-abstract methods (shortValue() and byteValue()); in other words, these methods are implemented in the class. If you were to write a class that extends Number, then you would have to check to see if the non-abstracts methods work for you specific type of number. If they don't, then you can provide implementations for the non-abstract methods by overriding them.

You cannot instantiate a Number object. You can, however, have a handle (i.e. object variable) to a Number object (e.g. Number num). The values that can be assigned to a Number object variable are handles to objects instantiated from classes that extend the Number class.

   Number num = new Integer(100);  // a typecast is not necessary

Docs.Oracle.com::Tutorial::Abstract Methods and Classes

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Introduction to Sorting

Typically, sorting is executed on files that contain records having keys. The keys are used to control the sort.

The objective of a sort is to rearrange records so that their keys are ordered according to some well-defined ordering rule (e.g. numerical order or alphabetical order).

The sorting problem is defined as follows:

   Given a set of records r1, r2, ..., rn with key 
   values k1, k2, ..., kn, respectively, arrange the
   the records into any order  s  such that
   records rs1, rs2, ..., rsn
   have keys obeying the property 
   ks1 <= ks2 <= ... <= ksn.

If the file being sorted can fit into memory, then an internal sort can be done; otherwise, sorting files from a disk (or some other secondary storage device) is called external sorting.

For discussion purposes, we will focus on internal sorting (more specifically, the sorting of arrays).

A characteristic of sorting methods is stability. A sort is stable if it preserves the relative order of equal keys in a file; otherwise, it is non-stable. For example, if an alphabetized class list is sorted by grade, then a stable method produces a list in which students with the same grade are still in alphabetical order, but a non-stable method is likely to produce a list that is no longer in alphabetical order.

The efficiency of a sorting algorithm depends on two measurements:

The amount of extra memory used by a sort is important. Extra memory is used by sort in the following ways:

In general, if the records being sorted are large, then avoid "shuffling" them around by rearranging the elements of an array of pointers (or indicies). This is called indirect sorting.

Swapping adjacent records (i.e. items) is called an exchange.

There are numerous "simple" sorting algorithms are based on comparing and/or exchanging adjacent records -- they are: bubbleSort, exchangeSort, selectionSort, and insertionSort.

There are numerous sorting algorithms that might be better than the aforementioned "simple" sorts. Some of these sorts are: shellSort, mergeSort, and quickSort.

Sorting and Searching: The Art of Computer Programming by Donald E. Knuth is a classic text on the subject of sorting. It covers about 25 different sorting algorithms. The following a quote from the book:

"But you can't look up all those license numbers in time," Drake objected. "We don't have to, Paul. We merely arrange a list and look for duplications." -- Perry Mason (The Case of the Angry Mourner, 1951)

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


BubbleSort

BubbleSort is an exchange sort that is inefficient, but easy to to understand.

Keep passing through the list, exchanging adjacent elements, if necessary; when no exchanges are required on some pass, the file is sorted.

  1. begin with elements 0 and 1 ('i' and 'j')
  2. compare two adjacent elements 'i' and 'j'
  3. if element 'i' less than element 'j', swap them
  4. move one position to the right

When sorting in ascending order, the largest element "sinks" to the end of the list and the smallest values "bubble up" towards their proper positions near the front of the list.

BubbleSort pseudo-code:

   // assume we have an array 'a' with length 'n'

   end_i = n-1;
   while (end_i > 0) {
      last_i = 0;
      for (next_i = 0; next_i < end_i; next_i++) {
         if (COMPARE (a, next_i, next_i+1)) {
            SWAP (a, next_i, next_i+1);
            last_i = next_i;
         }
      }
      end_i = last_i;
   }

BubbleSort is terrible [O(n^2)] if the list is sorted in reverse order. It works great given a list that is already sorted.

YouTube.com::Bubble Sort by CS50 at Harvard

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


InsertionSort

In most cases, InsertionSort is the best of the simple sorts (i.e. BubbleSort, ExchangeSort, and SelectionSort).

InsertionSort works well if only a few elements need sorting; however, it is a poor choice if dealing with a large number of elements.

Often times InsertionSort is used as the final stage of more advanced sorts (e.g. QuickSort).

For an example of InsertionSort, assume we have an array A and its length is N. Let's look at pass i (1 <= i <= N-1). The sublist A[0] to A[i-1] is already sorted in ascending order. The pass assigns A[i] to the list. Let A[i] be the TARGET and move down the list, comparing the target with items A[i-1], A[i-2], and so forth. Stop the scan at the first element A[j] that is less than or equal to TARGET or at the beginning of the list (j=0). As we move down the list, slide each element to the right (A[j]=A[j-1]). When the correct location for A[i] is found, insert it at location j.

Said another way.

Assume elements are being collected using array named 'a'. The initial state is that the first element, considered by itself, is sorted. Each time a new element with value 'n' is "added" to the collection, it is inserted into a slot 'i' such that a[i-1] <= a[i] <= a[i+1]. If the new element is inserted into the array (i.e. it is not the last element), then the elements to the right of the insertion point must be shifted.

Many card players use the insertion sort. They are dealt a hand of cards. Each time they receive a card they place it in their hand in a sorted order. Luckily for them, shifting cards is simple. The following is an example of a card player that stores their cards in ascending order (lowest-to-highest).

   start with an empty hand
   receive an 8:  8                 //1 element is always sorted
   receive a  4:  4 8               //4 is inserted, the 8 was shifted
   receive a 10:  4 8 10            //10 added (no shifting necessary)
   receive a  2:  2 4 8 10          //4,8,10 all shifted
   receive a  7:  2 4 7 8 10        //8,10 shifted

InsertionSort pseudo-code.

   // assume we have an array 'a' with 'n' elements

   for (cur_i = 1; cur_i < n; cur_i++) {
      next_i = cur_i;
      while (next_i > 0) {
         if (COMPARE (a, next_i, next_i-1))
            SWAP (a, next_i, next_i-1);
         next_i--;
      }
   }

YouTube.com::Insertion Sort by CS50 at Harvard

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


QuickSort

QuickSort  was first developed by C.A.R. Hoare. It requires the picking of a partition element (pivot) and then partially sorting the array about the partition. You can then sort each of the two partitions by recursive application of the same technique. The algorithm can sort quite rapidly, but it can also sort very slowly [O(n^2) worst case].

QuickSort is a fast divide-an-conquer algorithm when comparison sorting arrays in place (frequently O(n log n)).

The basic algorithm for QuickSort is recursive and consists of the following steps:

  1. If the number of elements is 0 or 1, return.
  2. Pick any element and call it the pivot.
  3. Partition remaining elements into two disjoint groups called L and R.
  4. Return the result of QuickSort(L), followed by the pivot, followed by QuickSort(R).
The pivot divides array elements into two groups: those smaller than the pivot and those larger than the pivot.

The partition step places every element except the pivot in one of two groups.

   13  81 43  92  31  65  57  26  75  0

   Assume 65 is selected as the pivot.  Partition the elements.

    Left:  13  43  31  57  26  0
   Right:  81  92  75

   Quicksort the left items.  Quicksort the right items.
   0  13  26  31  43  57      75  81  92
                          65
Example:
   Original list:
      8  1  4  9  6  3  5  2  7  0

   Select the pivot  6  and swap the pivot with the last element.

      8  1  4  9  0  3  5  2  7  6

   Run   i  from left-to-right, and  j  from right-to-left.
   When  i  sees a large element,  i  stops.  When  j  sees
   a small element,  j  stops.  If  i  and  j  have not
   crossed, swap their items and continue; otherwise, stop
   this loop.

      i  stops at element 8; j stops at element 2
      the 8 and 2 are swapped

   2  1  4  9  0  3  5  8  7  6

      i  stops at element 9; j stops at element 5
      the 9 and 5 are swapped

   2  1  4  5  0  3  9  8  7  6

      i  stops at element 9; j stops at element 3
      i and j have crossed -- swap pivot with
      i'th element (6 with 9)

   2  1  4  5  0  3  6  8  7  9
Picking the pivot is important to good performance. Never choose the first element as the pivot (you should also avoid the last element). The middle element is usually a reasonable choice. The perfect pivot is one that results in equally sized partitions. Picking a random pivot has proven efficient.

The  median-of-three  is a popular technique for picking a pivot. Sort the first, middle and last elements of the list and use the median (in this case middle) value. Using this technique is good because while in the process of determining the pivot, you are also getting started on the sorting of the list (element 0 will be less than the pivot and element N-1 will be greater than the pivot).

QuickSort pseudo-code:

   quickSort(T a[], int left, int right) 

      if (left >= right) return;
      SWAP (a, left, (left+right)/2);
      last = left;
      for (i = left+1; i <= right; i++) {
         if (COMPARE (a, i,  left) {
            ++last;
            SWAP (a, last, i);
         }
      }

      SWAP (a, left, last);

      quickSort(a, left, last-1);
      quickSort(a, last+1, right);

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


The Sounds of Sorting

YouTube.com::Tone of Sorting - Quick Sort Visualization with 100 elements [Casper Beyer]

YouTube.com::15 Sorting Algorithms in 6 Minutes [Timo Bingmann]

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Additional Resources}


Home Previous Next