Page History

This week's lab is a bit of a potpourri of topics

...

:

• Quicksort Algorithm

• Variable Argument Lists

• Two Visitor Styles

• Binary Search Algorithm

• Insertion into a Doubly-linked list

Quicksort

Quicksort is the most common sorting algorithm in use today.  In light of its technological impact, it's good to know how it works. 

...

===================================================================================================================

Variable Argument Lists

We discussed this before in lab and lecture, but it's worth revisiting to make sure everyone understands it.

...

(Note: there are more efficient ways of writing this method, but I wanted to show you several features at once)
unmigrated-wiki-markup

A vararg parameter comes in as an array, so one can figure out how many parameters were supplied (params.length) and one can access each supplied value using regular array syntax, e.g. params\[i\]. \\

The following are all valid calls to the above method:

...

===================================================================================================================

 A A Tale of Two Visitors

You were shown two different styles of writing visitors, with and without input parameters.    Why two different techniques?

...

===================================================================================================================

Binary Search in a Sorted Array

...

Consider the following sorted array of values:unmigrated-wiki-markup

{{\[1, 2, 4, 7, 10, 11, 12, 13, 20, 25, 27, 28, 30\]}}

Supposed you're give a value, x, what's the fastest way to either find that value in the array or determine if it is not present?

...

1. Open the book in the middle  mid = (max-+min)/2 (min, max and mid are the page numbers here)
2. If the name you want is on that page, you're done.
3. If the name is before the names where you opened the book, re-open the book halfway on the smaller side and repeat the process.
4. If the name is after the names where you opened the book, re-open the book halfway on the larger side and repeat the process.

...

1. min = 0, max = 13, so mid = 6 ==>  so look at the #12 (min= 0, max and mid are indices into the array here)
2. min= 0, max = 6, and 11 = 6, and 11 < 12, so look at mid = (6+0)/2 = 3, i.e. the #7.
3. min= 3, max = 6, and 11 > 7, so look at the mid = (6+3)/2 = 4, i.e. the #10
4. min = 4, max = 6 and 11>10 so look at the mid=(4+6)/2 = 5, i.e. the #11
5. min = 5, max = 6,  there's only one element left and since 11 = 11, we found it! 

...

One way to look at what is going on here is to think of the sorted array as already being in the form of a binary search tree, where each mid-point is the top node of a sub-tree.    All the above algorithm is doing is walking down from the top of the binary search tree., i.e the path 12 => 7 => 10 => 11.

                    12
                /        \
             7               25
          /     \         /     \
        2        10     13        28
      /  \          \      \     /  \
     1    4          11     20  27   30

It is a very useful notion to conceptually view an array as a tree.   This enables one to leverage the power of recursive data structures with the speed and compactness of an array.

============================================================================================================================================

Insertion into a Doubly-linked List

 Inserting a node into a doubly-linked list, ala BiList, isn't difficult, but it does take care to make sure that one has the right values for the node references at any given moment.    Here's a pictoral explanation of the process: