Thắc mắc về quick sort

[hoahongden2525]

Đây là đoạn code của phần Partition trong quick sort. Nhiệm vụ của Partition là đặt hết các phần tử nhỏ hơn phần tử chốt(pivot) nằm bên trái pivot và các phần tử lớn hơn pivot nằm bên phải pivot. Nhưng sau khi mình chạy đoạn code này : với pivot đầu tiên mình chọn pivot = 2. Nhưng khi in ra kết quả thì nó như sau: 1 1 0 4 3 5 2.
tức là lúc này pivot đã được di chuyển xuống vị trí cuối cùng của mảng. Nhưng lúc này các phần tử 4, 3, 5 đều lớn hơn 2 nhưng lại nằm bên trái 2 điều này mâu thuẫn với thuật toán.
Nhưng nếu mình chạy hết toàn bộ chương trình khi mình bỏ cặp dấu /* */ trong hàm Partition thì kết quả cuối cùng mảng vẫn được sắp xếp đúng.
Các bạn giúp mình giải thích chỗ này với?

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void Partition(int *a, int left, int right){
    int i = left;
    int j = right;
    int k;
    int pivot = a[1];

    while(i <= j){
        while(a[i] < pivot)
            i++;
        while(a[j] > pivot)
            j--;
        if(i <= j){
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    /*if(left < j)
        quickSort(a, left, j);
    if(i < right)
        quickSort(a, i, right);
    */
}

int main(){
    int a[10] = {1,2,5,4,3,0,1};
    int i;

    for(i = 0; i < 7; i++){
        cout << a[i] << " ";
    }
    cout << endl;

    Partition(a, 0, 6);


    for(i = 0; i < 7; i++){
        cout << a[i] << " ";
    }

    return 0;
}

View more random threads:

• moi nguoi chua loi gium e với ạ e k chữa đc hết hix
• Lỗi khi chạy DevC++, không in kết quả lên màn hình?
• Số lần in ra Helloworld
• Hỏi về cách sắp xếp mảng con trỏ và cách gán giá trị con trỏ.
• Debug trên CodeBlocks
• Hàm random trên C++??
• Hỏi về cây nhị phân tìm kiếm
• Trong lập trình hướng đối tượng khi nào dùng thừa kế
• ứng dụng của ngôn ngữ c và mạch điện
• Bài quản lý nhân viên, giúp mình tìm lỗi bài này với?

[gaukhunglong]

Bạn thử thêm phần kiểm tra nếu if (left>=right) thì thoát thử xem [IMG]images/smilies/smile.png[/IMG]
sai điều kiện thoát luôn khỏi hàm.

[Boom]

Trong đk của 2 cái while đó phải có đúng 1 dấu = .

[dudung94]

Trong đk của 2 cái while đó phải có đúng 1 dấu = .

Mình đã sửa lại cho 2 vòng while có thêm dấu = thì giải quyết được việc pivot = 2 nằm đúng chỗ nhưng khi chạy toàn bộ chương trình thì nó vô hạn.

- - - Nội dung đã được cập nhật ngày 10-06-2014 lúc 07:39 PM - - -

Bạn thử thêm phần kiểm tra nếu if (left>=right) thì thoát thử xem [IMG]images/smilies/smile.png[/IMG]
sai điều kiện thoát luôn khỏi hàm.

Ở dưới đã có điều kiện rồi mà bạn mình đang thắc mắc từng bước thực hiện của nó cơ

[10comblog]

Không biết thế nào nhưng đọc vào là ghét cái đoạn này

    int i = left;
    int j = right;
    int k;
    int pivot = a[1];

[blogthanhlap]

^ Ừ hen *facepalm*, ko thấy.
Chia kiểu này dở ẹc (nhưng ko phải ai cũng hiểu vì sao).

[fantasysl06]

Nếu chủ thớt chọn pivot bằng 2 thì có vẽ đúng, vì từ left -> đoạn nào đó <= pivot <= đoạn nào đó -> right (1 1 0 <= "2" <= 4 3 5 2)

[diennguyen59]

^ Hình như cách này đc xem là "dễ giảng" hơn cách kia.
Nhưng mà nó fail nặng vì swap nhiều hơn cách kia gấp đôi.