Simple in principle but Hard in practice
原理简单但是难以实践#

• “Professional programmers had a couple of hours to convert the above description (binary search) into a program in the language of their choice …
  “专业程序员有几个小时的时间将上述描述（二分查找）转换为他们选择的语言编写的程序…
• At the end of the specified time, almost all the programmers reported that they had correct code for the task …
  “在指定的时间结束时，几乎所有程序员都报告说他们已经为该任务编写了正确的代码…
• ninety percent of the programmers found bugs in their programs.”
  “90%的程序员在他们的程序中发现了错误。”

Principle 原则#

Efficient search in a sequence. 在序列中高效搜索。
Requirement (pre-condition): The sequence must be ordered.
要求（前提条件）：序列必须 有序。 This version is by Prof. Niklaus Wirth
此版本由 Niklaus Wirth 教授提供
It is surprisingly efficient and easy to show to be correct
它非常高效，而且很容易证明其正确性

Pre-condition 前置条件#

The sequence in the array must be ordered.
数组中的序列必须是有序的。

1
T a[N]; (* a[0] to a[N-1] *)
2
/* T is any type for which < == ... defined, such as int */
3
/* precondition:
4
    0 <=size <= N &
5
    (∀i: 0 < i < size: a[i-1] <=a[i]) */

Invariant 不变式#

1
/* precondition: 0 <=size <= N &
2
(∀i: 0 < i < size: a[i-1] <= a[i]) */
3
int left, right; /* 0 ... size */
4
/* invariant: precondition &
5
    a[0 ... left–1] < x &  // all before left are less than x
6
    a[right ... size-1] >= x*/

all from right up to size-1 are at least as big as x 所有从 right 到 size-1 的元素都至少和 x 一样大

Initially#

1
left = 0; right = size;
2
/* makes empty segments */

Finally#

Outline of loop 循环概述#

1
left = 0; right = size;
2
/* invariant*/
3
while (left != right) {
4
    /* invariant & left != right */
5
    body
6
    /* invariant */
7
}
8
/* (invariant & left == right) => postcondition*/

Body: Inspect mid element 主体：检查中间元素#

1
int mid;
2
…
3
mid = (left + right) / 2;
4
a[mid] < x ?     left = mid +1;
5
a[mid] >= x ?    right = mid;

Body: Inspect mid element 主体：检查mid元素#

1
left = 0; right = size;
2
while (left != right) { /* invariant and left != right */
3
    mid = (left + right) / 2;
4
    if (a[mid] < x) left = mid + 1;
5
    else right = mid;
6
    /* invariant */
7
}

At the end#

left == right and so found if a[left] == x, (or a[right] == x, since left == right)

left == right and so found if a[left] == x (or a[right] == x) what if right never moved. All elements < x, as in picture? Correct? No: we need to be sure that:

1
0 <= left < size

The algorithm#

1
left = 0; right = size;
2
while (left != right) { /* invariant and left != right */
3
    mid = (left + right) / 2;
4
    if (a[mid] < x) left = mid + 1;
5
    else right = mid;
6
    /* invariant */
7
}
8
found = (left != size) && (a[left] == x);

Proving that it terminates: Bound
证明它终止：界限#

Length of grey area is reduced each time, so bound is right - left

Each time the body is carried out:
either left gets bigger, or
right gets smaller
So eventually left == right and it terminates.

O(?)#

Length of grey area is halved each time, so the time complexity of the binary search algorithm is? $O(log~n)$

Efficiency 效率#

“Not found” takes more iterations* than versions of binary search that terminate as soon as an x is found.
“未找到“需要比立即在找到x时终止的二分查找版本更多的迭代。

However, each iteration requires only one access of the array; so more efficient.
然而，每次迭代只需要访问数组一次；因此更高效。

Useful consequence(结果): finds first (lowest-indexed) x

Thinking question: How many more iterations?

Just one more thing …#

There is still a problem! left + right might lead to numeric overflow 数值溢出; This can be avoided by using a bit of algebra 代数: $middle = \frac{left + right}{2} = left + \frac{right-left}{2}$ The expression on the right side will not overflow, since its value never exceeds that of right.

So finally …#

