Hiểu thuật toán lựa chọn trung bình?

Question

Tôi hiện đang học các thuật toán trong thời gian rảnh nhưng có câu hỏi sau trong khi học các thuật toán select() của chương 3.

Tôi hiểu rằng tôi có thể sử dụng thuật toán select() để tìm số trung bình (số thứ hai n/2) nếu tôi đang sử dụng mảng từ A đến số n.

1) nhưng đây là chút tôi đang cố gắng để hiểu. A = [3, 7, 5, 1, 4, 2, 6, 2]. giả sử đó là mảng. nội dung của mảng sau mỗi cuộc gọi đến phân vùng(), và các tham số trong mỗi cuộc gọi đệ quy của Select() là gì.

một số người có thể giải thích cách họ làm việc này không?

dưới đây là mã giả cho 2 thuật toán.

Select(A, p, r, k) { 
    /* return k-th smallest number in A[p..r] */ 
    if (p==r) return A[p] /* base case */ 
    q := Partition(A,p,r) 
    len := q – p + 1 
    if (k == len) return A[q] 
    else if (k<len) return Select(A,p,q-1,k) 
    else return Select(A,q+1,r,k-len) 
} 

và mã thứ hai là

Partition(A, p, r) { /* partition A[p..r] */ 
    x := A[r] /* pivot */ 
    i := p-1 
    for j := p to r-1 { 
     if (A[j] <= x) { 
      i++ 
      swap(A[i], A[j]) 
     } 
    } 
    swap(A[i+1], A[r]) 
    return i+1 
} 

Cuốn sách tôi đang sử dụng được gọi là nguồn gốc của thuật toán bởi Anne Kaldewaij.

Answer 1

Thuật toán này hoạt động theo hai bước. Bước phân vùng hoạt động bằng cách chọn một phần tử trục, sau đó sắp xếp lại các phần tử của mảng sao cho mọi thứ nhỏ hơn trục xoay sang một bên, mọi thứ lớn hơn trục xoay sang phía bên kia và trục nằm ở vị trí chính xác. Ví dụ, với các mảng

3 2 5 1 4 

Nếu chúng ta chọn một trục 3, sau đó chúng ta có thể phân vùng các mảng như thế này:

2 1 3 5 4 
+--+^+--+ 
^ | ^
| | +--- Elements greater than 3 
| +-------- 3, in the right place 
+------------- Elements less than 3 

Chú ý rằng chúng tôi đã không được sắp xếp mảng; chúng tôi đã làm cho nó gần hơn để được sắp xếp. Đây là tình cờ, bước đầu tiên trong quicksort.

Thuật toán sau đó sử dụng logic sau. Giả sử rằng chúng ta muốn tìm phần tử thuộc về chỉ mục k theo thứ tự sắp xếp (phần tử nhỏ nhất thứ k). Sau đó, liên quan đến trục chúng tôi đã chọn, có ba tùy chọn:

1. Trục nằm ở vị trí k. Sau đó, vì trục chính ở đúng vị trí, giá trị mà chúng tôi đang tìm kiếm phải là trục xoay. Đã được thực hiện.
2. Trục xoay ở vị trí lớn hơn k. Sau đó phần tử nhỏ nhất thứ k phải nằm trong phần của mảng trước trục xoay, vì vậy chúng ta có thể đệ quy tìm kiếm phần đó của mảng cho phần tử nhỏ nhất thứ k.
3. Trục xoay ở vị trí nhỏ hơn k. Sau đó, phần tử nhỏ nhất thứ k phải ở đâu đó trong vùng trên của mảng, và chúng ta có thể recurse ở đó.

Trong trường hợp của chúng tôi, giả sử chúng tôi muốn phần tử nhỏ thứ hai (phần tử ở vị trí 2). Kể từ khi trục đã kết thúc ở vị trí 3, điều này có nghĩa rằng phần tử thứ hai nhỏ phải ở đâu đó trong nửa đầu của mảng, vì vậy chúng tôi sẽ recurse trên subarray

2 1 

Nếu chúng ta muốn các yếu tố trung bình thực tế, kể từ khi trục kết thúc smack ở giữa mảng, chúng tôi sẽ chỉ ra rằng trung bình là 3 và được thực hiện.

Cuối cùng, nếu chúng tôi muốn một cái gì đó như là yếu tố thứ tư nhỏ, sau đó kể từ khi trục là trước khi vị trí thứ 4, chúng tôi sẽ recurse ở nửa trên của mảng, cụ thể là

5 4 

và sẽ tìm kiếm các yếu tố nhỏ nhất đầu tiên ở đây, vì có ba yếu tố trước khu vực này.

Phần còn lại của thuật toán là chi tiết về cách thực hiện bước phân đoạn (có lẽ là phần liên quan nhất của thuật toán) và cách thực hiện lựa chọn ba chiều về việc có nên chấp nhận hay không (ít hơn một chút) khó khăn). Hy vọng rằng, mặc dù, cấu trúc cấp cao này giúp thuật toán có ý nghĩa hơn.

Hy vọng điều này sẽ hữu ích!