- Comparable
- Selection Sort
- Insertion Sort
- Shell Sort
- Shuffle
- Convex hull

# Comparable

Implement the `Comparable`

interface to make the `sort()`

universal.

```
public class File implements Comparable<File>{
…
public int compareTo(File b){
…
return -1; // this less than b
…
return +1; // this greater than b
…
return 0; // equal
}
…
}
```

```
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)
exchange(a,j,j-1);
else break; // compare to next
}// end for j
}// end for i
}// end sort()
```

# Selection sort

- In iteration i, find index
`min`

of smallest remaining entry.- Swap a[i] and a[min]

```
public static void sort(Comparable[] a){
int N = a.lengh;
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;
exchange(a, i, min);
}// end for i
}// end sort()
```

## Facts

- Running time is insensitive to input: always quadratic time
- Data movement is minimal: linear number of exchanges(one-step to its final position)

# Insertion Sort

Animation: Insertion Sort

```
public static void sort(Comparable[] a){
int n = a.length;
// although start with 0 is waste of time, think about if n = 0, 1 will cause mistake, you need another `if` statement to proof it
for (int i = 0; i < n; n++){
for (int j = i; j > 0; j--){
if (less(a[j], a[j-1]) exchange(a, j, j-1);
// all before is already sorted, so do break
else break;
}// end for j
}// end for i
}// end sort()
```

## Facts

It’s obviously that this sort is highly depend on the data.

- Best case: already in order. N-1 compares, 0 exchange.
- Worst case: reversed order. N(1+N)/2 compares, N(1+N)/2 exchanges. ~1/2 N^2
- Partially-sorted: linear. ~N. This feature will be used in the ‘Shellsort’

# Shellsort

Insertion sort is kind of waste: each time comparing with the the only 1-before item although the `j`

might be very small — considering the reverse case.

So we can jump. Compare to k-before item; If bigger, exchange. The result will be `h-sort`

. Like this:

every 4 interleaved item is sorted: L, M, P, T; E, H, S, S; …
The result will be **nearly ordered**.

imply `h-sort`

with different `h`

:

A g-sorted array remains g-sorted after h-sorting it.

It’s quiet nature. I’m not going to proof it..

After 3-sort, we can imply 1-sort, aka, original insertion sort. After that, the array will become sorted.

This algorithm is more efficient. The problem is how to determine the `h`

?

`2^i`

: 1, 2, 4, 8, 16, 32, … (BAD: ignore the even position until final 1-sort, the even position may remain very unstable)`2^i - 1`

: 1, 3, 7, 15, 31, 63, … (MAYBE)`3x + 1`

(x is the previous one): 1, 4, 13, 40, 121, 364, … (OK)- Sedgewick (merging of
`(9 ⨉ 4 i ) – (9 ⨉ 2 i ) + 1`

and`4 i – (3 ⨉ 2 i ) + 1`

): 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, … (GOOD)

Animation: Shell Sort

## Implement

```
public static void shellSort(Comparable a[]){
int n = a.length;
// in the cycle we do not have another check. we start with h
if (n == 0) return;
int h = 1;
// minium sub-sort array length is 3
while (h < n/3) h = h * 3 + 1;
// until 1-sort
while (h > 0){
for (int i = h; i < n; i++){
for (int j = i; j >= h; j-=h){
if (less(a[j], a[j-h])) exchange(a, j, j-h);
else break;
}// end for j
}// end for i
h /= 3; // h = h / 3; === h = (h - 1) / 3
// 1, 4, 13, 40, 121, 364, ...
}// end while h
}// end sort()
```

A more beautiful code:

```
for (int j = i; j >= h; j-=h){
if (less(a[j], a[j-h])) exchange(a, j, j-h);
else break;
}// end for j
// === equal to ===
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exchange(a, j, j-h);
```

we do not need a `else break;`

‘cause the statement is in the rules line.

## Cost

- worst-case with
`3x + 1`

: O(N^3/2) - avg with
`3x + 1`

: NlgN ( it’s a guess, accurate model has not yet been discovered)

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.

Unsolved questions:

- Asymptotic growth rate?
- Best sequence of increments?
- Average-case performance?

## Q: Does prime number is a good increments?

(Q: 素数是不是一个比较好的 increments?) A: No 实验见 Algs-part1-coursera/week-2-stack-queue/prime-shellsort at master · d4rkb1ue/Algs-part1-coursera · GitHub

```
$ java-algs4 PrimeShellSort < int30000.txt
size: 30000
3x + 1 in 0.014s
prime in 0.109s
$ java-algs4 PrimeShellSort < int30000.txt
size: 30000
3x + 1 in 0.015s
prime in 0.101s
$ java-algs4 PrimeShellSort < int30000.txt
size: 30000
3x + 1 in 0.014s
prime in 0.108s
$ java-algs4 PrimeShellSort < int30000.txt
size: 30000
3x + 1 in 0.015s
prime in 0.104s
```

# Shuffle

A simply solution is set each item with a random number, and then, base on the giving number to sort these items. However, it’s quiet waste. Sort is very expansive.

```
public void shuffle(Object[] a){
int n = a.length;
for (int i = 0; i < n; i++){
// exchange with [0,i]
exchange(a, i, StdRandom.uniform(i + 1));
}
}
```

You should exchange with `[0, i]`

instead of `[0, n]`

because `[i+1, n-1]`

is unseen, doing a whole array doesn’t give you a uniformly random result.

## Why `exchange(a, i, random[0,n))`

is not correct?

algorithms - What’s a uniform shuffle? - Computer Science Stack Exchange http://stats.stackexchange.com/questions/3082/what-is-wrong-with-this-naive-shuffling-algorithm

## Wrong practice

# Convex hull

The convex hull of a set of N points is the smallest perimeter fence enclosing the points.