Hỏi về quicksort

omega1100100 · December 30, 2016, 4:42pm

Theo mình biết thì tư tưởng của quicksort là:

Tìm chốt
Chuyển tất cả giá trị < chốt về bên trái
Chuyển tất cả giá trị > chốt về bên phải
quicksort mảng con trái
quicksort mảng con phải
Theo code quicksort dưới (đúng) thì sau mỗi lần đệ quy lại đệ quy (left,j) (i,right), như vậy đã không tuân theo tư tưởng của quicksort. Tức là nếu đúng là phải đệ quy (left, m-1) (m+1, right), mình cứ thắc mắc mãi cái này.

#include <iostream>
using namespace std;

void print(int *a, int n)
{
    int i=0;
    while(i<n){
        cout<<a[i]<<",";
        i++;
    }
}

void swap(int i,int j, int *a){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


void quicksort(int *arr, int left, int right){
    int min = (left+right)/2;
    cout<<"QS:"<<left<<","<<right<<"\n";

    int i = left;
    int j = right;
    int pivot = arr[min];

    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;

        if(i<=j){
            swap(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                quicksort(arr, left, j);
            if(i<right)
                quicksort(arr,i,right);
            return;
        }
    }
}


int main() {
    int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
    quicksort(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    print(arr, (sizeof(arr)/sizeof(arr[0])));
    return 0;
}

nxphuc · December 30, 2016, 9:45am

cái vấn đề nó nằm ở thế nào là “mảng con trái” và “mảng con phải”, thì thấy là sau khi swap hết các cặp, thì có đảm bảo các phần tử từ left đến j sẽ không lớn hơn các phần tử từ i đến right, vậy thì mảng con trái và mảng con chính là tụi nó rồi

Rok_Hoang · December 30, 2016, 9:48am

m là gì? trong tư tưởng với code đâu có thấy m. :)) làm rõ m là hiểu thôi

omega1100100 · December 30, 2016, 10:18am

thì m là vị trí của pivot (chốt) ý bạn!

omega1100100 · December 30, 2016, 10:20am

Vậy chốt sau khi thực hiện sẽ không nằm ở khoảng giữa 2 mảng con đó sao? Nó tụt về mảng con trái

Rok_Hoang · December 30, 2016, 12:56pm

Vậy 2 tập chia ra theo vị trí chốt hay giá trị của chốt?

omega1100100 · December 30, 2016, 1:52pm

À mình hiểu rồi. Trước đây mình nghĩ là chia thành 2 mảng con và chốt phải nằm giữa 2 mảng đó =))