1
left = 0; right = size;
2
while (left != right) { /* invariant and left != right */
3
    mid = left + (right - left) / 2;
4
    if (a[mid] < x) left = mid + 1;
5
    else right = mid;
6
    /* invariant */
7
}
8
found = (left != size) && (a[left] == x);

Summary#

After studying the material of this lecture and the associated parts of the textbook and attempting the exercises, you should be able to:

Explain what is meant by a binary search

Understand the precondition of a binary search.

Correctly implement a binary search given a suitable loop invariant.
给出合适的循环不变式，正确实现二分查找。

Practical exercise 实践练习#

• Problem:
  Input $n(𝑛 ≤ 10^6)$ non-negative integers $𝑎_1, 𝑎_2, 𝑎_3, ……, 𝑎_𝑛, (𝑎_𝑖 ≤ 10^9)$, which are monotonically non-decreasing. Then perform $m(m ≤ 10^5)$ queries. For each query, an integer $q(q ≤ 10^9)$ is given. You are required to output the index of the first occurrence of this number q in the sequence. If it is not found, output -1.
  
• 题目：
  输入 $n(𝑛 ≤ 10^6)$ 个非负整数 $𝑎_1, 𝑎_2, 𝑎_3, ……, 𝑎_𝑛, (𝑎_𝑖 ≤ 10^9)$，它们按单调不降顺序排列。然后进行 $m(m ≤ 10^5)$ 次查询。每次查询给定一个整数 $q(q ≤ 10^9)$。要求输出该数字 q 在序列中第一次出现的下标；若未找到则输出 -1。

• Input:
  • The first line contains two integers n and m, representing the number of integers and the number of queries.
    第一行包含两个整数 n 和 m，分别表示整数个数和查询次数。
  • The second line contains n integers, representing the numbers to be queried.
    第二行包含 n 个整数，表示待查询的有序序列。
  • The third line contains m integers, representing the indices of the numbers to be queried.
    第三行包含 m 个整数，表示要查询的目标数值。
  • Example:

1
11 2
2
1 3 3 5 7 9 11 13 15 15
3
3 12
4
find q[j] 3 at 1
5
find q[j] 12 at -1

Content#

• ‘Straight’ sorting 直接排序
  • Why straight sorting is not very good
    为什么直接排序并不理想
• Quicksort 快速排序
  • Who discovered it
    是谁发现了它
  • Why is it so quick
    为什么它这么快
  • When it is ‘Slowsort’
    什么时候它会变成“慢排序”

Typical scenario 典型场景#

• I sort coursework submissions manually into alphabetical order of author.
  我手动把课程作业按作者字母顺序排序。
  • I took 30 minutes to sort 25 students.
    我给 25 位学生排序花了 30 分钟。
  • How long do you estimate the sorting for 50 students will take him?
    你估计给 50 位学生排序要花多久？

• Most sorting algorithms are $O(n^2)$, that is, time is proportional to number of records squared, so if n doubles the sorting takes 4 times as long
  大多数排序算法是 $O(n^2)$，也就是时间与记录数的平方成正比，所以当 n 翻倍时，排序时间会变为 4 倍。

Insertion Sort 插入排序#

This ‘straight’ sorting method works by inserting the next item of the unsorted stretch of a sequence into the already-sorted first stretch of the sequence.
这种“直接”排序方法的思路是：把未排序区间的下一个元素插入到前面已经排好序的区间中。

1
// post a[0..size-1] is ascending
2
void insertionSort(int [ ] a) {
3
    int i= 1; int x; int j;
4
    while (i < a.length) {
5
        // a[0..i-1] is ascending
6
        // insert value at a[i] into correct position in a[0..i-1]
7
        j= i; x= a[i]; // x is the value originally at a[i]
8
        while (j != 0 && a[j-1] > x) {
9
            // 'budge up' values that are bigger than the one at a[i]
10
            a[j]= a[j-1]; j--;
11
        } // j == 0 OR a[j-1] <= x
12
        // 'drop in' x, the value that was at a[j]
13
        a[j]= x;
14
        i++; // advance to insert next value
15
    } // i >= a.length
16
}

Simple sorting methods 简单排序方法#

