CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT: C++ ANY PARTITION

BÀI TẬP: ANY PARTITION

Một trong những “phép màu” của thuật toán quick sort là thao tác phân hoạch (gọi nôm na là “phân chia” cũng được) mảng thành 02 phần. Trong đó phần bên trái nhỏ hơn hoặc bằng giá trị pivot và phần bên phải lớn hơn hoặc bằng giá trị pivot.

Hãy viết hàm thực hiện thao tác trên, hàm nhận vào giá trị pivot và mảng a có n phần tử. Hàm thực hiện di chuyển các phần tử trong mảng a và trả về giá trị p sao cho:

• tất cả các phần tử từ a[0] đến a[p] có giá trị nhỏ hơn hoặc bằng pivot. Đây goi là phần bên trái của mảng
• tất cả các phần tử từ a[p+1] đến a[n-1] có giá trị lớn hơn hoặc bằng pivot. Đây gọi là phần bên phải của mảng

INPUT

Dòng đầu tiên chứa n và pivot, lần lượt là số phần tử của mảng cùng giá trị của pivot

n dòng tiếp theo là các giá trị có trong mảng.

Input sẽ đảm bảo pivot <= max(a) và pivot >= min(a), yêu cầu phải có ít nhất 01 phần tử trong mỗi phần của mảng, không phần nào được rỗng.

OUTPUT

Mảng sau khi phân hoạch xuất trên 01 dòng, cách nhau bởi khoảng trắng

Dòng cuối cùng xuất giá trị p mà hàm phân hoạch trả về.GHI CHÚ: Bài này chỉ cần làm đúng mô tả, không cần phải xuất chính xác 100% như ví dụ vẫn có thể pass.

VÍ DỤ

Input	Output
50 -97 72 6 -37 83 13 44 14 89 94 79 17 43 -55 -81 59 55 0 -22 39 -15 -29 -82 20 50 12 17 86 -91 98 70 -8 4 -97 29 -31 -43 53 39 -87 75 -84 -97 95 -85 -58 42 -28 -34 -88 45	-97 -97 -37 83 13 44 14 89 94 79 17 43 -55 -81 59 55 0 -22 39 -15 -29 -82 20 50 12 17 86 -91 98 70 -8 4 72 29 -31 -43 53 39 -87 75 -84 6 95 -85 -58 42 -28 -34 -88 45 1
70 -37 -94 70 -85 48 8 -89 -56 -55 -100 99 33 13 -10 -48 -40 -95 96 65 -90 -100 -91 -94 92 -1 56 42 26 33 -22 53 63 50 65 23 -81 96 -85 50 71 -99 92 -46 9 -46 -82 -66 50 -34 -85 16 74 96 -85 -45 -85 -23 41 95 82 8 -13 -24 -37 92 -49 92 -1 17 -58 71	-94 -85 -89 -56 -55 -100 -48 -40 -95 -90 -100 -91 -94 -81 -85 -99 -46 -46 -82 -66 -85 -85 -45 -85 -37 -49 -58 33 -22 53 63 50 65 23 48 96 8 50 71 70 92 96 9 65 99 33 50 -34 13 16 74 96 -10 92 -1 -23 41 95 82 8 -13 -24 56 92 42 92 -1 17 26 71 26

CODE C++:

1. int partition (int pivot, int *a, int n)
2. {
3.     int left=0;
4.     int right=n-1;
5.     if (left >=right)
6.         return 0;
7.     int i=left;
8.     int j=right;
9.     do
10.     {
11.         while (a[i]<pivot)
12.             i++;
13.         while (a[j]>pivot)
14.             j–;
15.         if (i<=j)
16.         {
17.             int temp=a[i];
18.             a[i]=a[j];
19.             a[j]=temp;
20.             i++;
21.             j–;
22.         }
23.     }
24.     while (i<j);
25.     return j;
26. }