Cải tiến thuật toán sắp xếp nhanh nếu có nhiều phím trùng lặp hơn

Question

Tôi đang đọc thuật toán sắp xếp nhanh trong sách của Robert Sedwick Thuật toán và cấu trúc dữ liệu phần 1-4.

template <class item> 

static void quicksort(item [] a, int l, int r) 
{ 
    if(r <= l) return; 
    int i = partition(a,l,r); 
    quicksort(a, l, i-1); 
    quicksort(a, i+1, r); 
} 

template <class item> 
int partition(item a[], int l, int r) 
{ 
    int i = l-1; j = r; item v = a[r]; 

    for(;;) { 
     while(a[++i] < v); 
     while(v < a[--j]) 
      if(j == l) 
       break; 
     if(i >= j) 
      break; // pointer crossing. 
     exch(a[i], a[j]); 
    } 

    exch(a[i], a[r]); 
    return i; 
} 

Sách có văn bản sau đây trên thuật toán trên.

Khi khóa trùng lặp có trong tệp, con trỏ qua là tinh tế. chúng tôi có thể cải thiện quá trình phân vùng một chút bằng cách chấm dứt quét khi tôi < j, và sau đó sử dụng j, thay vì i-1, để phân định đầu bên phải của tập tin con bên trái cho cuộc gọi đầu tiên đệ quy . Cho phép vòng lặp lặp lại một lần nữa trong trường hợp này là cải thiện , bởi vì, khi các vòng quét kết thúc với j và tôi đề cập đến cùng một phần tử, chúng ta kết thúc với hai phần tử trong vị trí cuối cùng của chúng: phần tử đã dừng cả hai bản quét phải có do đó bằng với phần tử phân đoạn và chính phần tử phân đoạn . Thay đổi này có thể đáng để thực hiện, bởi vì, trong trường hợp cụ thể này, chương trình để lại một bản ghi với khóa bằng phím phân vùng trong [r] và điều này làm cho phân vùng đầu tiên trong cuộc gọi nhanh chóng , i + 1, r) thoái hóa, bởi vì phím phải nhất của nó là nhỏ nhất của nó.

Câu hỏi của tôi là

1. Làm sao chúng ta có thể sửa đổi trên chương trình với mô tả dưới đây? Tôi đang gặp khó khăn trong việc sửa đổi nó để hiểu văn bản.
2. Tại sao thuật toán sắp xếp nhanh không hoạt động hiệu quả nếu có nhiều khóa trùng lặp hơn.
3. Cách sửa đổi ở trên cải thiện nếu có thêm nhiều phím sao chép?
4. Tác giả có ý nghĩa gì khi "phân đoạn đầu tiên trong phân loại nhanh cuộc gọi (a, i + 1, r) thoái hóa, vì khóa chính của nó là nhỏ nhất." ? tác giả có nghĩa là gì khi thoái hóa ở đây?

Cảm ơn bạn đã dành thời gian và trợ giúp.

Answer 1

>> Tại sao thuật toán sắp xếp nhanh không hoạt động hiệu quả nếu có nhiều khóa trùng lặp hơn?

Nó trở thành không hiệu quả vì tình trạng vi phạm của bạn là: if(i >= j) break;
như vậy, khi bạn quét từ hai phía với i và j, Nó là khá tốt mà bạn phá vỡ khi i == j thay vì để cho i vượt qua j.

Điều gì xấu có thể xảy ra khi chúng tôi truy cập i==j khi nhiều phím trùng lặp có mặt?

Khi bạn phá vỡ cho i==j; từ đầu tiên trong khi vòng lặp bạn phải có a[i] >= v và từ thứ hai vòng lặp while a[j] <=v nhưng vì chúng ta đang xem xét một 'phá vỡ' cho: i==j như vậy, ví dụ: giống với v, phần tử trục của bạn.

Trong trường hợp như vậy, ngoài cùng của bạn exch(a[i], a[r]); sẽ chỉ trao đổi giá trị trục chính cho chính nó.
Do đó, trong cuộc gọi đệ quy tiếp theo của bạn quicksort(a, i+1, r); cho nửa bên phải của mảng, bạn sẽ có yếu tố tối thiểu ngồi ở đầu ngoài cùng bên phải (chiến lược lựa chọn trục của bạn chỉ đơn giản là item v = a[r];) và tất cả chúng ta đều biết nó là xấu cho QuickSort để lựa chọn một phần tử pivot có giá trị tối thiểu hoặc tối đa của mảng. Do đó, cuộc gọi đệ quy tiếp theo của bạn cho nửa bên phải sẽ là làm thoái hóa một số.
Đó là lý do tại sao tác giả khuyên không nên phá vỡ i == j nhưng bắt chúng ngay trước khi điều đó xảy ra.

>> Tác giả có ý nghĩa gì khi thoái hóa ở đây?

Làm thoái hóa ở đây có nghĩa là cây đệ quy bị xiên lên tức là các vấn đề tiếp theo không được tạo ra với kích thước gần như bằng nhau. Bạn đang phân chia vấn đề về kích thước N thành vấn đề về kích thước N-1 và 1 thay vì cân bằng hơn, như chia nó thành các vấn đề về kích thước N/2 và N/2.

>> Làm cách nào chúng tôi có thể sửa đổi chương trình ở trên bằng mô tả bên dưới?

Chúng ta có thể thực hiện nó như sau:

int partition(int A[], int l, int r){ 
     int i=l-1, j=r, v = A[r]; 
     for(;;){ 
       while(A[++i] < v); 
       while(A[--j] > v) 
         if(j == l) 
           break; 
       if(i>=j) 
         break; 
       swap(A[i], A[j]); 
     } 
     if(i == j){// case when we stopped at the pivot element. 
       j = j+1;//backtrack j 1 step. 
       if(j <= r) 
        swap(A[j], A[r]); 
       return j;// partition the subsequent problems around j now. 
     } 
     swap(A[i], A[r]); 
     return i; 
} 

>> Làm thế nào trên sửa đổi cải thiện nếu có nhiều phím trùng lặp có mặt?
Nó cải thiện hiệu suất bằng cách cho phép bạn KHÔNG tạo ra một kịch bản rõ ràng của một trường hợp thoái hóa.