• Simple (naive) sorting methods such as selection sort, insertion sort and ‘bubble sort’ are O(n²) – that means they take time proportional to the size of the sequence squared.
  简单（朴素）排序方法，如 选择排序、插入排序和冒泡排序 的复杂度是 O(n²)，即耗时与序列长度的平方成正比。
• They only move values a short distance on each pass.
  它们每一趟只会把元素移动 很短的距离。

Quicksort: discoverer 快速排序：发现者#

• He called it ‘Quicksort’ because it is dramatically quick.
  他将其命名为“Quicksort（快速排序）”，因为它的速度非常快。
• Machine translation: ‘To assist in efficient look-up of words in a dictionary, he discovered the well-known sorting algorithm Quicksort’.
  机翻示例：“为了高效查找字典中的单词，他发现了著名的排序算法 Quicksort。”

Professor Sir Tony Hoare FRS
英国皇家学会会士 Tony Hoare 爵士教授

C.A.R. Hoare, “Quicksort”, The Computer J.,Vol. 5, No. 1, Apr. 1962, pp. 10-15.

1
void quicksort(int [ ] a, int low, int high) {
2
    int i= low, j= high, temp;
3
    int pivot= a[(low + high) / 2];
4
    while (i <= j) {
5
        while (a[i] < pivot) i++;
6
        while (a[j] > pivot) j--;
7
        // forall k :low ..i -1: a[k] < pivot && forall k: j+1 .. high: a[k] > pivot &&
8
        // a[i] >= pivot && a[j] <= pivot
9
        if (i <= j) {
10
            temp= a[i]; a[i]= a[j]; a[j]= temp;
11
            i++; j--;
12
        }
13
    }
14
…
15
}

1
void quicksort(int [ ] a, int low, int high) {
2
    int i= low, j= high, temp;
3
    int pivot= a[(low + high) / 2];
4
    while (i < j) {
5
        while (a[i] < pivot) i++;
6
        while (a[j] > pivot) j--;
7
        if (i <= j) {
8
            temp= a[i]; a[i]= a[j]; a[j]= temp;
9
            i++; j--;
10
        }
11
    }
12
    if (low < j) quicksort(a,low, j); // recursive call
13
    if (i < high) quicksort(a, i, high); // recursive call
14
}

1
void sort(int [ ] a) {
2
    quicksort(a, 0, a.length-1);
3
}

Comparison of sorting 排序比较#

• ‘Straight’, ‘naive’ sorts —— $O(n^2)$
  “直接/朴素”排序 —— $O(n^2)$
• ‘logarithmic sorts’ (Quicksort) —— $O(n\times log~n)$
  “对数级”排序（Quicksort）—— $O(n\times log~n)$
• Bubble sort is the slowest sorting method known! (but has a catchy name)
  冒泡排序 是已知最慢的常见排序方法之一！（但名字很好记）
• Quicksort is one of the fastest.
  快速排序 是最快的方法之一。

References 参考资料#

C.A.R. Hoare, “Quicksort”, The Computer J., Vol. 5, No. 1, Apr. 1962, pp. 10-15. https://portal.acm.org/citation.cfm?id=366644

The Art of Computer Programming, Vol. 3 – Sorting and Searching ISBN 0201896850 Author Donald E Knuth Addison-Wesley

Zonnon Report Zonnon Language Report Jürg Gutknecht Editors: Brian Kirk and David Lightfoot July 2009 https://www.zonnon.ethz.ch/language/report.html

From the Communications of the ACM

Summary 总结#

• After studying the material of this week and attempting the exercises, you should be able to:
  学习本周内容并完成练习后，你应该能够：
  • understand why straight sorting techniques are not very efficient
    理解为什么直接排序技术效率不高
  • understand the principle of Quicksort
    理解 Quicksort 的基本原理
  • know the efficiency of Quicksort (average case)
    掌握 Quicksort 的平均情况效率
  • know worst-case performance of Quicksort
    了解 Quicksort 的最坏情况性能

Better Quicksort (Three-way QuickSort) 更优快速排序（三路快排）#

