01/10/2018, 00:36
Hỏi về quickSort khi (j =left) && (i==right)
Ở cuối bài là thuật toán quickSort, mình chạy bằng tay trên giấy thì sẽ tới lúc mà phần bên trái mảng được sắp xong thì: " j = left && i = right"
vậy đoạn này là không thể thực hiện:
QuickSort(a, n, left, j);
if (i < right)
QuickSort(a, n, i, right); ```
vậy theo cách chạy tay thì quá trình Sorting sẽ ngừng ở đây khi mảng chưa được sếp xong. Nhưng máy vẫn sắp xếp bình thường. Vậy mọi người cho mình hỏi ở đây mình bỏ sót cái gì? Tks
void QuickSort(int *&a, int n, int left=0, int right =0)
{
int x, i = left, j = right;
x = a[(left + right) / 2];
do
{
while (a[i] < x) i++;
while (a[j] > x) j–;
if (i <= j)
{
swap(a[i], a[j]);
i++; j–;
}
} while (i <= j);
if (left < j)
QuickSort(a, n, left, j);
if (i < right)
QuickSort(a, n, i, right);
}
Bài liên quan
Đây là cách gọi trong hàm main của mình:
QuickSort(a,n,0, n-1);
anyone? 20 kí tự
các bạn thấy (left = 0), (right =1
vậy ở đoạn sau làm sao left =2; right =4?
Cái này do đệ quy thôi.
Quicksort sort trên từng mảng nhỏ nhỏ, nên cho dùng thấy phần này xong thì chưa chắc phần khác xong -> sort tiếp.
Dễ hiểu thì ổ bánh mì bự thật bự, bạn chia ra 10 phần, ăn 1 phần thì cũng ko thể gọi là ăn hết ổ bánh mì được.
Cảm ơn bạn. Mình mới tìm được là do đệ qui sau khi gọi chính nó xong thì sẽ thực hiện tiếp hàm chính( gọi ban đầu) nên các biến sẽ là biến ban đầu(của hàm chính).