Hóa giải ngộ nhận với quicksort

[Tran_Viet_Huy (Trần Việt Huy)]

mình có hàm quicksort đúng:

void quickSort(int *a, int l, int r)
{
    srand(time(NULL));  //khoi tao tham so ham rand()
    int key = a[l + rand() % (r-l+1)];  //lay khoa la gia tri ngau nhien tu a[l] -> a[r]
    //int key = a[(l+r)/2];
    int i = l, j = r;
 
    while(i <= j)
    {
        while(a[i] < key) i++;       // tim phan tu ben trai ma >=key
        while(a[j] > key) j--;       // tim phan tu ben trai ma <=key
        if(i <= j)
        {
            if (i < j)
                swap(int, a[i], a[j]);  // doi cho 2 phan tu kieu int a[i], a[j].
            i++;
            j--;
        }
    }
    //bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
    if (l < j) quickSort(a, l, j);   // lam lai voi mang a[l]....a[j]
    if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

và hàm sai

void quickSort(int *a, int l, int r)
{
    srand(time(NULL));  //khoi tao tham so ham rand()
    int key = a[l + rand() % (r-l+1)];  //lay khoa la gia tri ngau nhien tu a[l] -> a[r]
    //int key = a[(l+r)/2];
    int i = l, j = r;
 
    while(i <= j)
    {
        while(a[i] <= key) i++;       // tim phan tu ben trai ma >=key
        while(a[j] >= key) j--;       // tim phan tu ben trai ma <=key
        if(i <= j)
        {
            if (i < j)
                swap(int, a[i], a[j]);  // doi cho 2 phan tu kieu int a[i], a[j].
            i++;
            j--;
        }
    }
    //bay gio ta co 1 mang : a[l]....a[j]..a[i]...a[r]
    if (l < j) quickSort(a, l, j);   // lam lai voi mang a[l]....a[j]
    if (i < r) quickSort(a, i, r); // lam lai voi mang a[i]....a[r]
}

có ai biết tại sao hàm dưới lại sai khong vậy, nếu có thì cho mình 1 ví dụ sai với -_-. 2 hàm khác nhau mỗi chỗ <=key và <key

[noname00 (HK boy)]

nếu có thì cho mình 1 ví dụ sai

Bạn xem thử:

Ideone.com

Code bị lặp vô hạn.

[Tran_Viet_Huy (Trần Việt Huy)]

à mình hiểu r, sau khi nó swap 0-9 thì nó chạy đến chỉ số 7, từ đấy nó sẽ không tăng hay giảm i,j nữa, mà cái 2 luôn bên phải cái 5 dẫn đến sai :v, tks bạn nhé :33

[rogp10]

Dễ thấy nếu chọn trúng pivot là max hay min thì nó văng tuốt ra ngoài mảng rồi còn đâu.

Nhưng vẫn chưa thấy vì sao bị lặp vô hạn