1
public void quickSort3Way(int[] arr, int low, int high) {
2
    if (low >= high) return;
3
    int lt = low, i = low + 1, gt = high;
4
    int pivot = arr[low];
5
    while (i <= gt) {
6
        if (arr[i] < pivot) {
7
            swap(arr, lt++, i++);
8
        } else if (arr[i] > pivot) {
9
            swap(arr, i, gt--);
10
        } else {
11
            i++;
12
        }
13
    }
14
    quickSort3Way(arr, low, lt - 1);
15
    quickSort3Way(arr, gt + 1, high);
16
}

Concurrent Quicksort 并发快速排序#

1
activity PQuickSort(L, R: integer);
2
var i, j: integer; w, x: ElementOfArray;
3
begin i := L; j := R;
4
  x := MyArray[(L + R) div 2];
5
  repeat
6
    while MyArray[i] < x do i := i + 1 end;
7
    while x < MyArray[j] do j := j - 1 end;
8
    if i <= j then
9
      w := MyArray[i];
10
      MyArray[i] := MyArray[j]; MyArray[j] := w;
11
      i := i + 1; j := j - 1;
12
    end
13
  until i > j;
14
  if L < j then new PQuickSort(L, j) end; (*new activity – runs in parallel *)
15
  if i < R then new PQuickSort(i, R) end; (*new activity – runs in parallel *)
16
end QuickSort;
17

18
procedure ConcurrentQS;
19
begin
20
(* now instantiate the first activity with initial parameters *)
21
  new PQuickSort(integer(0), integer(MAX_SIZE - 1));
22
end ConcurrentQS;

• https://www.zonnon.ethz.ch/language/report.html https://www.zonnon.ethz.ch

Content 内容#

• Implementation and efficiency of ArrayList
  ArrayList 的实现与效率
• Linked lists
  链表
• Insertion into, and deletion from, linked lists.
  链表的插入与删除
• A linked list abstract data type (ADT)
  链表抽象数据类型（ADT）
• Recap of inner classes
  回顾 inner classes（内部类）
• Iterators 迭代器

Arraylist under the bonnet ArrayList 底层原理#

• Defined in the JDK already
  在 JDK 中已经定义

1
public class ArrayList<E> extends AbstractList<E>
2
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
3
{
4
    @java.io.Serial
5
    private static final long serialVersionUID = 8683452581122892189L;
6

7
    /**
8
     * Default initial capacity.
9
     */
10
    private static final int DEFAULT_CAPACITY = 10;
11

12
    /**
13
     * Shared empty array instance used for empty instances.
14
     */
15
    private static final Object[] EMPTY_ELEMENTDATA = {};
16

17
    /**
18
     * Shared empty array instance used for default sized empty instances. We
19
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
20
     * first element is added.
21
     */
22
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
23

24
    /**
25
     * The array buffer into which the elements of the ArrayList are stored.
26
     * The capacity of the ArrayList is the length of this array buffer. Any
27
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
28
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
29
     */
30
    transient Object[] elementData; // non-private to simplify nested class access
31

32
    /**
33
     * The size of the ArrayList (the number of elements it contains).
34
     *
35
     * @serial
36
     */
37
    private int size;
38

39
    /**
40
     * Constructs an empty list with the specified initial capacity.
41
     *
42
     * @param  initialCapacity  the initial capacity of the list
43
     * @throws IllegalArgumentException if the specified initial capacity
44
     *         is negative
45
     */
46
    public ArrayList(int initialCapacity) {
47
        if (initialCapacity > 0) {
48
            this.elementData = new Object[initialCapacity];
49
        } else if (initialCapacity == 0) {
50
            this.elementData = EMPTY_ELEMENTDATA;
51
        } else {
52
            throw new IllegalArgumentException("Illegal Capacity: "+
53
                                               initialCapacity);
54
        }
55
    }
56

57
    /**
58
     * Constructs an empty list with an initial capacity of ten.
59
     */
60
    public ArrayList() {
61
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
62
    }
63

64
    /**
65
     * Constructs a list containing the elements of the specified
66
     * collection, in the order they are returned by the collection's
67
     * iterator.
68
     *
69
     * @param c the collection whose elements are to be placed into this list
70
     * @throws NullPointerException if the specified collection is null
71
     */
72
    public ArrayList(Collection<? extends E> c) {
73
        Object[] a = c.toArray();
74
        if ((size = a.length) != 0) {
75
            if (c.getClass() == ArrayList.class) {
76
                elementData = a;
77
            } else {
78
                elementData = Arrays.copyOf(a, size, Object[].class);
79
            }
80
        } else {
81
            // replace with empty array.
82
            elementData = EMPTY_ELEMENTDATA;
83
        }
84
    }
85
}

