Home Previous Next

CSC205AA::Lecture Note::Week 09
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview
Assignment(s): [Note: All assignments have been assigned.]
• [program] #Q [due 04/21/02019]
• [program] #sorting [due 04/28/02019]
• [program] #BST [due 05/05/02019]
Code
``` [multi-dimensional arrays] MultiArrays.java | TwoDimensionalArrays.java | BYTES.java | ThreeDimensionalArray.java ...... PythagoreanTriples.java | Temps.java (4-d) [stack] NumberSystemStack.java | Stack.java | ParenChecker.java | Stack2.java [queue] Queue.java | FootNotes.java (footnotes.in.txt) | Q.java | TestQ.java | PriorityQueue.java ...... CircularArrayQ.java | Buffer.java [linked-list] SinglyLinkedList.java | TestLinkList.java [new version] SinglyLinkedList.java | DoublyLinkedList.java ```

### Multi-dimensional Arrays

Multi-dimensional arrays are arrays-of-arrays. Example: a two-dimensional array is an array of one-dimensional arrays.

```   int someArray[][];  // someArray  will reference an array whose elements
// are of type:   array-of-int

someArray = new int[3][];
for (int i = 0; i < someArray.length; i++)
someArray[i] = new int[5];

int[0][0]  int[0][1]   int[0][2]   int[0][3]   int[0][4]
int[1][0]  int[1][1]   int[1][2]   int[1][3]   int[1][4]
int[2][0]  int[2][1]   int[2][2]   int[2][3]   int[2][4]

/*
* example of a jagged two-dimensional array
*/
a = new int[4][];
for (int i = 0; i < a.length; i++)
a[i] = new int[i + 1];

int[0][0]
int[1][0]  int[1][1]
int[2][0]  int[2][1]  int[2][2]
int[3][0]  int[3][1]  int[3][2]  int[3][3]

The EXPR  a[i]  accesses the  i'th   one-dimensional array.

The following code snippet creates a 2x3 table of Foo objects.

Foo[][] foo = new Foo[2][3];
for (int i = 0; i < foo.length; i++)
for (int j = 0; j < foo[i].length; j++)
foo[i][j] = new Foo();

or

Foo[][] foo = new Foo[2][];
for (int i = 0; i < foo.length; i++)  {
foo[i] = new Foo[3];
for (int j = 0; j < foo[i].length; j++)
foo[i][j] = new Foo();
}
```

Excluding some mathematical and scientific computing, multi-dimensional arrays rarely exceed two dimensions.

##### MultiArrays.java

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

### Lists

A  list  is a linear data structure whose components can only be accessed sequentially, one after another.

The first item is a list is called the  head  or  front  and the last item is called the  tail ,  back  or  end.

Lists have the following features:

• varying lengths (a list grows when items are added to it, and it shrinks when items are removed)
• homogeneous components (e.g. list of integers, list of prime numbers, list of `string` objects)
List operations include:
• define a list
• check if a list is empty
• check if a list is full
• reset (move list cursor to front of the list)
• end-of-list (move list cursor to back of the list)
• get current item
• insert before current item
• insert after current item
• remove item

GDT::Java::Code::GoofyIntList.java

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

### Sets

A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).

The objects of a set are called elements (or members).

A set the following properties:

• all elements of a set belong to some universe
• any object of the universe is either in a set or it is not
• there is no particular ordering of elements within a set

Example of sets:

• a set of classes that a student it taking
• a set of prime numbers

The following operations are performed on a set:

• construct (i.e. define/create/instantiate) a set
• check to see if an object is a member of a set
• test if a set is empty
• get the cardinality (size of a set; number of elements/members)
• check if set A is included in set B (if so, then A is subset of B and B is superset of A)
• determine union of two sets (all elements appearing in A or B)
• determine intersection of two sets (all elements appearing in A and B)
• difference between to sets (all elements of set A not in set B -- notation: A - B)
• add an object to a set
• remove an object from a set
• clear all objects from a set

An array (i.e. vector) can be used to store a set.

A class that is used to represent a set could have the following instance methods:

```   Set();
Set(int capacity);
boolean isMember(Object element);
boolean isEmpty();
boolean isSubset(Set other);
int size();
Set union(Set other);
Set intersection(Set other);
Set difference(Set other);
void remove(Object element);
void clear();
```

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

### Stacks

A  stack  is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).

My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and  pushes  them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.

A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called  push ,  pop  and  top .

Elements are inserted onto a stack by using a push operation.

Elements are deleted from a stack by using a pop operation.

The most-recently inserted element can be examined by using a top operation.

Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:

