Sắp xếp nhanh - Lý do cho bằng kiểm tra

Question

Nhiều ví dụ trên web về Sắp xếp nhanh (trong Java) là như thế này:

private void quicksort(int low, int high) { 
    int i = low, j = high; 
    int pivot = numbers[low + (high-low)/2]; 

    while (i <= j) { 

     while (numbers[i] < pivot) { 
     i++; 
     } 

     while (numbers[j] > pivot) { 
     j--; 
     } 

     if (i <= j) { 
     exchange(i, j); 
     i++; 
     j--; 
     } 
    } 

    if (low < j) 
     quicksort(low, j); 
    if (i < high) 
     quicksort(i, high); 
} 

Điều tôi hoang mang về là lý do tại sao có những người bằng kiểm tra:

1) while (i <= j) thay vì while (i < j)

2) if (i <= j) thay vì if (i < j)

Có bất kỳ trường hợp cạnh nào mà bằng này là quan trọng không? Từ sự hiểu biết của tôi nếu chúng ta có if(i == j), thì về cơ bản chúng ta sẽ trao đổi cùng một giá trị với cùng một giá trị.

Bất kỳ ai cũng có thể giải quyết câu đố đó cho tôi?

Answer 1

Giả sử rằng điều kiện được thay thế bằng i < j.

Cho phép xem những gì sẽ xảy ra cho một mảng như:

5,4,3,2,1 

Vòng lặp while sẽ chấm dứt với i = 2 và j = 2 và chúng ta sẽ có chồng chéo lời gọi hàm quicksort và các cuộc gọi sẽ:

quicksort(0,2) and quicksort(2,4) 

trong khi nếu chúng tôi có điều kiện này i<=j vòng lặp sẽ kết thúc bằng i = 4 và j = 1 và bây giờ chúng tôi sẽ ld có các cuộc gọi là:

quicksort(0,1) and quicksort(3,4) 

đó là các cuộc gọi phù hợp.

Vì vậy, về cơ bản bạn là đúng đó là không có điểm trong trao đổi các yếu tố tương tự nhưng tác giả của mã phải đã bỏ qua nó để tránh sự cần thiết của việc thêm một điều kiện bổ sung mà bạn không cần phải trao đổi khi i bằng j