‣ Rules of the game:
public class Experiment
{
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
Double[] a = new Double[N];
for (int i = 0; i < N; i++)
a[i] = StdRandom.uniform();
Insertion.sort(a);
for (int i = 0; i < N; i++)
StdOut.println(a[i]);
}
}
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i; j > 0; j--)
if (a[j].compareTo(a[j-1]) < 0)
exch(a, j, j-1);
else break;
}
‣ Selection sort:
・In iteration i, find index min of smallest remaining entry.
・Swap a[i] and a[min]
Algorithm. ↑ scans from left to right.
Invariants.
・Entries the left of ↑ (including ↑) fixed and in ascending order.
・No entry to right of ↑ is smaller than any entry to the left of ↑.
public class Selection
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int min = i;
for (int j = i+1; j < N; j++)
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
private static boolean less(Comparable v, Comparable w)
{ /* as before */ }
private static void exch(Comparable[] a, int i, int j)
{ /* as before */ }
}
‣ Insertion sort:
・In iteration i, swap a[i] with each larger entry to its left.
Algorithm. ↑ scans from left to right.
Invariants.
・Entries to the left of ↑ (including ↑) are in ascending order.
・Entries to the right of ↑ have not yet been seen.
public class Insertion{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i; j > 0; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
else break;
}
private static boolean less(Comparable v, Comparable w)
{ /* as before */ }
private static void exch(Comparable[] a, int i, int j)
{ /* as before */ }
}
Insertion sort: best and worst case
Best case. If the array is in ascending order, insertion sort makes
N- 1 compares and 0 exchanges.
Worst case. If the array is in descending order (and no duplicates),
insertion sort makes ~ ½ N 2 compares and ~ ½ N 2 exchanges.
‣ Shell sort
Shellsort: Java implementation
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...
while (h >= 1){
// h-sort the array.
for (int i = h; i < N; i++)
{
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h/3;
}
}
private static boolean less(Comparable v, Comparable w)
{ /* as before */ }
private static void exch(Comparable[] a, int i, int j)
{ /* as before */ }
}
Why are we interested in shellsort?
Example of simple idea leading to substantial performance gains.
Useful in practice.
・Fast unless array size is huge (used for small subarrays).
・Tiny, fixed footprint for code (used in some embedded systems).
・Hardware sort prototype.
Simple algorithm, nontrivial performance, interesting questions.
・Asymptotic growth rate?
・Best sequence of increments?
・Average-case performance?
‣ Shuffling
・Generate a random real number for each array entry.
・Sort the array.
‣ Convex hull
The convex hull of a set of N points is the smallest perimeter fence
enclosing the points.
Equivalent definitions.
・Smallest convex set containing all the points.
・Smallest area convex polygon enclosing the points.
・Convex polygon enclosing the points, whose vertices are points in set.
## Convex hull application: motion planning
Robot motion planning.
Find shortest path in the plane from s to t
that avoids a polygonal obstacle.
Farthest pair problem.
Given N points in the plane, find a pair of points
with the largest Euclidean distance between them.
This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.
ConversionConversion EmoticonEmoticon