30/09/2018, 16:43
Partition trong QuickSort, giữ nguyên thứ tự các phần tử?
Chuyện là em thường sử dụng Quicksort trong cùng 1 hàm, hôm nay buồn buồn dạo trên hackerrank
, trong phần Quicksort, nó yêu cầu làm partition, mà thứ tự các phần tử giữ nguyên (thứ tự trước sau ấy), em bị vướng chỗ này, không biết làm sao, mọi người cho em ý tưởng với. Cho sẵn pivot (chốt) là phần tử đầu tiên
VD:
mảng: 4 5 3 7 2
output: 3 2 4 5 7
(3 phải đứng trước 2, 5 phải đứng trước 7
Bài liên quan
vẫn chưa tưởng tượng được đề, đăng hết cả đề luôn nha
2 vòng for chắc ổn á
Cái này giống merge sort là chia làm 2 phần bé hơn và lớn hơn hoặc bằng nhưng lại chọn trước sau mới sắp các phần
Code:
Cho một dãy, chốt là phần tử đầu tiên (trong Quicksort ấy, ở đây người ta cho sẵn chốt đúng luôn đỡ phải tìm). Yêu cầu;
VD:
4 5 3 7 2
Thằng đầu tiên (4) sẽ là chốt (đề người ta cho sẵn chốt nằm đó), 5 đứng trước 7, 3 đứng trước 2.
Output: 3 2 4 5 7
3 vẫn đứng trước 2 và 5 vẫn đứng trước 7
@Gio vậy là giờ em phải đi học merge sort à :’(
cơ mà code python ngộ quá nhỉ a[:]. Để em đi học Python, tới bài 15 bên LPTHW rồi.
À. Nói thế là để chỉ trong cpp có hàm stable_sort: khi key = nhau thì nó vẫn giữ đúng thứ tự là nó dùng merge sort.
Ở đây em dùng mảng phụ lọc ra 1 phần < a[0] với 1 phần >=a[0] để giải quyết bài này.
Bình thường qsort sẽ chạy i=0(phần bé hơn) và j=n-1( phần lớn hơn) để tìm cái không thoã mãn và đổi chỗ. Cách làm này tiết kiệm bộ nhớ hơn