• An ArrayList “wraps” an array (whose default capacity is 10, but this can be changed)
  ArrayList 对数组进行了“封装”（默认容量为 10，但可以调整）。
• The size field keeps track of how many elements in the array actually hold data
  size 字段用于记录数组中实际存放了多少个元素。

Adding an element to an arraylist#

• Case 1: Add to end of list without exceeding capacity
  情况 1：在不超过容量的前提下追加到末尾

• Case 2: Add to end of list and exceed capacity
  情况 2：追加到末尾并触发扩容

• Case 3: Insert into list
  情况 3：在中间位置插入

Performance of arraylist ArrayList#

• Adding to an ArrayList can potentially mean that existing data has to be copied from one location in memory to another. This can be inefficient when the size of the list is large.
  向 ArrayList 添加元素可能意味着要把已有数据从一块内存复制到另一块内存；当列表很大时，这会效率较低。
• This problem arises because an ArrayList keeps its data in a contiguous block.
  这个问题产生的原因在于 ArrayList 使用连续内存块存储数据。

Linked lists#

• A linked list keeps each of its elements in a separate block of memory.
  链表会把每个元素存放在独立的内存块中。
• Each element has a pointer to the next element.
  每个元素都包含一个指向下一个元素的指针。 Tail of list: 链表尾部： Pointer to next element is null
  指向下一个元素的指针为 null

1
public class Node {
2
    String data;
3
    Node next;
4
}

1
public static void insertAtHead(String data) {
2
    Node newNode = new Node();
3
    newNode.data = data;
4
    newNode.next = head;
5
    head = newNode;
6
}

1
public static void insertAfter(String data, Node insertPoint) {
2
    Node newNode = new Node();
3
    newNode.data = data;
4
    newNode.next = insertPoint.next;
5
    insertPoint.next = newNode;
6
}

1
public static void deleteHead() {
2
    head = head.next;
3
}

1
public static void deleteAfter(Node deletePoint) {
2
    deletePoint.next = deletePoint.next.next;
3
}

1
public static void printList() {
2
    Node current = head;
3
    while (current != null) {
4
        System.out.println(current.data);
5
        current = current.next;
6
    }
7
}

1
// return first node in list with data value sought,
2
// or null if not found
3
public static Node find(String sought) {
4
    Node current = head;
5
    while (current != null && !current.data.equals(sought)) {
6
        current = current.next;
7
    } // current == null || current.data.equals(sought)
8
    return current;
9
}

