Giải thích giúp em về thuật toán sắp xếp nhanh (quicksort)?

#1

Mấy anh ơi!
Có ai giải thích giúp em thuật toán quicksort (cụ thể là chỗ hàm void partition) này được không ạ?
Mặc dù em biết cơ chế hoạt động của thuật toán, nhưng sao code lại khác hoàn toàn với cách em nghĩ?
Em lấy lòng biết ơn khi các anh đã vào đây để đọc, nếu ai đó giúp em thì em cảm ơn người đó nhiều lắm!
Đây là video minh họa quicksort:

#include <stdio.h>

void quickSort( int[], int, int);
int partition( int[], int, int);


void main() 
{
	int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};

	int i;
	printf("\n\nUnsorted array is:  ");
	for(i = 0; i < 9; ++i)
		printf(" %d ", a[i]);

	quickSort( a, 0, 8);

	printf("\n\nSorted array is:  ");
	for(i = 0; i < 9; ++i)
		printf(" %d ", a[i]);

}



void quickSort( int a[], int l, int r)
{
   int j;

   if( l < r ) 
   {
   	// divide and conquer
	    j = partition( a, l, r);
	   quickSort( a, l, j-1);
	   quickSort( a, j+1, r);
   }
	
}



int partition( int a[], int l, int r) {
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;
		
   while( 1)
   {
   	do ++i; while( a[i] <= pivot && i <= r );
   	do --j; while( a[j] > pivot );
   	if( i >= j ) break;
   	t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}
#2

Mình hiểu cái thuật toán này như sau. Trong một dãy 9 phần tử a[0…8] mình chọn bất kì 1 con pivot (chốt). Như vậy pivot chia dãy này thành 2 phần. Mình bắt đầu tuyển chọn sao cho tất cả các số bên trái pivot thì nhỏ hơn pivot hay a[l] <= pivot (l của left, bên trái). Tất cả các số bên phải pivot thì lớn hơn pivot hay a[r] > pivot (r của right, bên phải). Như vậy ta được 2 dãy mà: dãy đầu tiên <= pivot < dãy thứ 2. Cứ tiếp tục sắp xếp như vậy với 2 dãy đã chia mình sẽ sắp xếp được cả dãy.

Trong hàm partition ở trên không chọn bất kì số nào mà đơn giản lấy luôn số đầu tiên. Và mình thấy nó làm y hệt như cái clip @@. Nhưng có thể tóm tắt lại là hàm do-while đầu tiền dừng tại a[3] = 8 vì không nhỏ hơn chốt = 3. Hàm do-while thứ 2 dừng lại tại ´a[5] = 2´ vì không lớn hơn chốt =3. Tiếp đó đổi vị trí a[3] và a[5] cho nhau qua trung gian là biến t.

Còn trong quickSort thì như nói ở trên đầu tiên chia làm 2 phần phân biệt rồi lại sắp xếp phần bên trái với quickSort(a, l, j-1) và phần bên phải với qickSort(a, j+1, r).

Theo mình hiểu là như thế :smiley:

#3

Tại sao cái này lại xuất hiện hai lần vậy anh?
Một cái trong while và ngoài while

#4

Thực sự thì mình không thấy “quick” ở chỗ nào cả.

#5

Nhanh ở chổ đệ quy mỗi lần chọn pivot nó chia dãy ra làm 2 sắp sắp, rồi 1 nữa tiếp tục chia làm 2, …

#6

Vậy làm sao chọn pivot để chia ra làm 2. Nếu pivot là max hoặc min thì sao ?

#7

Bên dưới là video về tốc độ sắp xếp của các thuật toán khác nhau. Quicksort giữ ngôi vị đứng đầu
Bạn hãy tham khảo :))

2 Likes
#8

Không biết thế nào chứ chắc phải code thực tế đo thời gian :smile: mới tin

1 Like
#9

pivot muốn chọn sao cung được hết, nhưng phổ biết là từng cặp số từ trái qua, nào lớn thì lấy
ví dụ 3 4 9 8 1 2, thì chọn 4 4 3 2 1 4 5 9 thì chọn 4 5 5 7 2 10 4 thì chọn 7

#10

Sao cái quick sort lại nhanh nhất được nhỉ. Mình thấy nó cứ cùi cùi thế nào ấy. :smiley:

#11

Sau khi mình dùng xong 1 cái chốt thì mình lại dùng cái chốt khác. Cái ngoài vòng While là phục vụ cho việc chuyển sang chốt mới là số đầu tiên của dãy bên trái, để mình làm tiếp tục sắp xếp dãy bên trái. Như trong clip là sô 3 nghỉ rồi bây giờ đến lượt số 2 bắt đầu hoạt động.

#12

thuật toán nhanh nhưng khó hiểu qua

#13

Hello bạn, mình coi clip và mình sửa lại method partition theo như cái clip nó làm:

// hàm trả về vị trí của pivot 
int partition(int* a, int l, int r) {
   int pivot = a[r]; //chọn pivot là phần tử cuối cùng của mảng      
   int pos = l - 1;  //pos = vị trí của pivot (giá trị trả về)

   for(int i = l; i < r; i++)
       if (a[i] <= pivot){ // pivot lớn hơn a[i]  
   	    pos = pos+1; //=> tăng vị trí của pivot lên 1
   	    exchange(a, pos, i);
      }
   // đã tìm đc vị trí của pivot rồi thì phải để pivot vào vị trí của nó !!!
   exchange(a, pos+1, r);

   return pos+1;
}

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

Nó dễ hiểu hơn rất nhiều và hy vọng giúp đc bạn :smiley:

1 Like
#15

Bạn nhìn quen quen :)))

#16

chạy visuastudio không báo lỗi chỉ có cánh báo mà chạy ko dduoc. đau đầu quá

#17

Chọn random :smiley: nếu phá được random để DoS thì lạy nó luôn :smiley:

#18

bỏ vô quicksort s ạ?! e làm nó xếp có 1 lần r bí luôn :((

#19

Xem clip thôi thì thấy dở ẹc là đúng :smiley: vì có 10 slot mem quá ít, cỡ đó dùng Insertion đúng hơn.

Chắc quên đệ quy rồi.

#20

Của bạn đây

void quickSort(int* a, int l, int r){
   int j;
   if (l < r) {
	   j = partition(a, l, r);
	   quickSort(a, l, j-1);
	   quickSort(a, j+1, r);
   }	
}

int main(void){
     
    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
    l = 0;
    r = (int)(sizeof(a) / sizeof(a[0]) //length of array

	quickSort( a, l, r);

}
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?