1. create an empty stack
1. if the symbol is an opening symbol, push it onto the stack
2. if the symbol is a closing symbol and the stack is empty, then report an error
3. otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
3. at EOF, if stack is *not* empty, then report an error

A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.

Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).

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

### Queues

A  queue  is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).

Operations are:

• `enqueue` -- insert at the back of the line (append)
• `dequeue` -- remove from the front of the line
• `front` -- access item from front of the line

Examples of a queue: buffered input and a line printer spooler.

Another queue example: message queues.

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

### 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}

A linked list is a low-level structure upon which high-level data structures can be built (e.g. `stacks` and `queues` can be implemented using a linked-list).

Sometimes the only Abstract Data Type (ADT) available for organizing data is the built-in array; however, this can be problem if the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. It can also be problem when arrays need to grow (i.e. increase in length [capacity]). In these cases a linked-list may be the solution.

A linked-list is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).

If each node contains only one link member, then we have a singly linked list.

Unlike an array, the nodes of a linked-list do not necessarily occupy consecutive memory locations.

The implementation of a linked-list relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linked-list is created, its length (i.e. # of nodes) is unknown.]

#### Terminology

A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The end-of-list (EOL) is called the rear its link data member has the value `NULL` (i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.

#### class Node

Example instance variables.

```   some_data_type data   // 1 or more of these
Node next             // pointer to next node
```

Example instance variables.

```   head      // handle to the 1st node in the linked-list
size      // # of nodes in linked-list
capacity  // maximum nodes allowed
// maybe more...
```

Possible instance methods.

```   constructors to initial linked-list objects
insert() -- insert nodes into a linked-list
delete() -- delete (remove) nodes from a linked-list
update() -- update (modify) a node in a linked-list
search() -- search a linked-list for data
// maybe more...
```
##### Bjarne Stroustrup: Why you should avoid Linked Lists

{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 number of comparisons
• the number of swaps

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

• sort in place using no extra memory except for a small stack or table
• need enough extra memory to store a copy of the array to be sorted

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)
##### Update::02019.04.17

YouTube.com::Sorting Out Sorting::Part 1 | Part 2 | Part 3 (heap sort) | Part 4

{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  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}

### ExchangeSort

ExchangeSort sort is an exchange sorts that works as follows: The item at index 0 is compared with each subsequent item in the list at index 1, 2, ..., N-1. For each comparison, if the subsequent item is smaller than the element at index 0, the two entries are exchanged. Repeat this process with index 1, index 2 and so on up to index N-2.

`ExchangeSort` pseudo-code:

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

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

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

### SelectionSort

SelectionSort is a simple sorting algorithm that makes a number of passes through a list (or sublist) and, on each pass, selects one element to be correctly position. Each element is moved only once; therefore, this type of sort can be handy when sorting files with very large records and small keys.

The item at index 0 is compared with each subsequent item in the list at index 1, 2, ..., N-1. The index of the smallest item encountered is saved. After the comparisons have been completed, the smallest item is swapped with the item at index 0. Repeat this process with index 1, 2, and so on up to N-1.

`SelectionSort` pseudo-code:

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

for (cur_i = 0, limit = n-1; cur_i < limit; cur_i++) {
small_i = cur_i;
for (next_i = cur_i+1; next_i < n; next_i++) {
if (COMPARE (a, next_i, small_i))
small_i = next_i;
}
if (small_i != cur_i)
SWAP (a, cur_i, small_i);
}
```

YouTube.com::Selection Sort by CS50 at Harvard

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

### ShellSort

ShellSort was discovered by a computer scientist named Donald Shell in 1959. It is also referred to as the diminishing gap sort.

It is based on `InsertionSort`, but adds a new feature that improves performance. The basic idea behind this sort is that in early stages, far-apart elements are compared, rather than adjacent ones as in simplier exchange sorts. This tends to eliminate large amounts of disorder quickly, so later stages have less work to do. The interval (i.e. gap) between compared elements is gradually decreased to one, at which point the sort effectively becomes an exchange method. The performance of this algorithm can be influenced by the gaps that are used.

`ShellSort` is good for medium-sized arrays (few thousand items). By default, `ShellSort` should probably be your choice for sorting. If performance becomes an issue, then change to a more advanced sorting technique such as `QuickSort`.

`ShellSort` pseudo-code:

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

for (gap = n/2;  gap > 0;  gap /= 2) {
for (i = gap;  i < n;  i++)
for (j = i-gap;  j >= 0;  j -= gap) {
if (!COMPARE (a, j, j+gap))
break;
SWAP (a, j, j+gap);
}
}

```

YouTube.com::Java Shell Sort by Derek Banas

{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}