1
public class StringLinkedList {
2
    private static class Node {
3
        String data;
4
        Node next;
5
    }
6
    private Node head;
7
    …

Brief introduction of Inner classes 内部类简介#

• An inner class is defined within another class.
  内部类是定义在另一个类内部的类。
• The differences between inner classes and standard classes are that:
  内部类与普通类的区别在于：
  • Each object of the inner class is associated with an object of the enclosing class and has access to fields and methods of the enclosing object (even private ones).
    每个内部类对象都关联一个外部类对象，并可访问外部对象的字段和方法（包括 private）。
  • Similarly the enclosing class, has access to the fields and methods of the inner class (even private ones)
    同样地，外部类也可以访问内部类的字段和方法（包括 private）。
  • An inner class can be private.
    内部类可以声明为 private。

1
public class A {
2
    …
3
    private class B {
4
        …
5
    }
6
}

1
public class A {
2
    private static int i;
3
    private int j;
4
    private static class B{
5
        …
6
    }
7
}

1
public class Out {
2
    …
3
    private class In {
4
        …
5
    }
6
}

Insertion into the linked list 向链表插入#

• We previously described two methods:
  前面我们介绍过两种方法：
  • public static void insertAtHead(String data)
  • public static void insertAfter(String data, Node insertPoint)
• The first of these can be made a public method of our linked list class.
  第一种可以作为链表类的 public 方法。
• The second would have to be private, because it refers to the Node class, which is now private. What we can do is define a public method like this
  第二种因为涉及 Node 类（现已私有）只能设为 private；我们可以改为定义如下 public 方法。

1
public void insert(int index, String data) {
2
    if (index == 0) {
3
        insertAtHead(data);
4
    } else {
5
        Node insertPoint = head;
6
        for (int i = 0; i < index - 1; i++) {
7
            insertPoint = insertPoint.next;
8
        }
9
        insertAfter(data, insertPoint);
10
    }
11
}

Deletion from the list 从链表删除#

• Deletion can be handled in a similar manner to insertion.
  删除操作可以用与插入类似的方式处理。
• Note that both the insert and delete methods may throw a null pointer exception if the index parameter is out of range.
  注意：如果 index 参数越界，insert 和 delete 方法都可能抛出空指针异常。

1
public void delete(int index) {
2
    if (index == 0) {
3
        deleteHead();
4
    } else {
5
        Node deletePoint = head;
6
        for (int i = 0; i < index - 1; i++) {
7
            deletePoint = deletePoint.next;
8
        }
9
        deleteAfter(deletePoint);
10
    }
11
}

Iterating through the list 遍历链表#

• There are circumstances in which we may need to iterate through all the elements in a list. For example, we might want to print them all or sum them (if they are numeric).
  在某些场景下，我们需要遍历链表中的所有元素。例如打印全部元素，或在元素为数值时求和。
• We could write separate methods for all these cases, printList, addList, and so on. However, this would be cumbersome, and we can’t anticipate all cases where we might need to perform an iteration.
  我们可以为这些场景分别写 printList、addList 等方法，但这种做法很繁琐，而且无法预先覆盖所有遍历需求。
• A much more elegant solution is to allow our list to create an Iterator.
  更优雅的方案是让链表能够创建一个 Iterator（迭代器）。

Iterators 迭代器#

• An iterator is an object that is associated with a list, and which implements (at least) the following two methods:
  迭代器是与列表关联的对象，至少应实现以下两个方法：
• next(): After the iterator has been created, the first call to next() returns the first element in the list, the second call returns the second element, and so on.
  next()：创建迭代器后，第一次调用返回第一个元素，第二次调用返回第二个元素，依此类推。
• hasNext(): a boolean method that returns true if there is another element that can be retrieved by next() and false if there is not (because we have already retrieved the last element.
  hasNext()：布尔方法；若后续还有可由 next() 获取的元素则返回 true，否则返回 false（表示已到最后一个元素）。
• Iterators may, optionally, implement a method remove, which deletes the next element in the list.
  迭代器还可以选择性实现 remove 方法，用于删除列表中的下一个元素。

• The Java API includes an interface Iterator, that defines the three methods mentioned above.
  Java API 提供了 Iterator 接口，其中定义了上面提到的三个方法。
• It also includes an interface Iterable which defines just one method iterator() which returns an iterator.
  它还提供了 Iterable 接口，仅定义一个方法 iterator()，用于返回迭代器。
• Lists should implement this interface.
  列表类型应实现这个接口。

1
public class StringLinkedList implements Iterable<String> {
2
    @Override
3
    public Iterator<String> iterator() {
4
        return new StrItr(head);
5
    }
6
    private class StrItr implements Iterator<String> {

1
private class StrItr implements Iterator<String> {
2
    private Node current;
3
    private StrItr(Node start) {current=start;}
4
    @Override
5
    public boolean hasNext() {return (current != null);}
6
    @Override
7
    public String next() {
8
        // Thinking Question: Think more about these three statements
9
        String result = current.data;
10
        current = current.next;
11
        return result;
12
    }
13
    @Override
14
    public void remove() {
15
        throw new UnsupportedOperationException("Not supported");
16
    }
17
}

1
Iterator<String> iter = myList.iterator();
2
    while (iter.hasNext()) {
3
        System.out.println(iter.next());
4
    }

1
for (String s : myList) {
2
    System.out.println(s);
3
}