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
Anchor | ||||
---|---|---|---|---|
|
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.
...
===================================================================================================================
Anchor | ||||
---|---|---|---|---|
|
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)
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\].
\\ Wiki Markup
The following are all valid calls to the above method:
...
===================================================================================================================
Anchor | ||||
---|---|---|---|---|
|
A Tale of Two Visitors
You were shown two different styles of writing visitors, with and without input parameters. Why two different techniques?
...
===================================================================================================================
Anchor | ||||
---|---|---|---|---|
|
Binary Search in a Sorted Array
The recursive technique used to find a value in a sorted array is very useful in many situations.
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?
...
- Open the book in the middle
mid = (max-+min)/2
(min, max and mid are the page numbers here) - If the name you want is on that page, you're done.
- 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.
- 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.
...
- min = 0, max = 13, so mid = 6 ==> so look at the #12 (min, max and mid are indices into the array here)
- min= 0, max = 6, and 11 < 12, so look at mid = (6+0)/2 = 3, i.e. the #7.
- min= 3, max = 6, and 11 > 7, so look at the mid = (6+3)/2 = 4, i.e. the #10
- min = 4, max = 6 and 11>10 so look at the mid=(4+6)/2 = 5, i.e. the #11
- 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.
No Format |
---|
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.
=====================================================================================================================================
Anchor | ||||
---|---|---|---|---|
|
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: